My dual solution is unbounded even when primal bounded and giving optimal solution.
AnsweredI am trying to apply benders decomposition to the problem, but when I add optimality cut to my master problem, after a few iterations, my lower bound exceeds the upper bound. To check i am applying correct optimality cut, i have made dual of my sub problem and trying to solve it, but my dual is giving unbounded solution even when my primal sub problem is feasible and giving optimal solution. Furthermore, when I use gurobi "InfUnbdInfo=1" the solution i am getting from dual is not equal to primal sub problem. Please help!
-
-
Gurobi Staff
Hi Ashish,
There's a few ways to implement the subproblem. Are you currently using a primal form then either using the Pi attribute or FarkasDual? Have you converted variable bounds to simple constraints before attempting the decomposition?
You can write the dual of a LP out using the "write" function of whichever API you are using and using the file extension .dlp. This may help you understand where you are going wrong. You could also try taking the dual values corresponding to your optimal solution in the primal LP, and fix the variables in your dual LP appropriately using lower and upper bounds. The result may help you debug further (especially if the result is infeasible).
- Riley
0 -
-
Dear Riley,
Thank you for your prompt reply. I did not know I could generate the .dlp dual of primal through the command "write." I tried this feature and am now getting the correct result after correcting my dual formulation. But still, I have a few questions:
1. In the .dlp file I get variables like C1, C2 , C3, etc. but I also observed C2(120) or C6 (20). What is the meaning of value inside the bracket?
2. Why is this important "Have you converted variable bounds to simple constraints before attempting the decomposition" ? Do you have any references where I can understand this?
3. Currently, I am formulating dual to get the feasibility cut using "InfUnbdInfo=1" and "getAttr("unbdray", variable name)", but I got to know that I can use primal of the subproblem to get "FarkaDual" by keeping "InfUnbdInfo=1". But when I am doing this, either I am not using "FarkasDual" correctly, or something is missing because my master problem is not updating in any of the iterations.
0 -
-
-
Hi Ashish,
In the .dlp file I get variables like C1, C2 , C3, etc. but I also observed C2(120) or C6 (20). What is the meaning of value inside the bracket?
It is the number of variables in the corresponding constraint.
Why is this important "Have you converted variable bounds to simple constraints before attempting the decomposition" ?
This really depends on whether your subproblem is in primal form or dual form. If you use the dual form then you'll need to introduce dual variables for each non-zero bound. If you use the primal form, and move the non-zero bounds to constraints then each bound will be associated with a dual variable. If you keep them as bounds then you'll need to use the reduced cost in place of those dual variables - however it gets complicated when the primal is infeasible, as I don't think the reduced costs are valid. So in my mind it is easier to just convert the primal to standard form where the only bounds are zero, and everything else is a constraint.
Currently, I am formulating dual to get the feasibility cut using "InfUnbdInfo=1" and "getAttr("unbdray", variable name)", but I got to know that I can use primal of the subproblem to get "FarkaDual" by keeping "InfUnbdInfo=1". But when I am doing this, either I am not using "FarkasDual" correctly, or something is missing because my master problem is not updating in any of the iterations.
I would try converting non-zero bounds to constraints and see if it is still incorrect.
- Riley
0 -
-
Dear Riley,
Thank you very much for all the input. I have one question regarding bender decomposition: when I apply the feasibility cuts to the master problem for small problems, it works fine. But for large-scale, feasibility cuts take many iterations to make the subproblem feasible. What could be the reason?
0 -
-
-
Hi Ashish,
Unfortunately a standard Benders implementation just typically doesn't work that well without various problem specific improvements to the algorithms - especially if there is only a single subproblem as opposed to many which can be solved in parallel. This is why we don't have an automatic Benders approach in Gurobi.
If you're interested in diving deeper into what sort of enhancements are required then see this talk from "Bender's Day" by Stephen Maher: https://youtu.be/vVuNsx1bfLA?si=lOUM6IY5HlFqYPbH
- Riley
0 -
-
Hi Riley,
Thank you for sharing this insight and the link to Stephen Maher’s talk from Benders Day. I appreciate the explanation on the challenges of a standard Benders implementation, especially with a single subproblem.
Best regards,
Ashish0 -
Please sign in to leave a comment.
Comments
6 comments