Topic
  • 15 replies
  • Latest Post - ‏2014-04-09T21:12:04Z by 1CEV_Guven_Ince
SystemAdmin
SystemAdmin
7929 Posts

Pinned topic Benders decomposition and primal degenerate basis

‏2012-11-09T09:19:08Z |
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
Updated on 2013-01-03T10:25:01Z at 2013-01-03T10:25:01Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-09T14:07:43Z  
    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-09T14:59:11Z  
    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)
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-09T22:28:36Z  
    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.
    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-13T10:30:45Z  
    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)
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-13T17:04:01Z  
    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.
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-13T18:12:32Z  
    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
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-11-14T09:02:56Z  
    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.
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-12-17T22:51:25Z  
    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
    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
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-12-28T12:53:14Z  
    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
    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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-12-29T14:24:27Z  
    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)
    "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.
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-12-29T22:46:10Z  
    "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?
    <pre class="jive-pre"> 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 </pre>
    Thanks,
    Vivek.
    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2012-12-31T04:37:54Z  
    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)
    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.
    Updated on 2014-03-24T22:43:29Z at 2014-03-24T22:43:29Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2013-01-02T22:51:17Z  
    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?

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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. </pre>

    Regards,
    Vivek.
    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)
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Benders decomposition and primal degenerate basis

    ‏2013-01-03T10:25:01Z  
    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)
    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.
  • 1CEV_Guven_Ince
    1CEV_Guven_Ince
    1 Post

    Re: Benders decomposition and primal degenerate basis

    ‏2014-04-09T21:12:04Z  
    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?

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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. </pre>

    Regards,
    Vivek.

    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.

     

    Updated on 2014-04-09T21:12:26Z at 2014-04-09T21:12:26Z by 1CEV_Guven_Ince