Pinned topic Benders decomposition and primal degenerate basis
We have a MIP which couldn't be solved in reasonable time frame. So we have decomposed that MIP using Benders. But our LP subproblems have degenerate optimal basis. However, the dual solution is unique. Our formulation requires us to use the primal solution combined with dual solution to generate cuts. So this means sometimes the point cuts that are generated leads to suboptimal solution. For example, if I use CPXbaropt, then I get optimal solutions to the MIP, but not for all the test cases. If I use either CPXprimopt or CPXdualopt, I never get to the optimal solution in any of the cases. I understand that I need to get a paretooptimal type solution among all optimal solutions but do I have to define another objective for it? This is a modeling question but would like your thoughts on it anyway. :)
A related question is that our MIP can get really huge. If we solve it without any decomposition techniques, the root relaxation alone takes a long time (20+ hours). The Benders decomposition is implemented independently. That is, we clone the original problem, delete the variables/constraints, split them into master and slave, etc., If I instead do the Bender cuts through callbacks (user/lazy), will that reduce the root relaxation time in any way or would that only help in the branch and cut?
Regards,
Vivek

ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121109T14:07:43Z in response to SystemAdminThis is a bit confusing. A degenerate primal solution typically implies multiple dual solutions (other than in rather unusual cases, I think) but does not typically imply multiple primal solutions, whereas you seem to be saying the opposite occurs.
You might want to look at the following paper, which discusses a way to generate tighter Benders cuts. (I think it applies only to optimality cuts, but my recollection is shaky.)
Magnanti, T.L. & Wong, R.T., Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria, Operations Research, 1981, Vol. 29(3), pp. 464484
I'm also having trouble understanding your last question. Use of callbacks versus the traditional solve master  solve subproblem  add cuts  loop approach does not change what the master problem looks like, or how long it takes to solve the root node the first time. In the conventional approach, each pass through the loop solves the master root again, and each time the master has grown by at least one constraint. On the other hand, after the first pass CPLEX can hotstart and use dual simplex to optimize the root fairly quickly (I think). The callback method solves the root only once. I favor the callback approach, but it won't change how long the first master root node takes.
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121109T14:59:11Z in response to SystemAdminHi Paul,
Sorry for the confusion. I think I used a wrong term here. What I meant by 'degenerate' is the existence of multiple optimal solutions. For example, when there exists two variables with the same cost coefficient. In this case, I guess the right thing to say is that primal is nondegenerate and has multiple solutions but dual could still be unique? As indicated by several nonbasic variables with zero reduced costs.
Our problem is similar to airline fleet assignment (assignment of aircrafts to flight legs). We are trying an approach where in we further decomposed the cuts for each flight leg. That is, we generate a bound for each the legs. This leg level approach requires us to rely on the primal solution too to arrive at the bounds for each leg. But because of the multiple primal solutions, we are unable to achieve optimality for all the test cases.
Thanks for the paper. I think I might be able to apply the same technique to my problem too.
Regarding the last point, in the callback method of doing things, I was under the impression that we add user cuts directly to the original problem. I now gather that we still have to make at least one master problem and keep adding cuts to it instead of starting from scratch. In our traditional implementation, we have turned on CPX_MIP_MIPSTART and we load the .mst file from the previous iteration of the master problem. Do you think this approach would have the same effect as using the callbacks?
Regards,
Vivek.
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121109T22:28:36Z in response to SystemAdminVivek,
> Sorry for the confusion. I think I used a wrong term here. What I meant by 'degenerate' is the existence of multiple optimal solutions. For example, when there exists two variables with the same cost coefficient. In this case, I guess the right thing to say is that primal is nondegenerate and has multiple solutions but dual could still be unique? As indicated by several nonbasic variables with zero reduced costs.
Zero reduced costs on nonbasic variables makes it likely (but not certain) that alternate primal optima exist. The implication for the dual is that the dual solution is degenerate (but typically unique).
> Regarding the last point, in the callback method of doing things, I was under the impression that we add user cuts directly to the original problem.
You can do that (in situations where you can come up with cuts to add), but that's not Benders decomposition.
> I now gather that we still have to make at least one master problem
Yes, and one or more slave problems.
> and keep adding cuts to it instead of starting from scratch. In our traditional implementation, we have turned on CPX_MIP_MIPSTART and we load the .mst file from the previous iteration of the master problem. Do you think this approach would have the same effect as using the callbacks?
It's a step in the right direction (probably), but I would expect that the "one tree" approach (callbacks) would be faster in most cases. (I've learned never to say "in all cases" when MIPs are involved.)
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121113T10:30:45Z in response to SystemAdminHi Paul,
Thanks!
Regarding multiple optimal primal solutions, I was hoping I could use a relative interior (ri) point of the dual solution to the subproblem to get to one single optimal primal solution among all possible solutions such that my bounds on the bender cuts are tightened. This is as per the paper to get the pareto optimal cut but applied to the primal solution instead of dual solution. As my cuts depend on both primal as well as dual solutions. And for each alternate primal, there is a value of the bound that I would like to maximize. Can I force CPLEX's barrier method to give me a RI point (a nonvertex solution typically but on the central path)?
Regards,
Vivek.
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121113T17:04:01Z in response to SystemAdminYou cannot really "force" CPLEX to provide a RI point, but if you disable crossover and presolve, then chances are high that you will get one.
Tobias
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121113T18:12:32Z in response to SystemAdminThanks Tobias!
I was earlier trying with convergence tolerance and switching off crossover. But by turning off presolve, I was able to solve few instances to optimality. And not for all. Also, for larger problem set, turning off presolve seems to have major impact on the performance. Is there any other way? Even an approximate (slightly infeasible) RI would do for me.
Regards,
Vivek.
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121114T09:02:56Z in response to SystemAdminYou could explicitly formulate the problem to find a relative interior point, for example as in:
R. Freund, R. Roundy, M. J. Todd
"Identifying the Set of AlwaysActive Constraints in a System of Linear Inequalities by a Single Linear Program"
Tech. Rep, No. 167485, Sloan School, M.I.T., 1985
If you want to get a relative interior point of the optimal face, then you would need to optimize over the regular model, fix the variables and slacks with nonzero reduced costs and duals, respectively, and then construct the auxiliary model to find a relative interior point. Of course, this is then two solves instead of one, so it might be too expensive for you.
Maybe, you can combine the original objective function and the "go to the interior" objective function, so that you only need to solve a single model in the end...
Tobias
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121217T22:51:25Z in response to SystemAdminDear Tobias
would you mind to shed light on this:
combine the original objective function and the "go to the interior" objective function, so that you only need to solve a single model in the end..
many thanks in advance
Shahin
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121228T12:53:14Z in response to SystemAdminI had some success with the following formulation:
Min b*y
St:
A*y >= c
b*y >= (1 + tau) * D
y  y* <= tau
 y* is the optimal solution and D is objective value corresponding to that optimal solution.
 The last constraint is a QCP constraint which could be readily solved by Barrier
 tau >= 0
Regards,
Vivek.






ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121229T14:24:27Z in response to SystemAdmin"It's a step in the right direction (probably), but I would expect that the "one tree" approach (callbacks) would be faster in most cases. (I've learned never to say "in all cases" when MIPs are involved.)"
Hi Paul,
I created one master problem at the very first iteration and started adding cuts through callbacks. I see that my cuts are being applied at every opportunity. And I do get the integer solutions relatively faster. But my best bound doesn't seem to improve at the same pace. Also, I have observed that the Benders does take long time to converge in my noncallback approach. But was wondering if you have observed something similar?
Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap Variable B NodeID Parent Depth Nodefile size = 70.55 MB (33.05 MB after compression) 805 639 5526679.1409 43 5284779.1038 1.12019e+07 54562 111.97% Y_5702 D 805 804 63 809 639 7430356.1712 66 5284779.1038 1.12019e+07 55269 111.97% V_255360 U 809 116 70 818 644 5338070.6709 43 5284779.1038 1.12019e+07 55894 111.97% Y_377 D 818 816 77 822 645 7285620.5136 66 5284779.1038 1.12019e+07 56737 111.97% V_193060 D 822 821 46 836 659 6245786.4840 49 5284779.1038 1.12019e+07 57564 111.97% Y_10955 D 836 835 60 848 667 5710461.4504 36 5284779.1038 1.12019e+07 57650 111.97% V_336959 D 848 847 72 854 669 7430356.1712 65 5284779.1038 1.12019e+07 58367 111.97% V_255342 U 854 89 43 862 674 6370075.0618 42 5284779.1038 1.12019e+07 58904 111.97% Y_3331 D 862 861 51 880 689 5942647.4482 31 5284779.1038 1.12019e+07 59246 111.97% V_336938 D 880 879 69 929 726 5957264.6404 54 5284779.1038 1.12019e+07 62448 111.97% V_383928 D 929 928 61 Elapsed real time = 6476.91 sec. (tree size = 230.71 MB, solutions = 6) Nodefile size = 103.56 MB (48.67 MB after compression) * 999 775 integral 0 5457160.4499 1.12019e+07 64603 105.27% V_59 U 999 998 79 User: 16 1026 792 6929517.6170 68 5457160.4499 1.12019e+07 67370 105.27% Y_10954 D 1026 1025 48 1059 815 5477399.7231 47 5457160.4499 1.12019e+07 69530 105.27% Y_7517 D 1059 1058 69 1102 839 6637115.9236 32 5457160.4499 1.12019e+07 72589 105.27% Y_10959 D 1102 1101 78 * 1116 530 integral 0 6843399.2391 1.12019e+07 73351 63.69% V_297095 U 1116 1114 90 User: 7 * 1118 488 integral 0 6935312.9382 1.12019e+07 73472 61.52% V_297096 U 1118 1117 91 User: 3 1146 494 7245884.4547 66 6935312.9382 1.12019e+07 76806 61.52% V_255351 U 1146 93 47 1168 493 7566975.3259 46 6935312.9382 1.12019e+07 80140 61.52% V_191571 D 1168 1167 61 1207 502 7642721.0022 50 6935312.9382 1.12019e+07 83072 61.52% V_254230 U 1207 118 72 1249 520 7020873.3581 62 6935312.9382 1.12019e+07 86978 61.52% V_19600 D 1249 1248 57 Elapsed real time = 7512.06 sec. (tree size = 164.74 MB, solutions = 9) Nodefile size = 37.67 MB (17.70 MB after compression) 1295 536 6975967.5697 5 6935312.9382 1.12019e+07 91760 61.52% V_19594 D 1295 1293 80 1325 540 7537922.4261 55 6935312.9382 1.11705e+07 96343 61.07% V_434034 U 1325 128 82 1357 534 5905780.6450 11 6935312.9382 1.11599e+07 100928 60.91% V_337376 D 1357 1356 101 1383 537 7542166.2845 52 6935312.9382 1.11599e+07 104094 60.91% V_294856 D 1383 1382 99 1420 544 7383357.9660 63 6935312.9382 1.11572e+07 107118 60.88% V_253097 D 1420 1419 81 1461 573 1.07659e+07 195 6935312.9382 1.11572e+07 109818 60.88% Y_10955 D 1461 1460 110 1524 636 1.07223e+07 176 6935312.9382 1.11572e+07 110547 60.88% Y_9333 D 1524 1523 173 1550 662 1.07047e+07 144 6935312.9382 1.11572e+07 111037 60.88% Y_6572 D 1550 1549 199 1587 699 1.06744e+07 131 6935312.9382 1.11572e+07 111461 60.88% V_458193 D 1587 1586 236 1623 727 7481434.4227 60 6935312.9382 1.11572e+07 113105 60.88% V_434425 U 1623 153 107 Elapsed real time = 8632.95 sec. (tree size = 231.08 MB, solutions = 9) Nodefile size = 104.26 MB (48.84 MB after compression) 1679 756 7610228.0051 28 6935312.9382 1.11464e+07 116835 60.72% Y_9361 D 1679 1678 137 1729 739 7060245.4885 48 6935312.9382 1.11106e+07 120236 60.20% Y_6628 D 1729 15 11 1763 727 cutoff 6935312.9382 1.10428e+07 125495 59.23% V_440859 U 1763 55 9 1776 722 9539275.5215 3 6935312.9382 1.10140e+07 129980 58.81% V_360364 U 1776 231 185 * 1826 622 integral 0 7055107.3074 1.09278e+07 134140 54.89% V_59 U 1826 1825 20 User: 71 1861 626 7253360.6324 49 7055107.3074 1.07659e+07 137966 52.60% V_147758 D 1861 1860 99 1906 640 cutoff 7055107.3074 1.07659e+07 142094 52.60% V_189776 U 1906 1477 127
Thanks,
Vivek.
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121229T22:46:10Z in response to SystemAdminSlow convergence is not uncommon (both with and without Benders decomposition). I don't think the "one tree" approach is prone to slower convergence than the restart at each iteration approach in general, but on any given problem instance pretty much anything can happen.
A couple of things that might (or might not) speed up convergence:
1. You can try switching the MIPEmphasis parameter in the master problem to 2 (emphasize optimality) or 3 (move the bound), which could result in the bound moving faster (but might or might not affect how quickly you find new incumbents).
2. If your Benders subproblems generate optimality (point) cuts, and not just feasibility (ray) cuts, you might look at
Magnanti, T. L. & Wong, R. T. Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria Operations Research, 1981, 29, 464484
which discusses a way to pick subproblem solutions so as to make optimality cuts a bit deeper.
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20121231T04:37:54Z in response to SystemAdminHi Paul,
Thanks again!
2 helped a lot. It cut down the number of iterations by 15%. I hope it translates to similar time savings for larger problems.
Other thing I observed is that through callback approach, the normal cuts don't seem to get generated/applied, compared to the noncallback approach.
For example, I see only this at the end of the solve: "User cuts applied: 1465". No other cut information is available. I see the following at the very beginning. Could it be because of this?
Lazy constraint(s) or lazy constraint callback is present. Disabling dual reductions (CPX_PARAM_REDUCE) in presolve. Disabling nonlinear reductions (CPX_PARAM_PRELINEAR) in presolve.
Regards,
Vivek.Updated on 20140324T22:43:29Z at 20140324T22:43:29Z by ironman
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20130102T22:51:17Z in response to SystemAdminVivek,
I'm not on the cutting edge when it comes to cuts (sorry, couldn't resist, first bad pun of the new year), but I think that some cuts are based on dual values of the LP relaxation. When you have a lazy constraint callback (or apparently when you have lazy constraints in the model, although I'm a bit more surprised by the latter), the dual values are unreliable, because the addition of an as yet unrevealed constraint could easily change some or all of the dual solution. So CPLEX automatically turns of dual reductions when it sees lazy constraints, and logically it should also turn off whichever cuts rely on dual values.
Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20130103T10:25:01Z in response to SystemAdminThanks Paul. That makes sense.
In that one instance I posted the result, I didn't see nonuser cuts being applied but in others I do.
Regards,
Vivek.


ACCEPTED ANSWER
Re: Benders decomposition and primal degenerate basis
20140409T21:12:04Z in response to SystemAdminVivek.
I am facing with the same problem as you had with the convergence of the Benders. I was hoping to get stronger cuts by implementing the idea of generating paretooptimal cuts as it is suggested by Magnanti referred by Paul. From your earlier post I see that you had a success in the performance of Benders by implementing the idea.
Could you please give me some more details about your implementation?
1 Doesn't it require to find an interior point of the optimal face, to be able to get the paretooptimal solution?
2 If so, how do you get that interior point?
3 If there is an auxiliary problem to find the pareto dual solutions, what is the form of that?
Thanks in advance.
Guven.
Updated on 20140409T21:12:26Z at 20140409T21:12:26Z by 1CEV_Guven_Ince





