Infeasibility while adding a constraint
Awaiting user input
-
In the mathematical formulation of constraint \((4)\), constraints are added for all \( \ell = 2, \ldots, d_k \). However, your implementation adds constraints for all \( \ell = 1, \ldots, d_k \). So, you could try iterating over \( \texttt{dk[1:]} \) instead of \( \texttt{dk} \) in your second Model.addConstrs() call:
m.addConstrs( (x[j,k,l] <= x.sum('*',k,dk[dk.index(l)-1]) for j in J for k in K for l in dk[1:]), name="sequence")2 -
Thank you, this works!
1 -
Hi Eli Towle,
I have had continue working on the model and another problem appears.
When I run the program I obtained an incorrect solution:
Job1 assigned to machine 1.2 at sequence 1. Start at day 0.00. Processing time 24h
Job2 assigned to machine 1.2 at sequence 3. Start at day 0.00. Processing time 24 h
Job3 assigned to machine 2.2 at sequence 3. Start at day 0.03. Processing time 24 h
There is something wrong with the sequence and starting time, because the solution has to be:
Job1 assigned to machine 1.2 at sequence 1. Start at day 0.00. Processing time 24h
Job2 assigned to machine 1.2 at sequence 2. Start at day 1. Processing time 24.0 h
Job3 assigned to machine 2.2 at sequence 1. Start at day 0. Processing time 24 h
The constraints and variables used for starting time and sequence are:
J = ['Job1', 'Job2', 'Job3']
K = ['1.2', '2.2]
p = m.addVars(J, name="p")
t = m.addVars(J, name="t")
d = range(1,10) #sequence 1 (minimum) to sequence 10 (maximum)
x = m.addVars(J, K, d, vtype=GRB.BINARY, name="x")
M = {(i,j) : 10000000000000000 for i in J for j in J}
m.addConstrs((t[j] >= t[i] + p[i] - M[i,j]*(2-x[j,k,l]-x[i,k,d[d.index(l)-1]]) for i in J for j in J for k in K for l in d[1:]),name="startingTime")
m.addConstrs(t[j] >= 0 for j in J for k in K)
m.addConstrs((x.sum('*',k,l) <= 1 for k in K for l in d), name="assignOneSequence")
m.addConstrs( (x.sum('*',k,l) <= x.sum('*',k,d[d.index(l)-1]) for k in K for l in d[1:]), name="sequence")I don't know how to fix the problem: stablish the correct sequence at the correct starting time. Visualising the problem the solution has to be something like that:
Thank you!
Susana.
0 -
Can you share a mathematical formulation of this model? Additionally, it would be helpful to see a complete, self-contained code example that reproduces the results you currently see.
Here are some thoughts I have looking over the code you posted:
- The model has no objective function. Are we supposed to be minimizing the makespan?
- The formulation in your original post included \( \texttt{assignOne} \) constraints. Are these constraints still part of the model? For the formulation in your code snippet, a feasible solution can be constructed by setting every variable to \( 0 \).
- Is \( p_i \) the processing time of job \( i \in J \)? If so, shouldn't each \( p_i \) be a fixed value instead of a model variable?
- \( \texttt{range(1,10)} \) generates the sequence \( 1, \ldots, 9 \). This contradicts your comment about \( \texttt{d} \) being a sequence from \( 1 \) to \( 10 \).
- You add the constraints \( t_j \geq 0 \) for all \( j \in J \) and \( k \in K \). There is no \( k \) in this constraint; you effectively add each \( t_j \geq 0 \) constraint \( |K| \) times. Anyways, you can omit these constraints completely; by default, variables like \( t \) added to the model via Model.addVars() have a lower bound of \( 0 \).
- It's good practice to choose big-\(M\) values that are as tight/small as possible. \(10^{16} \) is not only a very loose bound, but the coefficient is also so large it could cause numerical issues for solvers like Gurobi. It looks like \( M \) serves as an upper bound on \( t_i + p_i - t_j \) (\(i \in J, j \in J\)); I would set \( M \) to be the largest reasonable value for this expression. Depending on what units are represented by the \( t \) and \( p \) variables, this should be a small value (probably no greater than \(100\) for this instance).
0
Please sign in to leave a comment.
Comments
4 comments