Originally posted by: SystemAdmin

Folks,

We have a MIP which couldn't be solved in reasonable time frame. So we have decomposed that MIP using Benders. But our LP sub-problems 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 sub-optimal 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 pareto-optimal 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
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This 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. 464-484

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 hot-start 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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi 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 non-degenerate and has multiple solutions but dual could still be unique? As indicated by several non-basic 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.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Vivek,

> 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 non-degenerate and has multiple solutions but dual could still be unique? As indicated by several non-basic 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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Paul,

Thanks!

Regarding multiple optimal primal solutions, I was hoping I could use a relative interior (ri) point of the dual solution to the sub-problem 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 non-vertex solution typically but on the central path)?

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You 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
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks 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.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You 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 Always-Active Constraints in a System of Linear Inequalities by a Single Linear Program"
Tech. Rep, No. 1674-85, 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 non-zero 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
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Dear 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
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I 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.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: 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 non-callback 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.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Slow 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, 464-484

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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi 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 non-callback 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 non-linear reductions (CPX_PARAM_PRELINEAR) in presolve.

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Vivek,

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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Paul. That makes sense.

In that one instance I posted the result, I didn't see non-user cuts being applied but in others I do.

Regards,
Vivek.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: 1CEV_Guven_Ince

Vivek.

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 pareto-optimal 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 pareto-optimal 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.

 

#CPLEXOptimizers
#DecisionOptimization