Seeking help: I'm getting infinite loop of the exactly same (non optimal) solution
AnsweredHello,
I'm writing an application that optimizes the represantation of a graph as a grid drawing. Gurobi behaves in a way I can't understand: Often - not always - it ends up in a seemingly infinite loop of the same (non optimal) solution. I'm using a callback function like this:
def mycallback(m, where):
if where == GRB.Callback.MIPSOL:
<check current solution for properties, e.g. line crossings>
if necessary:
m._new_constraints_necessary = True
m.terminate()
env = gp.Env(empty=True)
env.setParam("LogToConsole", 0)
env.setParam("IntFeasTol", 1e-7)
env.start()
m = gp.Model(env=env, name=<name>)
m.Params.LogFile = <path>
m.optimize(mycallback)
while m.status == 11 and m._new_constraints_necessary:
<add some constraints to model>
m.optimize(mycallback)
As I understand it, the callback function should be called, when there is a new solution available. Instead Gurobi seems to not even try to find a new solution. I'll attach part of a logfile. I'd be glad, if someone could point me in the right direction.
Best regards
Thorsten
...
Warning: Completing partial solution with 16677 unfixed non-continuous variables out of 16737
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R21 by 517.000000000
MIP start from previous solve produced solution with objective 6670 (0.34s)
Loaded MIP start from previous solve with objective 6670
Presolve time: 0.05s
Explored 0 nodes (0 simplex iterations) in 0.42 seconds
Thread count was 1 (of 2 available processors)
Solution count 1: 6670
Solve interrupted
Best objective 6.670000000000e+03, best bound -, gap -
User-callback calls 40, time in user-callback 0.04 sec
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64)
Thread count: 2 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 68469 rows, 16896 columns and 215827 nonzeros
Model fingerprint: 0x031ef61a
Variable types: 95 continuous, 16801 integer (16649 binary)
Coefficient statistics:
Matrix range [5e-01, 1e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+04]
RHS range [1e+00, 1e+04]
Warning: Completing partial solution with 16741 unfixed non-continuous variables out of 16801
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R21 by 517.000000000
MIP start from previous solve produced solution with objective 6670 (0.32s)
Loaded MIP start from previous solve with objective 6670
Presolve time: 0.05s
Explored 0 nodes (0 simplex iterations) in 0.41 seconds
Thread count was 1 (of 2 available processors)
Solution count 1: 6670
Solve interrupted
Best objective 6.670000000000e+03, best bound -, gap -
User-callback calls 41, time in user-callback 0.04 sec
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64)
Thread count: 2 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 68733 rows, 16960 columns and 216659 nonzeros
Model fingerprint: 0x72ebeb4f
Variable types: 95 continuous, 16865 integer (16713 binary)
Coefficient statistics:
Matrix range [5e-01, 1e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+04]
RHS range [1e+00, 1e+04]
Warning: Completing partial solution with 16805 unfixed non-continuous variables out of 16865
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R21 by 517.000000000
MIP start from previous solve produced solution with objective 6670 (0.38s)
Loaded MIP start from previous solve with objective 6670
Presolve time: 0.04s
Explored 0 nodes (0 simplex iterations) in 0.46 seconds
Thread count was 1 (of 2 available processors)
Solution count 1: 6670
Solve interrupted
Best objective 6.670000000000e+03, best bound -, gap -
User-callback calls 40, time in user-callback 0.04 sec
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64)
Thread count: 2 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 68997 rows, 17024 columns and 217491 nonzeros
Model fingerprint: 0x354a3595
Variable types: 95 continuous, 16929 integer (16777 binary)
Coefficient statistics:
Matrix range [5e-01, 1e+04]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+04]
RHS range [1e+00, 1e+04]
Warning: Completing partial solution with 16869 unfixed non-continuous variables out of 16929
User MIP start did not produce a new incumbent solution
User MIP start violates constraint R21 by 517.000000000
MIP start from previous solve did not produce a new incumbent solution
Presolve time: 0.06s
Explored 0 nodes (0 simplex iterations) in 0.42 seconds
Thread count was 1 (of 2 available processors)
Solution count 0
Solve interrupted
Best objective -, best bound -, gap -
User-callback calls 27, time in user-callback 0.00 sec
...
-
Official comment
-
Gurobi Staff
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 Thorsten,
In the
while m.status == 11 and m._new_constraints_necessary:
<add some constraints to model>
m.optimize(mycallback)block, are you setting
m._new_constraints_necessary = False
? Otherwise, if this variable is set to \(\texttt{True}\) in the callback of an optimization run, you end up in an infinite loop.
Is the variable \(\texttt{necessary}\) used in the callback set to \(\texttt{False / True}\) in each callback call?
Best regards,
Jaromił0 -
-
Hi Jaromił,
thanks for your quick reply.
The variable is reset inside the callback function before testing for the graph properties.
But shouldn't the callback function be only applied, when there is a new solution available? The variable not reset would then result in termination and restart of the solve for every new solution - necessary or not, but wouldn't explain the output of the same solution over and over again. But maybe I'm wrong with this ...
Best regards,
Thorsten
0 -
-
-
Hi Thorsten,
The block
if where == GRB.Callback.MIPSOL:
[...]is called only if the \(\texttt{where}\) value equals MIPSOL in the callback. However, your callback function \(\texttt{mycallback}\) is called more often than just when \(\texttt{where == MIPSOL}\) to check for possible other callbacks, e.g., MIP, MIPNODE, ... This means that once
m._new_constraints_necessary = True
is set and \(\texttt{necessary = True}\), then Gurobi will terminate every time it check for a possible callback code which is not MIPSOL. You could add a few \(\texttt{print}\) lines to better track the issue.
Best regards,
Jaromił0 -
-
Hi Jaromił,
you're totally right regarding the code snippet I posted. Unfortunately I made a stupid copy and paste mistake. The actual code of my callback function looks like this:
def mycallback(m, where):
if where == GRB.Callback.MIPSOL:
<check current solution for properties, e.g. line crossings>
if necessary:
m._new_constraints_necessary = True
m.terminate()Sorry for wasting your time by such a foolish slip.
Also thank you for pointing out, that not the callback function is called only when there is a new solution, but the conditional block. For the example it should make no difference, but might prevent me from longsome error tracking in the future.
I'll try and play around with printing some status lines anyway.
Thank you and best regards,
Thorsten
0 -
-
-
Hi Thorsten,
Sorry for wasting your time by such a foolish slip
I would not say that it was a foolish slip because I am sure that this conversation helps many others in the Community so thank you for posting.
Best regards,
Jaromił0 -
-
Hello!
Unfortunately, I'm still stuck with this problem.
First I let print out some lines on entering the callback function, on leaving the callback function, before calling the optimize routine and when returning from optimize. I noticed, that often the program didn't even return from the callback. I got printed out the message from the end of the callback function and after that from the beginning of the next callback without anything in between.
I minimized processing during the callbacks and even reduced the callback function to a simple
if where == GRB.Callback.MIPSOL:
m.terminate()and let the processing happen in the function that calls the optimization. This didn't solve the problem and also gave me no hints where to search for the reason.
I double checked everything in my model. I went through some eyample by hand. The only idea I got is that the 'infinite loop' is more likely to accure when the model is smaller.
In the Gurobi logs I read:
MIP start from previous solve produced solution with objective 7489 (0.10s)
Loaded MIP start from previous solve with objective 7489
Presolve time: 0.01s
Explored 0 nodes (0 simplex iterations) in 0.13 seconds
Thread count was 1 (of 2 available processors)
Solution count 1: 7489
Solve interrupted... over and over again. So the previous solution is loaded and without further processing put out as new solution? It sure isn't the optimal solution, it not even satisfies all constraints.
I have absolutely no clue and would be really glad, if anyone could give me a hint.
Best regards
Thorsten
0 -
-
-
I suspect the constraints you add in your cutting plane loop do not necessarily cut off the incumbent solution from the previous solve. Gurobi tries to warm-start the subsequent MIP solve using this incumbent solution. In the log output you posted, the previous solve's incumbent solution is still feasible:
MIP start from previous solve produced solution with objective 7489 (0.10s)
Loaded MIP start from previous solve with objective 7489When Gurobi observes that the previous incumbent solution is feasible, your callback function is called with \( \texttt{where == GRB.Callback.MIPSOL} \). This results in the optimization terminating. After all of this, Gurobi has the exact same solution, and your code will likely add the exact same set of constraints in the future. So the entire process repeats itself.
Can you double-check that the constraints you add are (i) guaranteed to cut off the incumbent solution by an amount greater than the default feasibility tolerance, and (ii) the constraints are implemented correctly? If it's helpful, you can use Model.write() to write out an LP model file, which you can use to visually inspect the newly added constraints for correctness.
0 -
-
Hi Eli,
thanks a lot for your comment.
In fact, preventing my function from terminating the solving and adding the same constraints again, did the trick. I still don't understand, how it is possible to get the same solution again after the first time adding them, although. Unless, of course, there are numerical issues or simple errors, but I din't find any.
The basic idea of that algorithm (not mine) adds all constraints to avoid line crossings preventively. Running that versions I had no problems and for the version with the callback function I use the same routine to add the constraints ...
For now it is working. - Thanks again for your help.
All the best
Thorsten
0 -
Post is closed for comments.
Comments
9 comments