Unable to get results for existing MIP model
AnsweredHi,
I'm trying to use Gurobi to solve an existing MIP model (found in page 403 of https://link.springer.com/content/pdf/10.1007/s10846-015-0211-5.pdf):
\[\max \sum_{k=1}^{K} \sum_{i=1}^{N} x^{k}_{i} \]
s.t.
\[\sum_{k=1}^{K} x^{k}_{i} \leq 1, \forall i = 1 ... N (1)\]
\[t^{k}_{i} + Td - t^{k}_{j} \leq M * (2 - x^{k}_{j} - x^{k}_{i} ), \forall k = 1 .. K, i,j : x_{j} \geq x_{i} (2)\]
\[t^{k}_{i} \leq max( TW^{k}_{i}), \forall i = 1... N, \forall k = 1...K (3)\]
\[t^{k}_{i} \geq min( TW^{k}_{i}), \forall i = 1... N, \forall k = 1...K (4)\]
where
\[x^{k}_{i} \in \{0,1\} , t^{k}_{i} \in R^{+} \]
which I tried to model in the code at the bottom (based on the Gurobi technician routing example). I'm wondering if my problem is with the second constrain because I cannot figure out how to add the conditional \(i,j : x_{j} \geq x_{i} \) without getting either "var cannot be compared to var" or the "are you trying to add a a<= b <= c constraint" error messages, or if it's something else all together.
Any help would be greatly appreciated!
# lists:
K = [k.arm_n for k in arm]
N = [i.index for i in fruit]
# dictionaries:
# TW start and end are dependant on both the arm number and fruit number, requiring dictionary with a list
# see canCover in technician gurobi example[k]
TW_start = {i : [j.TW_start for j in job if j.fruit_i.index == i] for i in N}
TW_end = {i : [j.TW_end for j in job if j.fruit_i.index == i] for i in N}
### Create model
m = gp.Model("melon_mip")
### Decision variables
# Arm-fruit assignment (is fruit i picked by arm k)
x = m.addVars(K, N, vtype=GRB.BINARY, name="x")
# Time arm k reaches fruit i
t = m.addVars(K, N, lb=0, name="t")
### Constraints
# At most one arm can be assigned to a fruit (1)
m.addConstrs((x.sum('*', i) <= 1 for i in N), name="assignOne")
# Time elapsed between pickup of any two fruit reached by the same arm is at least Td (2)
m.addConstrs((t[k, i] + Td - t[k, j] <= M * (2 - x[k, i] - x[k, j]) for i in N for j in N for k in K), name='atLeast')
# Ensure each node is visited within the given time window (3) and (4)
m.addConstrs((t[k, i] <= max(TW_start[i][k], TW_end[i][k]) for i in N for k in K), name='timeWinA')
m.addConstrs((t[k, i] >= min(TW_start[i][k], TW_end[i][k]) for i in N for k in K), name='timeWinB')
### Objective function
m.setObjective(gp.quicksum(x[k, i] for i in N for k in K) , GRB.MAXIMIZE)
Using this code, I get the output:
*************************** Solving base scenario model***************************
Set parameter Username
Academic license - for non-commercial use only - expires 2022-02-07
Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (linux64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 32040 rows, 864 columns and 124416 nonzeros
Model fingerprint: 0x93dcd1d8
Variable types: 432 continuous, 432 integer (432 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+03]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [4e-02, 2e+03]
Found heuristic solution: objective -0.0000000
Presolve removed 32040 rows and 864 columns
Presolve time: 0.11s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.15 seconds (0.02 work units)
Thread count was 1 (of 4 available processors)
Solution count 1: -0 No other solutions better than -0
Optimal solution found (tolerance 1.00e-04)
Best objective -0.000000000000e+00, best bound -0.000000000000e+00, gap 0.0000%
a total of 0 fruit were harvested out of 72
-
Hi Natalie,
Based on the paper (page 4), it seems to me that each fruit \(i\) has known \((x_i, y_i)\) coordinate values . You just need to ensure that the second constraint is implemented for the pair of \((i, j)\) fruits where the \(x\)-coordinate of fruit \(j\) is not smaller than the \(x\)-coordinate of fruit \(i\).
It should be enough to modify the second constraint as below:
m.addConstrs(
(
t[k, i] + Td - t[k, j] <= M * (2 - x[k, j] - x[k, i])
for i in N
for j in N
for k in K
if x_coordinate[j] >= x_coordinate[i]
),
name="atLeast",
)Best regards,
Maliheh
0 -
Hi Maliheh!
Thank you for your reply, unfortunately the results are still zero. Adding the if-conditional did decrease the model's rows by half, so something seems to have changed.
How did you identify that the \(x\) values in the condition \(x_j >= x_i\) are for the coordinates and not the \(x^k_i\) or \(x^k_j\) boolean variables? I ask because I had assumed that the \(j\) fruit was behind the \(i\) fruit and so \(x_j >= x_i\) didn't make sense to me. I had assumed \(x_j == x^k_j\), and the condition only triggered if the j-th fruit had also been picked along the i-th fruit. Would this be possible?
Assuming this constraint is not the problem, are there recommended tests I could do to find out why the results are staying at zero? Can I somehow get more output to see how the model is running/making decisions? Are there common issues that a beginner might do that leads to these types of problems?
Thank you again for your help!
Natalie
0 -
Hi Natalie,
How did you identify that the x values in the condition xj>=xi are for the coordinates and not the xik or xjk boolean variables? I ask because I had assumed that the j fruit was behind the i fruit and so xj>=xi didn't make sense to me. I had assumed xj==xjk, and the condition only triggered if the j-th fruit had also been picked along the i-th fruit. Would this be possible?
It is definitely odd to define two different notations referring to the same thing. I have not read the paper in detail, however, in Fig 2, \((x_i, y_i)\) are clearly defined as coordinates. Furthermore, there is an inherent assumption in the second constraint that if fruits \(i\) and \(j\) are picked up by the same arm, the pickup time of fruit \(j\) is at least \(Td\) time units apart from the pickup time of fruit \(i\). This intuitively makes sense if fruit \(j\) is placed farther away along the \(x\)-coordinate.
Assuming this constraint is not the problem, are there recommended tests I could do to find out why the results are staying at zero? Can I somehow get more output to see how the model is running/making decisions? Are there common issues that a beginner might do that leads to these types of problems?
You can call the write() method on the model object to write the solution into a file. You can then read the solution back into your program and investigate why the objective value worsens if the solution moves away from zero. To access the value of the decision variables, you can also use the getAttr() method. For example, you can have:
model.getAttr("X", model.getVars())
Best regards,
Maliheh
0
Please sign in to leave a comment.
Comments
3 comments