Callback on MIPNODE is late or slow
Answered
Dear community,
I am working on solving a large MIP with user callbacks. In one of the callbacks, I query
if where == GRB.Callback.MIPNODE:
and then add heuristic solutions via
model.cbSetSolution(model._x, sol_x)
model.cbUseSolution()
to the solver with an initial feasible solution.
To my understanding, the solution should then be added/checked in the root node, once the LP relaxation is solved.
However, from the log file, I can see that this is fact does not happen and the MIPNODE callback is only called later and after I already have incumbent solutions. This somewhat defeats the purpose for the larger problems I want to solve.
Is there a way I can force the solver to apply the callback at the earliest possible time?
I tried to additionally check for the root via the following, but the behavior did not change.
if model.cbGet(GRB.Callback.MIPNODE_NODCNT) == 0:
Below is an exemplary logfile of a small test instance.
Any hints or help would be greatly appreciated!
Changed value of parameter LazyConstraints to 1
Prev: 0 Min: 0 Max: 1 Default: 0
Parameter OutputFlag unchanged
Value: 1 Min: 0 Max: 1 Default: 1
Changed value of parameter MIPGap to 0.01
Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
Changed value of parameter Presolve to 2
Prev: -1 Min: -1 Max: 2 Default: -1
Changed value of parameter TimeLimit to 86400.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (win64)
Optimize a model with 2241 rows, 3854 columns and 16425 nonzeros
Model fingerprint: 0x7777c421
Variable types: 8 continuous, 3846 integer (3846 binary)
Coefficient statistics:
Matrix range [1e+00, 4e+01]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
Presolve removed 2223 rows and 2223 columns
Presolve time: 0.22s
Presolved: 18 rows, 1631 columns, 8949 nonzeros
Variable types: 8 continuous, 1623 integer (1623 binary)
Presolved: 26 rows, 1631 columns, 10516 nonzeros
Root relaxation: objective 6.140457e-02, 44 iterations, 0.01 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.06140 0 11 - 0.06140 - - 3s
H 0 0 412.0601887 0.06140 100% - 8s
H 0 0 241.7279406 0.06140 100% - 13s
H 0 0 209.5648939 0.06140 100% - 24s
INSERTING HEURISTIC SOLUTION NOW
0 0 50.14156 0 26 209.56489 50.14156 76.1% - 29s
0 0 60.14010 0 29 209.56489 60.14010 71.3% - 29s
0 0 60.98010 0 30 209.56489 60.98010 70.9% - 29s
0 0 70.61015 0 34 209.56489 70.61015 66.3% - 29s
0 0 73.34117 0 39 209.56489 73.34117 65.0% - 29s
0 0 73.36760 0 39 209.56489 73.36760 65.0% - 29s
0 0 82.92854 0 41 209.56489 82.92854 60.4% - 29s
0 0 83.93797 0 27 209.56489 83.93797 59.9% - 29s
0 0 83.94010 0 28 209.56489 83.94010 59.9% - 29s
0 0 87.33516 0 41 209.56489 87.33516 58.3% - 29s
0 0 87.33516 0 41 209.56489 87.33516 58.3% - 38s
0 0 87.33516 0 41 209.56489 87.33516 58.3% - 41s
H 0 0 146.6467143 87.33516 40.4% - 43s
0 0 97.20303 0 44 146.64671 97.20303 33.7% - 43s
0 0 97.71503 0 44 146.64671 97.71503 33.4% - 43s
0 0 97.74272 0 43 146.64671 97.74272 33.3% - 43s
0 0 101.72330 0 54 146.64671 101.72330 30.6% - 43s
0 0 103.08055 0 54 146.64671 103.08055 29.7% - 44s
0 0 103.42627 0 57 146.64671 103.42627 29.5% - 44s
0 0 105.46411 0 62 146.64671 105.46411 28.1% - 44s
0 0 105.46411 0 62 146.64671 105.46411 28.1% - 44s
0 0 106.48970 0 14 146.64671 106.48970 27.4% - 45s
0 0 111.93811 0 19 146.64671 111.93811 23.7% - 49s
0 0 119.77311 0 6 146.64671 119.77311 18.3% - 49s
0 0 133.95679 0 7 146.64671 133.95679 8.65% - 49s
0 0 139.81468 0 12 146.64671 139.81468 4.66% - 53s
0 0 144.46861 0 12 146.64671 144.46861 1.49% - 53s
0 0 cutoff 0 146.64671 146.64671 0.00% - 53s
Cutting planes:
Cover: 3
Implied bound: 1
Clique: 4
MIR: 3
GUB cover: 10
Relax-and-lift: 1
Lazy constraints: 4
Explored 1 nodes (1281 simplex iterations) in 53.53 seconds
Thread count was 16 (of 4 available processors)
Solution count 4: 146.647 209.565 241.728 412.06
Optimal solution found (tolerance 1.00e-02)
Best objective 1.466467142864e+02, best bound 1.466467142864e+02, gap 0.0000%
User-callback calls 405, time in user-callback 50.97 sec
-
Hi Mike,
The MIPNODE callback is called after the MIPSOL callback which means that if any heuristic solutions are found before the first cutting plane phase, then they will be reported before you can feed your heuristic solution to Gurobi. If you know your solution beforehand, i.e., you don't have to access information from the MIPNODE callback to construct it, you should provide your solution to Gurobi as an initial point (see also How do I use MIP starts?).
Best regards,
Jaromił0 -
Hi Jaromil,
thank you for the clarification on the MIPNODE callback. I was under the impression that it should be called earlier, I also understood that in the recent webinar on heuristics (callback example for the greedy heuristic, around 39mins into the video): https://www.gurobi.com/resource/faster-mips-using-custom-heuristics/?mkt_tok=MTgxLVpZUy0wMDUAAAF_9MZZ03YL72LHfzobyi7aWxLdlE-fWDlDABd184kd9mDDDZXCWEn1MQwyfIboCHISVs0498ukHG7HTGWepCbj2I0mwdwIJDoSaC-pjg5k8A
I face another issue with using MIP starts (which is why I tried the callback) as my procedure uses lazy constraints. I believe this older post of yours refers to the difficulty of that combination.
https://support.gurobi.com/hc/en-us/community/posts/360073235912/comments/360015464812
If I understand your post correctly, I should only add those lazy constraints that are sure to cut off the MIP start solution? In other words - my starting solution should be such that it is cut off by the lazy constraint(s) in the callback routine? Or is the other way around and it should NOT be cut off?
Alternatively, is there another way to inject known solutions as a means to fastly provide an incumbent to a MIP that otherwise has difficulties finding the first integer solution?
Thank you for your support!
Best regards,
Mike
0 -
Hi Mike,
I was under the impression that it should be called earlier, I also understood that in the recent webinar on heuristics
Please note that in Greg's code and in the webinar, he mentions multiple times that a feasible solution is needed first to apply his TSP heuristics. This makes even more sense then the MIPNODE callback which uses a feasible point and injects a possibly better solution point is called after the MIPSOL callback.
In other words - my starting solution should be such that it is cut off by the lazy constraint(s) in the callback routine?
Yes, correct.
Alternatively, is there another way to inject known solutions as a means to fastly provide an incumbent to a MIP that otherwise has difficulties finding the first integer solution?
If the number of lazy constraints is not too high, i.e., you don't have exponentially many lazy constraints in worst case, then adding them as normal constraints may work well. It might even make sense if the number of lazy constraints equals (or is larger than) the number of your normal constraints. In some cases this may even speed up the optimization process, because more information is present in the model.
Alternatively, you can use variable hints if you think that the initial point you provide is close to the optimal one. Your certainty can be set via the hint priority attribute.
Best regards,
Jaromił0 -
Hi Jaromil,
thanks a lot for the clarification.
The number of lazy constraints, unfortunately, exceeds the number of my normal constraints significantly. Following your suggestion, I would like to add them as normal constraints via cbCut only when the starting solution is evaluated and then continue to add lazy constraints. Is there a way to query the status of the optimization when a callback is initiated so that it tells me when the MIP start has been evaluated?
Thank you for your support!
Best regards
Mike
0 -
Hi Mike,
Is there a way to query the status of the optimization when a callback is initiated so that it tells me when the MIP start has been evaluated?
This is currently not possible.
You could try adding your MIP start in a MIPNODE callback in the root node. To check whether you are in the root node, you can check whether the value of MIPNODE_NODCNT equals 0.
Best regards,
Jaromił0 -
Hi Jaromil,
apologies for the late reply, the workarounds did not work in my case. Therefore it would be great if the abvove-mentioned issue with using lazy constraints and MIP starts would be fixed in Gurobi 9.5 and one more reason for me to upgrade. Can you say if that is the case?
Thank you and best regards
Mike
0 -
Hi Mike,
This behavior did not change in v9.5.0.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
7 comments