Infeasible scheduling problem
進行中I am formulating a problem with the following definition:
- I have several orders with ids A-D.
- I want to assign each of these orders to exactly one line, 0 or 1.
- I want to set an indicator variable to know if two IDs are on the same line. That is, if A and B are on the same line, the indicator variable would be 1, and if not, 0.
- I have formulated the above requirement by assuming that if A and B are assigned to the same line, the sum of their indicator variables is 2, so I end up with the piecewise function, A+>= 2 => indicator=1, else 0
I am attempting to solve the following problem with gurobipy and am getting back an infeasible solution. Is there a better way to formulate this set of constraints?
from pulp import *
#lines
line_count=2
lines=[i for i in range(line_count)]
order_ids=['A','B','C','D']
pars = len(order_ids)
#OPTIMIZATION VARIABLES
line_assignment = LpVariable.dicts("Line", [(task, line) for task in order_ids for line in lines], cat='Binary')
share_line = LpVariable.dicts("ShareLine", [(task1, task2) for task1 in order_ids for task2 in order_ids],
cat='Binary')
prob = LpProblem("TaskScheduling", LpMinimize)
# Add constraints
#tasks must be assinged to only one line
for task in order_ids:
prob += lpSum(line_assignment[(task, line)] for line in lines) == 1
for i in range(pars):
for j in range(pars):
if i!=j:
for line in lines:
sum_lines=lpSum(line_assignment[(order_ids[i],line)] + line_assignment[(list(order_ids)[j],line)])
M=1000
tol=.01
#https://cs.stackexchange.com/questions/69531/greater-than-condition-in-integer-linear-program-with-a-binary-variable
prob+=sum_lines - M* share_line[list(order_ids)[i],list(order_ids)[j]] >= 2 -M #-tol
prob+=sum_lines - M*share_line[list(order_ids)[i],list(order_ids)[j]]<= 1 #+tol
#symmetric constraint AB = BA
prob+= share_line[list(order_ids)[i],list(order_ids)[j]] ==share_line[list(order_ids)[j],list(order_ids)[i]]
#Build the solverModel for your preferred
solver = getSolver('GUROBI', timeLimit=20) #THIS WORKS BUT IS LIMITED
prob.solve(solver)
# Print the solution'
for key in line_assignment.keys():
#print(key, line_assignment[key])
if key[1]==1:
print(key[0], "Line: "+str(key[1]))##, value(line_assignment[key]))
for key in share_line.keys():
print(key, share_line[key].varValue)
0
-
正式なコメント
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
Consider replacing your constraints by:
prob += sum_lines <= share_line[list(order_ids)[i],list(order_ids)[j]] + 1
This will enforce that share_line becomes 1 when both orders in the (i,j) pair are scheduled on the same line.
0
投稿コメントは受け付けていません。
コメント
2件のコメント