Is it possible to change when (the gap %level) Gurobi starts focusing on finding feasible solutions instead finding a lower lower bound?
AnsweredI am trying to solve a nonconvex MIQP. I see that I was very close to the final solution within about 3000 seconds but gurobi still kept on focusing on finding a lower lower bound instead of trying to improve the incumbent solution.
Ultimately, the whole process took more than 11 hours. Is it possible to somehow manually decide the gap % at which gurobi tries to find a feasible solution instead of finding a lower lower bound. Would MIPFocus =1 help? Is there any other manual way?
A snippet of the log file (notice how at 3000s, I am within 1000 Euros (0.2% gap) of the final solution ):
Nodes| Curr| Node|Obj Bnd| Wrk Exp Unexp | Obj Dep IInf | Incum BestBd Gap | It/Nd Time
20036 8446 cutoff 33 -410759.81 -417835.00 1.72% 288 3008s
20802 8689 -416649.09 69 78 -410759.81 -417809.70 1.72% 288 3109s
21588 9025 -416421.74 43 106 -410759.81 -417794.02 1.71% 291 3237s
22451 9025 -416632.85 114 - -410759.81 -417786.42 1.71% 292 3542s
22600 9553 -411437.40 44 150 -410759.81 -417774.68 1.71% 293 3675s
22905 9553 -416748.81 148 - -410759.81 -417773.97 1.71% 292 3970s
23867 9815 cutoff 55 -410759.81 -417753.30 1.70% 293 4100s
24808 10133 infeasible 53 -410759.81 -417737.38 1.70% 295 4246s
25845 10650 -416324.90 62 129 -410759.81 -417721.82 1.69% 295 4405s
27076 11155 cutoff 47 -410759.81 -417707.11 1.69% 294 4561s
28436 11585 -414786.73 59 135 -410759.81 -417687.84 1.69% 294 4740s
29814 11949 infeasible 48 -410759.81 -417667.88 1.68% 294 4911s
30994 12484 cutoff 50 -410759.81 -417654.59 1.68% 295 5097s
32359 13548 cutoff 48 -410759.81 -417649.35 1.68% 296 5280s
32677 13548 -416799.85 98 - -410759.81 -417639.32 1.67% 298 5572s
33892 13555 -416239.17 150 - -410759.81 -417616.92 1.67% 295 5868s
34504 14110 infeasible 37 -410759.81 -417615.13 1.67% 290 6058s
36094 14501 cutoff 32 -410759.81 -417608.95 1.67% 292 6297s
37418 15047 -416843.94 35 196 -410759.81 -417586.12 1.66% 294 6522s
38896 15550 -415152.00 55 141 -410759.81 -417571.81 1.66% 295 6736s
40613 16335 -415886.33 54 121 -410759.81 -417562.14 1.66% 295 7002s
41105 16335 -416809.40 96 - -410759.81 -417559.37 1.66% 294 7317s
42668 16968 -415986.84 53 137 -410759.81 -417536.06 1.65% 293 7540s
44257 17435 cutoff 49 -410759.81 -417523.93 1.65% 293 7806s
45647 17986 -416748.20 58 128 -410759.81 -417515.42 1.64% 296 8120s
47350 18475 -417142.71 42 178 -410759.81 -417498.77 1.64% 295 8445s
49178 19087 -417135.75 47 118 -410759.81 -417482.95 1.64% 295 8749s
50645 19087 cutoff 50 -410759.81 -417480.58 1.64% 294 8750s
51269 19747 -415750.73 41 152 -410759.81 -417470.18 1.63% 294 9072s
H52303 19747 -410759.8052 -417468.04 1.63% 295 9072s
53286 20271 -417367.81 45 154 -410759.81 -417461.35 1.63% 294 9351s
54992 20580 -416833.64 49 126 -410759.81 -417450.04 1.63% 295 9663s
56280 20910 -417169.02 60 105 -410759.81 -417437.45 1.63% 298 9988s
57829 21202 -416608.13 49 147 -410759.81 -417423.09 1.62% 300 10322s
59185 21562 -416546.90 51 101 -410759.81 -417411.87 1.62% 301 10716s
60664 21840 cutoff 41 -410759.81 -417404.33 1.62% 303 11073s
62288 22687 infeasible 64 -410759.81 -417389.02 1.61% 306 11465s
63449 22687 -416646.13 83 - -410759.81 -417386.73 1.61% 305 11771s
63455 22689 -416660.46 86 - -410759.81 -417386.73 1.61% 305 12074s
64543 23147 -416502.16 66 120 -410759.81 -417375.07 1.61% 305 12459s
66435 23636 -416883.10 57 113 -410759.81 -417362.80 1.61% 306 12814s
66787 23636 -415165.87 46 169 -410759.81 -417362.20 1.61% 306 12815s
68112 23956 -416773.43 47 142 -410759.81 -417358.75 1.61% 308 13545s
69518 24838 -416062.08 55 143 -410759.81 -417349.96 1.60% 310 14028s
72377 25546 -417141.38 69 105 -410759.81 -417334.20 1.60% 310 14474s
74540 25546 -416550.46 91 - -410759.81 -417326.91 1.60% 310 14800s
74735 26397 infeasible 64 -410759.81 -417326.91 1.60% 309 15257s
76832 26397 -417182.88 46 55 -410759.81 -417320.41 1.60% 309 15570s
77324 27034 cutoff 52 -410759.81 -417308.63 1.59% 309 15921s
77518 27034 -416609.73 87 - -410759.81 -417308.23 1.59% 309 16234s
79323 27773 cutoff 69 -410759.81 -417302.98 1.59% 309 16683s
81993 28454 cutoff 41 -410759.81 -417294.10 1.59% 307 17083s
84024 29244 cutoff 50 -410759.81 -417283.22 1.59% 307 17543s
85985 29308 -417162.81 53 36 -410759.81 -417281.14 1.59% 306 17861s
86665 30008 cutoff 57 -410759.81 -417272.10 1.59% 306 18221s
88524 30008 -416260.06 130 - -410759.81 -417264.52 1.58% 306 18538s
88992 30509 -416385.98 47 138 -410759.81 -417264.28 1.58% 305 18950s
91015 31069 -415155.39 53 137 -410759.81 -417259.21 1.58% 304 19362s
92393 31071 -416613.35 111 - -410759.81 -417255.12 1.58% 304 19684s
93031 31445 -417227.79 64 89 -410759.81 -417250.40 1.58% 304 20087s
94558 31445 -417176.45 52 48 -410759.81 -417246.51 1.58% 304 20408s
94730 32184 -415723.41 51 129 -410759.81 -417241.76 1.58% 304 20835s
94812 32184 -416595.59 93 - -410759.81 -417241.76 1.58% 304 21145s
94813 32185 -416609.74 94 - -410759.81 -417241.76 1.58% 304 21452s
97037 32619 cutoff 55 -410759.81 -417234.13 1.58% 303 21890s
97286 32619 -416561.12 81 - -410759.81 -417233.53 1.58% 303 22196s
99006 32922 infeasible 50 -410759.81 -417224.01 1.57% 303 22595s
100840 33384 -416524.73 54 109 -410759.81 -417214.00 1.57% 303 23008s
101598 33384 -412989.27 96 - -410759.81 -417211.53 1.57% 304 23317s
102812 33871 cutoff 57 -410759.81 -417208.85 1.57% 304 23730s
103660 33871 -416513.79 76 - -410759.81 -417206.03 1.57% 303 24028s
105167 34202 cutoff 68 -410759.81 -417201.91 1.57% 303 24420s
107126 34358 -416430.22 64 106 -410759.81 -417182.18 1.56% 304 24773s
108928 34767 -416571.90 62 107 -410759.81 -417175.61 1.56% 304 25269s
111016 35030 infeasible 64 -410759.81 -417160.16 1.56% 304 25674s
112910 35366 cutoff 60 -410759.81 -417146.81 1.55% 305 26085s
115176 35741 -416459.76 54 104 -410759.81 -417134.53 1.55% 305 26519s
115400 35741 -416682.31 83 - -410759.81 -417134.53 1.55% 305 26824s
117174 36209 cutoff 120 -410759.81 -417127.36 1.55% 305 27227s
119142 36500 cutoff 72 -410759.81 -417119.05 1.55% 305 27672s
121043 36900 -414720.15 50 149 -410759.81 -417103.90 1.54% 305 28212s
122907 37111 -416961.25 57 148 -410759.81 -417100.89 1.54% 306 28608s
124270 37111 -414815.45 78 - -410759.81 -417100.89 1.54% 306 28978s
124583 37947 cutoff 58 -410759.81 -417096.22 1.54% 306 29540s
126154 37947 -416607.75 80 47 -410759.81 -417088.70 1.54% 306 29872s
126866 38060 -416510.12 71 33 -410759.81 -417088.29 1.54% 305 30199s
127362 38570 -416283.92 57 115 -410759.81 -417075.14 1.54% 305 30681s
127972 38570 -416606.46 91 - -410759.81 -417074.37 1.54% 305 31043s
129271 39195 -416734.81 59 121 -410759.81 -417071.84 1.54% 305 31579s
130180 39195 -416682.31 100 - -410759.81 -417070.54 1.54% 306 31931s
130190 39196 -416624.35 104 - -410759.81 -417070.54 1.54% 306 32288s
131979 39668 -416050.49 48 126 -410759.81 -417062.57 1.53% 304 33064s
133610 40131 -416518.73 58 116 -410759.81 -417058.02 1.53% 305 33621s
*134838 20696 94 -416609.7313 -417051.91 0.11% 306 33973s
134841 20696 -416609.93 95 - -416609.73 -417051.91 0.11% 306 34310s
135691 20220 -416889.64 52 105 -416609.73 -417042.47 0.10% 305 34712s
136315 20220 -416691.52 86 - -416609.73 -417041.79 0.10% 305 35023s
136490 20228 -416615.41 91 - -416609.73 -417041.79 0.10% 305 35329s
136500 20229 -416692.81 92 - -416609.73 -417041.79 0.10% 305 35644s
*136713 16124 122 -416679.5483 -417041.79 0.09% 304 35955s
139910 15373 -416860.16 60 108 -416679.55 -417025.01 0.08% 300 36555s
140401 15373 -416696.65 166 2 -416679.55 -417024.21 0.08% 300 36870s
*140479 14090 204 -416696.6460 -417024.21 0.08% 300 36870s
*142424 11814 91 -416739.0497 -417015.73 0.07% 298 37235s
142701 11853 -416919.91 55 118 -416739.05 -417015.41 0.07% 298 37547s
*142800 11853 80 -416739.0498 -417015.41 0.07% 297 37846s
*145040 8097 75 -416809.3696 -417013.45 0.05% 295 38470s
*145052 8095 81 -416809.3727 -417013.45 0.05% 295 38786s
146904 6835 cutoff 72 -416809.37 -416994.82 0.04% 292 38929s
*148680 6833 74 -416809.3795 -416964.04 0.04% 290 39241s
*148721 6830 104 -416809.3874 -416964.04 0.04% 290 39567s
*148752 6822 92 -416809.3979 -416964.04 0.04% 290 39889s
*149218 6822 109 -416809.3979 -416964.04 0.04% 289 39889s
149474 5806 cutoff 52 -416809.40 -416964.04 0.04% 288 40094s
151091 4906 infeasible 55 -416809.40 -416956.75 0.04% 287 40224s
152910 3869 cutoff 57 -416809.40 -416940.27 0.03% 285 40324s
154671 2852 cutoff 54 -416809.40 -416907.06 0.02% 283 40453s
156589 1657 cutoff 76 -416809.40 -416890.80 0.02% 281 40552s
158237 230 cutoff 68 -416809.40 -416882.22 0.02% 280 40616s
Cutting planes:
Learned: 34
Gomory: 10
Cover: 375
Implied bound: 392
Projected implied bound: 12
Clique: 6
MIR: 897
StrongCG: 3
Flow cover: 2147
Inf proof: 17
Zero half: 1
RLT: 1145
Relax-and-lift: 123
Explored 160001 nodes (44322318 simplex iterations) in 40618.00 seconds (22229.78 work units)
Thread count was 12 (of 12 available processors)
Solution count 10: -416809 -416809 -416809 ... -416680
-
Hi Gaurav,
The parameter ImproveStartGap allows you to specify a gap at which the solver switches to a strategy that will focus on finding better feasible solutions.
A manual approach will be to stop the solve at your desired gap, change parameters to focus on finding feasible solutions and start the solve again. The parameters that generally help with finding feasible solutions are MIPFocus(=1), NoRelHeurTime, and Heuristics.
Best regards,
Simran0 -
Hello Simran,
Thanks for your reply!
If I set the parameter ImproveStartGap = 0.5, then would it completely give up on moving the best bound?
I would instead prefer that after a certain gap, the solver alternates between strategies of improving the feasible solution and that of improving the lower bound.
If it completely gives up of moving the lower bound, then wouldn't it lead to cases where the problem is never solved as even at the optimal there is some gap left?
Regards
Gaurav0 -
Hi Gaurav,
With ImproveStartGap = 0.5, after the solver reaches a mip gap of 50%, it will give up on bound improvement and focus entirely on finding feasible solutions.
I would instead prefer that after a certain gap, the solver alternates between strategies of improving the feasible solution and that of improving the lower bound.
To do this, you can change the relevant parameters in the MIP callback. For example, the script below starts solving the glass4.mps instance (distributed with the Gurobi software) with default settings, terminates optimization in the callback as soon as it reaches the mip gap of 50%, sets MipFocus=1 to focus on finding feasible solutions, continues optimization for the next 5 seconds, terminates the optimization again in the callback, sets MipFocus=2 to focus on improving bound, and continues optimization again.
import gurobipy as gp
from gurobipy import GRB
def my_callback(model, where):
if where == GRB.Callback.MIP:
run_time = model.cbGet(GRB.Callback.RUNTIME)
objbst = model.cbGet(GRB.Callback.MIP_OBJBST)
objbnd = model.cbGet(GRB.Callback.MIP_OBJBND)
if abs(objbst - objbnd) < change_gap * (1.0 + abs(objbst)) and check_gap:
m._changeParam_focusSol = True
model.terminate()
if run_time > change_time and check_time:
model._changeParam_focusBound = True
model.terminate()
change_gap=0.5
change_time=5
check_gap = True
check_time = False
m = gp.read('glass4.mps')
m._changeParam_focusSol = False
m._changeParam_focusBound = False
m.optimize(my_callback)
if m._changeParam_focusSol:
m.params.MIPFocus = 1
check_gap = False
check_time = True
m.optimize(my_callback)
if m._changeParam_focusBound:
m.params.MIPFocus=2
m.optimize()If it completely gives up of moving the lower bound, then wouldn't it lead to cases where the problem is never solved as even at the optimal there is some gap left?
Yes, you are correct; the solver may not terminate if the gap cannot be reduced to the MIPGap parameter value by only finding feasible solutions (for example, when the optimal solution is found in the improvement phase but the gap is still high due to a weak bound), and there are no other terminating criteria.
Best regards,
Simran0 -
Thanks Simran!
This looks like exactly what I needed. I will test it and get back to you. One question though:
I think (please confirm) that when m.optimize() is called for the second and then for the 3rd time, it actually continues the same optimization routine and doesn't start optimizing from the beginning.Regards
Gaurav
0 -
Yes, the solver will continue the same optimization run with updated parameters in the second and third optimize() call.
0 -
Dear Simranjit Kaur,
one question regarding your answer above. If I call
model.cbGet(GRB.Callback.MIP_OBJBND)
within
if where == GRB.Callback.MIP:
I get a File "src/gurobipy/model.pxi", line 6468, in gurobipy.Model.cbGet
gurobipy.GurobiError: Callback error
Exception ignored in: 'gurobipy.callbackstub' error.This does not happen, however, if I call the same cbGet function within
if where == GRB.Callback.MIPSOL:
Any clue?
In particular, I have the problem that the solver doesn't callback with MIPSOL when only the dual bound changes. So I cannot react when only the dual bound changes but not the primal bound, since I cannot retrieve the dual value (OBJBND) from the model in those cases.
0 -
Hi Johannes,
Querying the best objective bound with model.cbGet(GRB.Callback.MIP_OBJBND) in a MIP callback should work. Please see the section on Callback codes in our reference manual.
Could you please share a minimal reproducible example that reproduces the callback error with us? Thanks!
Best regards,
Simran0
Please sign in to leave a comment.
Comments
7 comments