Test if the start solution is feasible
I have a start solution for MIP (with some bilinear and MIN constraints). However, it seems the solver ignores it: I get User MIP start did not produce a new incumbent solution message. I wonder if it is a mistake in my provided feasible solution (either mathematical or just a programming typo somewhere, e.g., wrong indices or whatever). For that, it would be nice to see which constraints are NOT satisfied by my provided solution. Is there a way to check that with Gurobi?
At the moment, I am still testing my model on some small data, so the solver is anyway able to find an optimal solution. However, I will further run it on a much larger data, where - I guess - providing a feasible solution might be helpful.
-
The solver cannot tell you which constraints or bounds are violated by the MIP start. You will have to test this yourself. (Iterate over the constraints/bounds and compute each violation.)
How do you create your MIP start? Is it a complete or a partial one?
0 -
I have a (complete) solution which (I believe) satisfies the constraints of my model - but its objective is far from optimal. After creating the variables of the model, I set the variables by calls like the following:
v_kappa[m][q].set(GRB_DoubleAttr_Start, start.kappa[m][q])
Here, v_kappa[m][q] is a GRBVar object created in the model (by calling v_kappa[m] = addVars(...)), and start is a structure with prepared values of my MIP start solution.
After that, I call model.optimize().
If Gurobi cannot tell me what constraints are violated, how can I at least make sure that I correctly understand the solver: does it think that my solution doesn't satisfy the constraints or discard the solution because of some other reasons?
0 -
Okay, I think I found the solution here: https://www.gurobi.com/documentation/9.0/refman/start.html
If you want to diagnose an infeasible MIP start, you can try fixing the variables in the model to their values in your MIP start (by setting their lower and upper bound attributes). If the resulting MIP model is infeasible, you can then compute an IIS on this model to get additional information that should help to identify the cause of the infeasibility.
1 -
I had the same question. I followed the guidance and set the upper and lower bounds equal to my initial solution, and the resulting model is feasible. Moreover, the objective function of the initial solution is better than Gurobi's solution, and yet I still get the message "User MIP start did not produce a new incumbent solution." How is this possible?
2 -
I would like to investigate. Could you please send me
- your original model as *.mps file,
- your MIP start as *.mst file or *.sol file, and
- your modified model with bounds fixed to the MIP start as *.mps file?
Please send this to achterberg (at) gurobi (dot) com.
Thanks,
Tobias
0 -
I am facing the same issue,
I provide a partial start solution (there is a unique completion to this partial solution) and Gurobi says: "User MIP start did not produce a new incumbent solution.". For this, Gurobi just keeps on running until it reaches the time limit (set to 2 mins) without even a feasible solution to the program.
When I set the lower and upper bounds as the start solution value, Gurobi immediately terminates (as other variables are uniquely determined) and yields that the solution is feasible. The program is a mixed-integer bilinear program. Why could this be happening?
The start solution was generated by running the same model with a subset of the original constraints (without the bilinear constraints and some other constraints) and a different objective.
1 -
I suspect that this is a numerical issue. When you fix the bounds of the variables to your solution values, what does Gurobi say at the end about the violations of the solution? Does it report violations that are larger than 1e-6?
I would be interested in taking a closer look. Could you send me the *.mps and *.sol or *.mst file?
Regards,
Tobias
0 -
That was the first thing I checked, the bound, constraint, and integrality violation, all are < 1e-14.
The problem we are trying to diagnose is Gurobi taking a lot of time to find a feasible solution when the partial start solution completes to a unique feasible solution. (It was verified that the partial start was feasible by setting the variable bounds as start solution and in this scenario, the solver immediately returns). For reference for this model:
Presolved model has 413 SOS constraint(s)
Presolved model has 162 bilinear constraint(s)
Variable types: 1550 continuous, 1895 integer (1742 binary)If I have a smaller problem then by default, the solver immediately returns (with our without partial start). I can share the model but it is fairly large for it to cause Gurobi to take time. Do I send it to: achterberg (at) gurobi (dot) com?
There is another thing I found, if I have a much larger problem, then Gurobi has a hard time even completing the partial solution to the unique feasible solution when the variable bounds are set so that there is only one feasible solution. At this point, Gurobi just needs to solve a system of equations where each constraint has 1 unknown variable, even for this it takes >300s to find that unique feasible solution. I guess the cause of this might have something to do with either piece-wise linear constraints or quadratic equality constraints (non-convex). For reference, for this model:
Presolved model has 2040 SOS constraint(s)
Presolved model has 2044 bilinear constraint(s)
Variable types: 5106 continuous, 4084 integer (2040 binary)0 -
Also, I am using version:
Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (linux64)
I am assuming the issue referred to here: https://groups.google.com/forum/#!topic/gurobi/C1bIDPFvtKY has been fixed in that version.
0 -
This is really strange. Your models are not that large that they would lead to 300 seconds just for solving an equation system.
Yes, could you please send your data to achterberg (at) gurobi (dot) com? I would like to take a closer look. Ideally, I would need the *.mps files and the corresponding *.mst or *.sol files (A *.mst file only has the integer variables, a *.sol file is the complete solution).
Regards,
Tobias
0 -
import gurobipy as gp
import random
NUM = 10000
UB = 8
m = gp.Model('test')
xs = m.addVars(range(NUM), vtype=gp.GRB.INTEGER, lb=1, ub=UB, name='x')
ys = m.addVars(range(NUM), vtype=gp.GRB.CONTINUOUS, lb=0, name='y')
zs = [random.random()*50 for i in range(NUM)]
for i in range(NUM):
m.addConstr(xs[i] * ys[i] == zs[i])
m.setParam(gp.GRB.Param.NonConvex, 2)
ymax = m.addVar(vtype=gp.GRB.CONTINUOUS, name='ymax')
m.addGenConstrMax(ymax, ys)
m.setObjective(ymax)
m.ModelSense = gp.GRB.MINIMIZE
# m.setParam(gp.GRB.Param.MIPFocus, 2)
m.setParam(gp.GRB.Param.TimeLimit, 120)
m.update()
m.optimize()
# """
# Above takes around 30 to 90 seconds on
# AMD Ryzen 5 3600 6-Core Processor (12 H/W Threads)
# 16 GB RAM
# """
# Known optimal solution:
ymax_opt = 0
for i in range(NUM):
xs[i].lb = UB
this_ys = zs[i] / UB
ys[i].start = this_ys
ymax_opt = max(ymax_opt, this_ys)
ymax.start = ymax_opt
print(ymax_opt)
m.update()
m.optimize()This takes around 80ish seconds on my machine.
This is stylistically similar to my original model, where the zs variables are set from the start solution and are not constants.
So the above emulates the case when I set variable bounds on zs variables to fix their value.Surprisingly, If I change NUM to 10 times its value, the model immediately solves. So I am not sure if this would reproduce on your machine. I ran it multiple times, it does take 30 to 80s for each run for the above code.
Here is a log for reference:
Using license file /home/anupa/gurobi.lic
Academic license - for non-commercial use only
Changed value of parameter NonConvex to 2
Prev: -1 Min: -1 Max: 2 Default: -1
Changed value of parameter MIPFocus to 1
Prev: 0 Min: 0 Max: 3 Default: 0
Changed value of parameter TimeLimit to 120.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (linux64)
Optimize a model with 0 rows, 20001 columns and 0 nonzeros
Model fingerprint: 0xf3277a38
Model has 10000 quadratic constraints
Model has 1 general constraint
Variable types: 10001 continuous, 10000 integer (0 binary)
Coefficient statistics:
Matrix range [0e+00, 0e+00]
QMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 8e+00]
RHS range [0e+00, 0e+00]
QRHS range [3e-03, 5e+01]
Presolve added 8757 rows and 0 columns
Presolve removed 0 rows and 2486 columns
Presolve time: 0.13s
Presolved: 43785 rows, 17515 columns, 87570 nonzeros
Presolved model has 8757 bilinear constraint(s)
Variable types: 8758 continuous, 8757 integer (0 binary)
Root relaxation: objective 6.249121e+00, 21668 iterations, 0.12 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 6.24912 0 14408 - 6.24912 - - 0s
0 0 6.24912 0 14408 - 6.24912 - - 0s
0 0 6.24912 0 14027 - 6.24912 - - 0s
0 0 6.24912 0 13837 - 6.24912 - - 0s
0 0 6.24912 0 13970 - 6.24912 - - 1s
0 0 6.24912 0 12102 - 6.24912 - - 1s
0 0 6.24912 0 12260 - 6.24912 - - 1s
0 0 6.24912 0 9678 - 6.24912 - - 1s
0 0 6.24912 0 9591 - 6.24912 - - 1s
0 0 6.24912 0 8734 - 6.24912 - - 2s
H 0 0 39.8783374 6.24912 84.3% - 2s
H 0 0 11.5481040 6.24912 45.9% - 3s
H 0 2 8.3300642 6.24912 25.0% - 3s
0 2 6.24912 0 9019 8.33006 6.24912 25.0% - 3s
197 303 6.24912 35 9562 8.33006 6.24912 25.0% 20.2 5s
831 1252 6.24912 140 9506 8.33006 6.24912 25.0% 5.4 10s
2109 2462 6.24912 353 9440 8.33006 6.24912 25.0% 2.8 15s
3066 3385 6.24912 502 9306 8.33006 6.24912 25.0% 2.0 21s
3720 4086 6.24912 611 9198 8.33006 6.24912 25.0% 1.6 25s
4490 4902 6.24912 739 9076 8.33006 6.24912 25.0% 1.4 30s
5303 5756 6.24912 874 8946 8.33006 6.24912 25.0% 1.2 35s
H 6272 5959 8.3259060 6.24912 24.9% 1.0 38s
H 6273 5661 8.3233186 6.24912 24.9% 1.0 39s
H 6275 5380 6.9373923 6.24912 9.92% 1.0 39s
H 6277 5111 6.9035873 6.24912 9.48% 1.0 39s
6279 5112 6.24912 202 3081 6.90359 6.24912 9.48% 1.0 40s
H 6279 4857 6.8974937 6.24912 9.40% 1.0 40s
H 6282 4616 6.8931683 6.24912 9.34% 1.0 40s
H 6314 4413 6.8916486 6.24912 9.32% 7.7 41s
7069 5189 6.24912 77 5165 6.89165 6.24912 9.32% 7.0 45s
8600 6001 6.34246 200 4656 6.89165 6.24912 9.32% 22.9 50s
9953 7076 6.24912 297 4716 6.89165 6.24912 9.32% 57.0 56s
10658 7828 6.60963 345 3878 6.89165 6.24912 9.32% 71.6 60s
12320 8984 6.24912 469 4372 6.89165 6.24912 9.32% 95.4 66s
H13103 8579 6.8728021 6.24912 9.07% 113 68s
H13174 7128 6.6524118 6.24912 6.06% 113 68s
13319 7469 cutoff 543 6.65241 6.24912 6.06% 111 70s
14642 8235 6.24912 656 3535 6.65241 6.24912 6.06% 102 75s
15969 9182 6.24912 751 3469 6.65241 6.24912 6.06% 100 81s
H17207 1329 6.2491208 6.24912 0.00% 101 84s
Cutting planes:
MIR: 5278
RLT: 3966
Explored 17499 nodes (1786441 simplex iterations) in 84.48 seconds
Thread count was 12 (of 12 available processors)
Solution count 10: 6.24912 6.65241 6.8728 ... 8.32591
Optimal solution found (tolerance 1.00e-04)
Best objective 6.249120786816e+00, best bound 6.249120786816e+00, gap 0.0000%
6.249120786816276
Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (linux64)
Optimize a model with 0 rows, 20001 columns and 0 nonzeros
Model fingerprint: 0x1829ebe3
Model has 10000 quadratic constraints
Model has 1 general constraint
Variable types: 10001 continuous, 10000 integer (0 binary)
Coefficient statistics:
Matrix range [0e+00, 0e+00]
QMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [8e+00, 8e+00]
RHS range [0e+00, 0e+00]
QRHS range [3e-03, 5e+01]
Loaded user MIP start with objective 6.24912
MIP start from previous solve did not produce a new incumbent solution
Presolve removed 0 rows and 20001 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.01 seconds
Thread count was 1 (of 12 available processors)
Solution count 1: 6.24912
Optimal solution found (tolerance 1.00e-04)
Best objective 6.249120786816e+00, best bound 6.249120786816e+00, gap 0.0000%From the log, Gurobi was able to find the correct bound but not the optimal solution. So I tried MIPFocus 2, which solves immediately. For my original problem, I was using MIPFocus 1 as it was struggling to even find feasible solutions.
I am experimenting with my original problem if MIPFocus = 2 rectifies the high solving time, I will probably share the requested files after that.
0 -
Also, I wanted to confirm one thing. For the below code, Gurobi saying "User MIP start did not produce a new incumbent solution" just means that it already knows the start solution right? i.e. since we are feeding it the solution it produced and it already knows it. Or could it be hinting to some problem with the start solution itself?
In other words, is the loop marked TAG below needed in the first place?
m.optimize()
# TAG:
for v in m.getVars()[:COUNT]:
v.start = v.x
# ^ Not all variables are explicitly assigned start value
# Add more vars and constraints
# Change objectives
m.update()
m.optimize()0 -
Also, I wanted to clarify, I wasn't quite correct when saying there is unique completion for the partial solution. There are more feasible solutions. Like in the above example, xs can take smaller values than `UB` as well, the solver does need to decide that.
Having said that, I still feel the solver is taking more time than it should be.
I ran the experiments with my original model and they are taking a similar time as before even with MIPFocus 2. There is something else going on I guess. I will share the files.
0
Please sign in to leave a comment.
Comments
13 comments