Infeasible scheduling problem
OngoingI 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
-
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
Please sign in to leave a comment.
Comments
1 comment