Decision Optimization

 View Only
  • 1.  BENDERS WARNING: no sub-problems left

    Posted Fri September 23, 2022 06:55 PM
    Edited by System Fri January 20, 2023 04:34 PM
    Hello everyone, 

    I am trying to compare three different modeling approaches on a set of instances with two variables x (integer), and y (continuous) using CPLEX 12.7 version.

    In the first one, I use a  single MIP model, in the second, a manual Benders decomposition where two separate models, a master (for x) and a sub-problem (for y) are written and cuts are added through LazyConstraints callbacks, and in the third, CPLEX automatic benders decomposition is used.

    while the  single MIP model and the Manual approach gave the same (optimal) results, CPLEX automatic benders raise the following warning : 

    "BENDERS WARNING: no sub-problems left", and the problems became infeasible. 

    No matter which Benders strategy parameter I use (Full, Workers, or User) I got the same error.

    After checking the annotation file below written by cplex.writeBendersAnnotation(), it seems that CPLEX annotate every variable y_ijk to a different sub-problem.

    Shouldn't the value of every variable be the same so they are placed in the same sub-problem? In my case the value shouldn't the value be equal to 1?

    Thank you for your help.


    <?xml version='1.0' encoding='utf-8'?>
    <CPLEXAnnotations>
    <CPLEXAnnotation name='cpxBendersPartition' type='long' default='0'>
    <object type='1'>
    <anno name='y_0_0_0' index='0' value='1'/>
    <anno name='y_0_0_1' index='1' value='2'/>
    <anno name='y_0_0_2' index='2' value='3'/>
    <anno name='y_0_1_0' index='3' value='4'/>
    <anno name='y_0_1_1' index='4' value='5'/>
    <anno name='y_0_1_2' index='5' value='6'/>
    <anno name='y_0_2_0' index='6' value='7'/>
    <anno name='y_0_2_1' index='7' value='8'/>
    <anno name='y_0_2_2' index='8' value='9'/>
    <anno name='y_0_3_0' index='9' value='10'/>
    <anno name='y_0_3_1' index='10' value='11'/>
    <anno name='y_0_3_2' index='11' value='10'/>
    <anno name='y_1_0_0' index='12' value='12'/>
    <anno name='y_1_0_1' index='13' value='10'/>
    <anno name='y_1_0_2' index='14' value='10'/>
    <anno name='y_1_1_0' index='15' value='13'/>
    <anno name='y_1_1_1' index='16' value='14'/>
    <anno name='y_1_1_2' index='17' value='15'/>
    <anno name='y_1_2_0' index='18' value='16'/>
    <anno name='y_1_2_1' index='19' value='17'/>
    <anno name='y_1_2_2' index='20' value='18'/>
    <anno name='y_1_3_0' index='21' value='19'/>
    <anno name='y_1_3_1' index='22' value='20'/>
    <anno name='y_1_3_2' index='23' value='21'/>
    </object>
    </CPLEXAnnotation>
    </CPLEXAnnotations>



    ------------------------------
    ISSA bou zeid
    ------------------------------
    #DecisionOptimization


  • 2.  RE: BENDERS WARNING: no sub-problems left

    IBM Champion
    Posted Sun September 25, 2022 02:58 PM
    CPLEX did in fact assign four variables to the same subproblem (value="10"). This suggests that most of your y variables appear in constraints that contain only them (and some x variables) and do not contain other y variables. That would induce CPLEX to put them in subproblems by themselves (which should not produce an error).

    When you attempt to use USER decomposition, how do you set your annotations?

    It might help to see the full output log (as an attachment).

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: BENDERS WARNING: no sub-problems left

    Posted Mon October 24, 2022 06:02 AM

    Hello Paul,

    Sorry for my late reply.
    To answer your question, I do the following, first I initialize the annotation as following:

    IloCplex.LongAnnotation bendersUsers = cplex.newLongAnnotation(IloCplex.CPX_BENDERS_ANNOTATION);

     
    Then for every variable I set the annotation:

     cplex.setAnnotation(benders, xvar, 0); for variables that go in the master problem

     or cplex.setAnnotation(benders, yvar, 1); for variables that go in the sub-problem

     
    However, after verifying the log file and trying a few parameters, it looked like for some instances, the problem was too easy that was solved in presolve, thus the error "BENDERS WARNING: no sub-problems left". I attach the log file (log1.log) of the problem solved as a single MIP, as benders using strategy 3 (I also have the same error when using the FULL strategy or the USER strategy) with presolve enabled , and with presolve disabled. 

    I can see that it was solved with benders strategy 3 when presolve is disabled (set preprocessing presolve no). 

    However for some other instances, when presolve is set to no, I got the following error: CPLEX Error 3019: Failure to solve MIP subproblem.
    I attach the log file (log2.log). (same error with benders strategy FULL, or USER) 

    I am wondering what's going on and how to avoid such errors? 

    Thank you. Your help is much appreciated.
    Best Regards.



    ------------------------------
    ISSA bou zeid
    ------------------------------



  • 4.  RE: BENDERS WARNING: no sub-problems left

    IBM Champion
    Posted Mon October 24, 2022 11:51 AM
    Before continuing further down this rabbit hole, you should make sure that your test problems are amenable to Benders decomposition. Looking at your log1 file, the first time you solve the problem (no decomposition) CPLEX reports that it has 14 columns and 14 "general" (integer) variables. When you try Benders strategy 3, it reports "no sub-problems left" because there are no subproblems, since there are no continuous variables. That is also the source of the Error 2002 message.

    Benders decomposition requires subproblems that are linear programs, which means they contain continuous variables.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 5.  RE: BENDERS WARNING: no sub-problems left

    Posted Mon October 24, 2022 03:36 PM
    Thank you Paul for your reply.

    Yes in my model, I have a couple of integer variables and one continuous variable linked to one of the integer variables and to the binary variables in othe constraints. Below is the solution found by CPLEX.

    CPLEX> display sol var *
    Incumbent solution
    Variable Name Solution Value
    p_0              1.000000 (Integer)
    Direct_0       1.000000 (Binary)
    dummy         1.000000 (Binary)
    y_0_0_0_1    4666.666667 (Continuous)
    x_0_1           1.000000  (Integer)
    x_0_0            1.000000 (Integer)
    x_0_2            1.000000 (Integer)
    x_0_3            1.000000 (Integer)

    However since this example is too small, the binary variables could be fixed and thus the right-hand side of the constraints linking the continuous variables and the binary variables becomes a constant. For instance, let yigkt be the continuous variable and zi be the binary variable, and Cigt is a constant for every i,g,t, thus the original constraints Σyigkt = Cigt * zi for all i,g,t  becomes Σyigkt = Cigt for all i,g,t with additional constraints zi = 1 for all i.

    Honestly the example I showed is too small and Benders decomposition isn't necessarily the most suitable approach. However for larger instances, I think BD would work so well since the number of continuous variables to the integer one is significant.

    Best regards.



    ------------------------------
    ISSA bou zeid
    ------------------------------