suboptimal
AnsweredHi guys,
I am curious when gurobi says the result is suboptimal before crossover, what does it mean? I know the interior point must be suboptimal, since it is not on vertices. However, does gurobi have some other meaning?
Kindly advise.
Best,
Yanda
-
Hi Yanda,
Please note that a solution does not have to correspond to a vertex to be optimal. A LP either has:
* no solutions (i.e. it is infeasible), or
* 1 unique solution, or
* infinite solutionsAs soon as you find 2 solutions to a LP, you can take a convex combination of these to produce new optimal solutions (which will not be at vertices). In practice, most feasible LPs have infinite solutions and in this case the barrier algorithm tends to find midface solutions - these are non-basic. We can then employ the crossover algorithm to convert the solution to a basic one (i.e. a vertex).
Barrier is not intended to terminate until the appropriate tolerances are satisfied, at which point the solution is optimal (not suboptimal!).
Suboptimal termination indicates that barrier was not able to perform as intended. Accompanying this error should be a primal objective value, and inspecting the barrier log you should find this value in the primal objective column. In the corresponding row I expect you will find a solution where the primal residual is below tolerances but complementarity residuals (and perhaps dual residuals) are not below tolerances.
This typically occurs when the model causes numerical issues in the solve. Consequently, here's some things to try:
* review our Guidelines for Numerical Issues. There is guidance on model building and a section called "Solver Parameters to Manage Numerical Issues" which will give you some parameters to try.
* try tightening the barrier convergence tolerance (BarConvTol)
* heed any warnings that are given in the log- Riley
0 -
Hi Riley,
Thanks for your insightful explanation. I attached the screenshot below. If I understand your meaning correctly, this meaning of suboptimal solution is it is a feasible solution and maybe optimal, but due to the complementary residue or dual residue cannot satisfy tolerance requirement, it is terminated and called suboptimal. Did I misunderstand your meaning?
Kindly advise!
Best,
Yanda
0 -
Hi Yanda,
In your case the best iterate (#94) is neither primal feasible, dual feasible, or satisfies complementarity. Judging from the log it looks like the algorithm is terminated due to dual infeasibility getting worse and worse. At that point it then picks the best iterate, and in this case the best is still not good.
The performance of barrier on your model is quite terrible - we usually hope for a few seconds for a barrier iteration, not 1000! How big is your model, and what are the coefficient ranges like?
Perhaps the following webinar recording will help: Performance Tuning for Gurobi's Barrier Algorithm
- Riley
0 -
Hi Riley,
This case is kind of large. Do you mean even industry size case can converge within 1000s? And why do you think the result is not a feasible solution? I suppose the iteration process of barrier method is implemented within feasible region. If so, then how could I get a infeasible solution during the process?
Best,
Yanda
0 -
Hi Yanda,
This case is kind of large
It's actually not too bad.
Do you mean even industry size case can converge within 1000s?
I'm not sure what industry size means. Some of our commercial customers solve models with just a handful of constraints and variables that take milliseconds to solve. Your solve is stopping after 104 iterations, after close to 100,000, so close to 1000 seconds per iteration. That's not good, especially when the estimation (per your screenshot is 30s per iteration). This is more evidence something is not going well numerically.
why do you think the result is not a feasible solution
The primal residual is 1.18e-03. In a perfect world it would be 0. As a rule of thumb we use a default tolerance of 1e-6, and this is 3 orders of magnitude larger than that.
I suppose the iteration process of barrier method is implemented within feasible region. If so, then how could I get a infeasible solution during the process?
It depends on the implementation of the barrier method. Barrier is often taught with examples where the constraints are inequalities, and then log functions are applied to these inequalities to make sure that iterates are interior to the constraints. Our implementation is more akin to converting LPs to a standard form where all constraints are equalities, and so the log functions are not applied to these constraints, only the bounds, so in this way we are interior to bounds only, and at each iteration we are approximately solving a system which includes the equality constraints. There's finer details in that barrier tuning video.
- Riley
0
Please sign in to leave a comment.
Comments
5 comments