Trouble with the Non-Integer Solution of Gurobi MIP-Optimizer
Answered
Hi
I've implemented a benders decomposition and now I'm comparing its solution to the one of Gurobi. All integer variables of the model are binary.
It seems that only if the input data is well designed that make Gurobi return a integer solution, the results of both methods will be the same. Otherwise Gurobi will return a non-integer solution, while it takes benders decomposition far more time to solve and as result, one more binary variable of the benders decomposition will be set to 1, as the rest of the solution are the same, thus the objective value of two methods are different.
I've tried setting the parameter IntegralityFocus to 1 but it only rounds the non-integer value. In addition, the master problem always returns an integer solution due to its smaller scale so I cannot get the same non-integer solution as which of Gurobi.
I'm quite sure that the benders decomposition is implemented properly, otherwise it will never show the same result as Gurobi.
I need your advice to fix this issue. Thank you in advance!
Best regards
Zheren
-
Hi Zheren,
Based on your post it is hard to get a complete picture of your setup.
I guess you have a complete model with binary variables that you solve with Gurobi.
Additionally, you decompose the model based on Benders and you implemented a branch-and-cut algorithm in Gurobi dynamically adding feasibility and/or optimality cuts via callbacks. Is this correct?By theory, if you did the decomposition correctly both approaches should give the same optimal value but potentially lead to a different solution (if there are multiple optimal solutions). If you define your variables in both approaches to be binary, then the solution values should also be binary. Did you do that?
If you get fractional values for your binary variables in the final solution, by how much do they deviate from an integral value? Note that due to limited machine precision, the solution value might deviate by IntFeasTol (1e-5 by default).
One additional comment: The fact that you obtain the correct result for some but not all instances does not imply that your two approaches are equivalent and correct. Implementing Benders decomposition is far from being trivial, there are a lot of potential issues that could come up, often based on numerics and tolerances when adding cuts in a callback.
Best regards,
Mario0 -
Hi Mario
You have a proper concept of my setup despite my unclear discription.
What I should have mentioned is that the subproblems of my model are always feasible and there are no multiple optimal solutions. In addition, the objective also contains continuous variables (operation costs) so only the decision variables (investment decision) are set to binary.
The IntFeasTol is of both approaches are set to default, but only the solution of Gurobi returns the deviating solution. Moreover, some binary variables which are expected as 0 deviate by 3e-6 of 4e-6
As adding the benders cuts, I've only set the LazyConstraint to 1 so that I can add the benders cuts via cbLazy().
I hope these information can help you getting a better picture of my setup.
Best regards
Zheren
0 -
Hi Zheren,
If I understood your last post correctly, then your solution values of binary variables only deviate by a value less than 1e-5. If this is correct, then this is expected behavior. You can round those values to the nearest integer to obtain the actual solution values.
If the optimal objective values of your two approaches are significantly different (by more than a small epsilon), then there is a mistake somewhere, either in the complete model handed over to Gurobi, or in the Benders approach.
Are both solutions feasible for your problem?0 -
Hi Mario
Both solutions are feasible. In the solution of Gurobi, the decision variables do deviate by a value less than 1e-5, while the objective value of two approaches are significantly different. More specificaly, the objective value of benders decomposition approach is worse (bigger in case of a minimization problem) than which of Gurobi, that means the constraints of the Benders approach are tighter.
If I set the IntegralityFocus of the complete model to 1, the objective value handled by Gurobi will become the one of Benders approach, but there is one more of the desicion variables in benders set to 1 as in Benders approach and the solutions of all the other continuous variable of two approach are different. The IntegralityFocus doesn't affect the solution of Benders approach, as the master problem always returns an integer solution.
In addition, I've noticed that the slack of the benders cuts usually have a negative value, which may cause the benders approach has one more of the binary variables set to 1 and thus the numerical instability. I can only avoid it by relaxing the integrality constriants in the master problem. Only if I do so, the rounded integer solution will be the same, and the objective value of Benders approach will be much better. However, the difference between the objective values of two approch is about 0.5 which is still significant.
0 -
Hi Zheren,
If both solutions are feasible for your problem, and the solution from the complete model solved by Gurobi is clean (no significant violations) and better then I would say that your Benders cuts are too restrictive.
Are you saying that you solve the same complete model with Gurobi (without adding cuts in callbacks), once with IntegralityFocus=0 (default) and once with IntegralityFocus=1, and you get two significantly different optimal objective values?
How do you derive the slack of constraints? Do you manually compute it or do you query the Slack attribute of linear constraints? In the latter case, you have to be careful since negative slacks do not automatically mean violations. This can be checked in the following way (in Python):
for c in model.getConstrs(): if ( (c.Sense == GRB.EQUAL and c.Slack != 0.0) or (c.Sense == GRB.LESS_EQUAL and c.Slack < 0.0) or (c.Sense == GRB.GREATER_EQUAL and c.Slack > 0.0) ): print(model.getRow(c), c.Sense, c.RHS, "violated by", abs(c.Slack))
0 -
Apart from that, your model seems numerically quite challenging. You could try to set parameter NumericFocus=1 (or 2 or even 3).
0 -
Hi Mario
I do get two significantly different optimal objective values after setting IntegralityFocus = 1, while the worse one is as same as the solution of the Benders approach.
Since the sense of my Benders Cuts is always greater equal, a Benders cut with negative slacks are not violated in this case. Thank you for the tipp.
After setting NumericFocus = 1, which is quite adequate for my model, the objective value of the complete model is not changed, while all the non-integer solutions (as NumericFocus = 0) are rounded.
Like IntegralityFocus, NumericFocus doesn't affect the solution of Benders approach, neither.
It seems like the problem is restricted to the Benders cuts which result in the worse objective value of the subproblem in the next iteration . However, I have no idea how to fix this issue since all of them are not violated and I don't know any other way to relax them except removing the integrality constraints, which make no cuts are added by the callback function and thus not a proper way.
0 -
Hi Zheren,
Would you be willing to share the complete model such that we can reproduce the difference with IntegralityFocus=0 vs. 1 on our side? If yes, please create a support request (and refer to me) and upload your model here?
To find out which of your cuts are too restrictive, here are a few tips:
- Take the better solution from your complete model solve, and compare it to the added cuts in your Benders approach. There should be at least one cut that is violated by the full-model solution. Maybe this gives you a hint.
- Many cut issues are based on numerics, i.e., when using the current solution values in your Benders subproblem make sure that you consider some tolerance for EACH variable value, e.g., 1e-6 or even a higher value.
- Reduce your problem instance to the smallest size where the issue still appears. Then, you can do manual debugging more easily.
- Make sure that your Benders subproblem is defined correctly. Don't forget variable bounds when creating your dual problem!
0 -
Hi Mario
I've uploaded the complete model and the Benders approach, which could be necessary, via the link you provide.
I will work on the modification of the Benders cut using your tipps. Thank you very much!
0 -
Thanks, I got the files! We will continue the discussion in the ticket.
0
Please sign in to leave a comment.
Comments
10 comments