Gurobi reports a bounded model as unbounded
AnsweredHello, everyone
Before showing what I think is a weird output from Gurobi, I’d like thank Gurobi for this amazing tool and, of course, for making it fully available for students.
I’m trying to solve several small LPs in sequence with Gurobi 9.1 and python 3.7. I let all parameters in their default settings, except Threads, which I set to 1, Method, which I also set to 1, and OptimalityTol, which I set to 1e-9.
Regarding the LP models, the differences between them is their objective functions only: the set of constraints and the bounds remain the same. (I’m sure that all models are bounded. For the particular model used in this post, the boundedness can be easily verify by inspection.) Naturally, instead of creating several models, I create a single one and simply change its objective function accordingly. If I understand correctly, once Gurobi solves a model, it stores information regarding the solution found. Such information can be used as warm-start for subsequent solves.
Everything apparently works if I use an optimality tolerance of 1e-6 (OptimalityTol = 1e-6). However, if I change the optimality tolerance to 1e-9, then, when using the solution information from a previous solve, Gurobi reports a bounded model as being unbounded.
I attached the model that Gurobi reports as being unbounded in .lp and .mps formats, respectively, unbounded.lp and unbounded.mps.
Below you can see the log for the model being solved from scratch. The first log is for an optimality tolerance of 1e-6, and, in the second, this parameter is set to 1e-9.
If I try to solve the same model using as warm-start the optimal basis of a problem whose only difference to “unbounded.mps” is its objective function, then Gurobi reports “unbounded.mps” as being unbounded if I set the optimality tolerance to 1e-9. The basis used in this experiment is given in “unboundedBasis.bas”. The results for the optimality tolerances of 1e-6 and 1e-9, respectively, are shown in the following.
All files can be found at https://drive.google.com/drive/folders/1r5-ozO50UZWoRt-6qfvsivPPIy4XG1Ji?usp=sharing
So, am I missing something here or is it really an unexpected behavior from Gurobi?
I appreciate your help,
Bruno
-
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 Bruno,
It is hard to explain it briefly in a community post, thus I will directly point you to the publication explaining what is happening here. While the whole paper is definitely worth a read, you are most likely interested in Section 2.3 of Klotz 2014.
What happens in your case is that the round-off errors of the coefficients and bounds in the MPS file come into play, e.g., the coefficient 2.0215719780000002e-01 should most likely read 2.021571978e-1 or 1.6581263629999998e-01 should rather be 1.658126363e-1. Note that when using the LP file format, you don't observe the behavior you describe, because the LP file format simply cuts off the numerical representation at some fixed decimal. Already these small round-off errors are enough to result in this rather unexpected behavior. You will also observe that if you would use the primal simplex algorithm (Method=0) instead of the dual simplex algorithm (Method=1), the situation you describe does not occur. This is because the optimality tolerance can be seen as the feasibility tolerance of the dual simplex method. Thus, playing with the optimality tolerance affects the feasibility numerics of the dual simplex algorithm.
I hope that the paper and the above explanation help in the understanding of your problem.
Best regards,
Jaromił2 -
-
Hi, Jaromił
That's a great explanation! Thank you. And I'll definitely take a look at that paper.
Thanks,
Bruno
0 -
Post is closed for comments.
Comments
3 comments