MIP start did not produce a new incumbent solution
Answered
I have seen this title has been used before (in Gurobi Google Groups) but I could not find a satisfying response for my specific issue. I am trying to solve a MIP with two sets of variables: x[v] and y[a,v]. There are more variables involved but everything turns around these two; the others are determined based on these two. I wanted to push a warm start to improve the computational time but confronted with the response given in the title "MIP start did not produce a new incumbent solution." So, I am wondering why Gurobi printed this message.
As shown in the example, I implemented the initialization. Here is my code:
for v in V:
for a in Person_based_activity_IDs[v-1]:
y[a,v].start = 1.0
for v in V:
x[v].start = 1.0
Based on my initialization, I can precalculate the obj. function as 2360. My init. also does not cause an infeasibility. Indeed, if it did violate any constraint it was going to print: "MIP start violates constraint ...... by ....." Long story short, here is my log when I run it by pushing the above start.
Optimize a model with 13350 rows, 1552 columns and 118464 nonzeros
Variable types: 1216 continuous, 336 integer (336 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+03]
Objective range [4e+00, 8e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 3e+03]
MIP start did not produce a new incumbent solution
Presolve removed 8144 rows and 944 columns
Presolve time: 0.94s
Presolved: 5206 rows, 608 columns, 84013 nonzeros
Variable types: 0 continuous, 608 integer (344 binary)
Found heuristic solution: objective 3836.0000000
Found heuristic solution: objective 3448.0000000
Found heuristic solution: objective 3416.0000000
Found heuristic solution: objective 3000.0000000
Root relaxation: objective 2.280000e+03, 3192 iterations, 0.54 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2280.00000 0 151 3000.00000 2280.00000 24.0% - 3s
Another try with MIP start
H 0 0 2400.0000000 2280.00000 5.00% - 4s
0 0 2280.00000 0 128 2400.00000 2280.00000 5.00% - 5s
0 0 2280.00000 0 108 2400.00000 2280.00000 5.00% - 5s
0 0 2280.00000 0 114 2400.00000 2280.00000 5.00% - 5s
H 0 0 2340.0000000 2280.00000 2.56% - 5s
0 0 2280.00000 0 114 2340.00000 2280.00000 2.56% - 5s
0 0 2280.00000 0 136 2340.00000 2280.00000 2.56% - 6s
0 0 2280.00000 0 120 2340.00000 2280.00000 2.56% - 6s
0 0 2280.00000 0 101 2340.00000 2280.00000 2.56% - 7s
0 0 2280.00000 0 109 2340.00000 2280.00000 2.56% - 7s
0 0 2280.00000 0 110 2340.00000 2280.00000 2.56% - 8s
0 0 2280.00000 0 107 2340.00000 2280.00000 2.56% - 8s
0 0 2280.00000 0 97 2340.00000 2280.00000 2.56% - 8s
0 0 2280.00000 0 54 2340.00000 2280.00000 2.56% - 9s
0 0 2280.00000 0 128 2340.00000 2280.00000 2.56% - 9s
0 0 2280.00000 0 126 2340.00000 2280.00000 2.56% - 9s
0 0 2280.00000 0 101 2340.00000 2280.00000 2.56% - 11s
0 0 2280.00000 0 101 2340.00000 2280.00000 2.56% - 11s
0 2 2280.00000 0 100 2340.00000 2280.00000 2.56% - 13s
20 21 2280.00000 6 216 2340.00000 2280.00000 2.56% 170 15s
Cutting planes:
Implied bound: 1
MIR: 26
Explored 89 nodes (19443 simplex iterations) in 17.09 seconds
Thread count was 4 (of 4 available processors)
Solution count 6: 2340 2400 3000 ... 3836
Time limit reached
Best objective 2.340000000000e+03, best bound 2.280000000000e+03, gap 2.5641%
Here are the things I don't understand.
- Why does Gurobi even bother finding a Heuristic that is higher than my guess?
Found heuristic solution: objective 3836.0000000 Found heuristic solution: objective 3448.0000000 Found heuristic solution: objective 3416.0000000 Found heuristic solution: objective 3000.0000000
- I understand it was explained here and there that the message "MIP start did not produce a new incumbent solution" means Gurobi knows a better solution than you provided. If it knows a better solution, why does the incumbent start from 3000? I guess, this number is related to the last number given above.
- Does "MIP start did not produce a new incumbent solution" mean Gurobi did not use my start at all? This is a repeated question from other posts.
- I also set heuristics to 0 as suggested in here, but it made the solution even worse with a long repeat on 5% gap. Any alternatives that I can try?
When I tried to let y[a,v] variables free but set x[v]=1 as a start, I got the following log:
Optimize a model with 13350 rows, 1552 columns and 118464 nonzeros
Variable types: 1216 continuous, 336 integer (336 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+03]
Objective range [4e+00, 8e+01]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 3e+03]
MIP start produced solution with objective 2812 (1.32s)
MIP start produced solution with objective 2548 (1.37s)
MIP start produced solution with objective 2532 (1.43s)
MIP start produced solution with objective 2488 (2.56s)
MIP start produced solution with objective 2476 (2.61s)
MIP start produced solution with objective 2460 (3.01s)
MIP start produced solution with objective 2456 (3.48s)
MIP start produced solution with objective 2428 (3.50s)
MIP start produced solution with objective 2412 (4.73s)
MIP start produced solution with objective 2360 (4.75s)
Loaded MIP start with objective 2360
Processed MIP start in 4.75 seconds
Presolve removed 8144 rows and 944 columns
Presolve time: 0.80s
Presolved: 5206 rows, 608 columns, 84013 nonzeros
Variable types: 0 continuous, 608 integer (344 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -2.0672000e+04 0.000000e+00 5.182100e+04 6s
3192 2.2800000e+03 0.000000e+00 0.000000e+00 6s
3192 2.2800000e+03 0.000000e+00 0.000000e+00 6s
Root relaxation: objective 2.280000e+03, 3192 iterations, 0.51 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 2280.00000 0 151 2360.00000 2280.00000 3.39% - 7s
0 0 2280.00000 0 128 2360.00000 2280.00000 3.39% - 7s
0 0 2280.00000 0 108 2360.00000 2280.00000 3.39% - 7s
0 0 2280.00000 0 115 2360.00000 2280.00000 3.39% - 8s
0 0 2280.00000 0 125 2360.00000 2280.00000 3.39% - 8s
0 0 2280.00000 0 102 2360.00000 2280.00000 3.39% - 9s
0 0 2280.00000 0 100 2360.00000 2280.00000 3.39% - 9s
0 0 2280.00000 0 116 2360.00000 2280.00000 3.39% - 10s
0 0 2280.00000 0 110 2360.00000 2280.00000 3.39% - 10s
0 0 2280.00000 0 102 2360.00000 2280.00000 3.39% - 10s
0 0 2280.00000 0 100 2360.00000 2280.00000 3.39% - 10s
0 0 2280.00000 0 106 2360.00000 2280.00000 3.39% - 11s
0 0 2280.00000 0 114 2360.00000 2280.00000 3.39% - 11s
0 0 2280.00000 0 72 2360.00000 2280.00000 3.39% - 11s
0 0 2280.00000 0 118 2360.00000 2280.00000 3.39% - 12s
0 0 2280.00000 0 66 2360.00000 2280.00000 3.39% - 12s
0 0 2280.00000 0 66 2360.00000 2280.00000 3.39% - 12s
0 0 2280.00000 0 74 2360.00000 2280.00000 3.39% - 13s
0 0 2280.00000 0 74 2360.00000 2280.00000 3.39% - 13s
0 2 2280.00000 0 74 2360.00000 2280.00000 3.39% - 14s
7 9 2280.00000 3 173 2360.00000 2280.00000 3.39% 107 15s
Cutting planes:
MIR: 22
StrongCG: 2
Zero half: 1
Explored 90 nodes (15462 simplex iterations) in 17.08 seconds
Thread count was 4 (of 4 available processors)
Solution count 9: 2360 2412 2428 ... 2548
Time limit reached
Best objective 2.360000000000e+03, best bound 2.280000000000e+03, gap 3.3898%
- Does "MIP start produced solution with objective 2812 (1.32s)" mean Gurobi considered my start this time? I understand that this start should not guarantee that the incumbent will be initiated with my estimation (2360). But, how come, it starts with my guess this time but not in the previous try?
Sorry for such a long question. But, this will probably clear the confusions for many users.
Thanks in advance!
-
Official comment
This post is more than three 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 why not try our AI Gurobot?. -
Hi Taner,
I guess you are using 8.1.1? If so, from what you explain this seems a bit odd, maybe you can share a minimal example where I can reproduce this? If you can, contact me directly at espinoza at gurobi dot com
Daniel
0 -
Hi, Taner,
Your description is quite clear. I have got the same question as you. I also tried my best to solve this problem. But unfortunately, it did not work.
So have your question been solved? Many thanks for any experience shared.
TAO
0 -
Just out of curiosity, has the problem been finally solved? (I encountered the same message and googling brought me here. However, I don't know if I have the same issue - it may be just mistakes on my input :) )
0 -
@Yauhen, it was all my bad. My solution was not really feasible. I thought it was a feasible solution and was wrong. Thanks to Daniel, I could verify it.
0 -
Thanks, Taner Cokyasar. It seems I might have also a mistaken initial feasible solution. I wonder if there is a way to check the solution I set as start. Ideally, is it possible to see which constraints my provided start solution does NOT satisfy?..
0 -
Okay, I perhaps better post it as a separate question as it might be useful for other users too.
0
Post is closed for comments.
Comments
7 comments