Decision Optimization

 View Only
  • 1.  Benders cuts in OPL using CPLEX 12.7.1

    Posted Fri August 16, 2019 08:08 AM

    Originally posted by: Nomykan


    HI 

    i am trying to solve a MIP problem through benders decomposition using OPL in CPLEX 12.7.1. i have gone through the examples provided with the package i.e benders and also portfolio. in this version annotations are used for benders partitions but i am confused how to use benders feasibility cut in the subproblem. in the benders example only annotations are used and no information about benders cuts and how to implement them with annotations. in portfolio optimization no annotations are used. help in this regard will be highly appreciated. a small example using benders cuts  or more information about it will be highly appreciated. 

    thanks in advance


    #DecisionOptimization
    #MathematicalProgramming-General


  • 2.  Re: Benders cuts in OPL using CPLEX 12.7.1

    IBM Champion
    Posted Fri August 16, 2019 07:18 PM

    When you are using "automatic" Benders (via annotations), you do not specify the Benders cuts. You just tell CPLEX (through annotations) how to partition the original model into master problem and subproblem(s), or you tell CPLEX to partition automatically. Once the problem is partitioned, CPLEX generates standard Benders cuts (both optimality and feasibility cuts) automatically.

    If for some reason you want non-standard Benders cuts, you need to use callbacks to implement them. I'm not positive that it is still true, but as of a year or so ago callbacks were not available through OPL, and I believe they still are not.


    #DecisionOptimization
    #MathematicalProgramming-General


  • 3.  Re: Benders cuts in OPL using CPLEX 12.7.1

    Posted Sat August 17, 2019 09:11 AM

    Originally posted by: Nomykan


    Hi PaulRubin

    Thanks for your response. actually my problem consists of a master problem and subproblem. i want to use the solution of the master problem and use it in the subproblem. if the result of the master problem is infeasible for the sub problem then a cut will be added to the master problem as shown in the figure attached with this response. if the solution of master problem is feasible then solve the subproblem and so on. so i am confused in this case what to do? just use the flowcontrol for the problem and use automatic benders strategy or provide benders cuts to the problem to solve? help in this regard will be highly appreciated. Thanks  


    #DecisionOptimization
    #MathematicalProgramming-General


  • 4.  Re: Benders cuts in OPL using CPLEX 12.7.1

    Posted Sat August 17, 2019 09:12 AM

    Originally posted by: Nomykan


    Hi PaulRubin

    Thanks for your response. actually my problem consists of a master problem and subproblem. i want to use the solution of the master problem and use it in the subproblem. if the result of the master problem is infeasible for the sub problem then a cut will be added to the master problem as shown in the figure attached with this response. if the solution of master problem is feasible then solve the subproblem and so on. so i am confused in this case what to do? just use the flowcontrol for the problem and use automatic benders strategy or provide benders cuts to the problem to solve? help in this regard will be highly appreciated. Thanks  


    #DecisionOptimization
    #MathematicalProgramming-General


  • 5.  Re: Benders cuts in OPL using CPLEX 12.7.1

    IBM Champion
    Posted Sat August 17, 2019 11:51 AM

    Let me start by describing what I would call "standard" Benders decomposition, and see if it applies to your situation. You start with a MIP model (containing both integer and continuous variables). You pull out the continuous variables and the constraints that involve them and make that the subproblem. The master problem contains the integer variables (plus one continuous variable representing the contribution of the subproblem to the objective function), plus any constraints that involve only the integer variables (and, as the algorithm progresses, the Benders cuts).

    If this is what you are doing, the annotation system will do it for you. You give CPLEX the original, full model (containing all variables, integer and continuous), and either use annotations to tell CPLEX which parts go into the subproblem or let CPLEX figure that out automatically. CPLEX takes care of the cut generation process in your flowchart.

    On the other hand, in some situations the subproblem does not come from the original, full MIP model, but arises externally. If that is the case, meaning you do not have a MIP model with all the variables and constraints in it to start, you cannot use annotation. So you either need to drop OPL and switch to an API that allows callbacks (C, C++, Java, ...) or you need to stick with OPL, write a script that alternates between master and subproblem, and do this the way Jack Benders originally did. That means you solve the master (either to "optimality" or to some time or solution limit), test the solution in the subproblem and, if the subproblem generates any cuts, add them to the master problem and the solve the master again (starting over each time).


    #DecisionOptimization
    #MathematicalProgramming-General


  • 6.  Re: Benders cuts in OPL using CPLEX 12.7.1

    Posted Sat August 17, 2019 12:20 PM

    Originally posted by: Nomykan


    Hi PaulRubin

    i really appreciate your effort in response to the queries. my situation is the second case i.e. 

    " the subproblem does not come from the original, full MIP model, but arises externally. If that is the case, meaning you do not have a MIP model with all the variables and constraints in it to start, you cannot use annotation. So you either need to drop OPL and switch to an API that allows callbacks (C, C++, Java, ...) or you need to stick with OPL, write a script that alternates between master and subproblem, and do this the way Jack Benders originally did. That means you solve the master (either to "optimality" or to some time or solution limit), test the solution in the subproblem and, if the subproblem generates any cuts, add them to the master problem and the solve the master again (starting over each time)".

    i want to stick to OPL. so in this case if i use the flowcontrol in the OPL like first solve the main problem and then use this solution in the subproblem. if the subproblem is feasible with the solution from the main problem then there is no issue in the program. but in case if the solution is infeasible then i need to add cuts to the main problem to start over with the cuts and then solve again the main problem. if the solution from the main problem is then feasible with the subproblem then the program proceeds. so in this case how can i add cuts to the main problem without benders decomposition without anootations?  

    Thanks again for such a quick response


    #DecisionOptimization
    #MathematicalProgramming-General


  • 7.  Re: Benders cuts in OPL using CPLEX 12.7.1

    IBM Champion
    Posted Sat August 17, 2019 12:30 PM

    You just add the cuts as new constraints in the master problem (the same way you added the original constraints to the master).


    #DecisionOptimization
    #MathematicalProgramming-General


  • 8.  Re: Benders cuts in OPL using CPLEX 12.7.1

    Posted Sun August 18, 2019 01:14 AM

    Originally posted by: Nomykan


    Thanks a lot ... this has now cleared my confusion ..


    #DecisionOptimization
    #MathematicalProgramming-General


  • 9.  RE: Re: Benders cuts in OPL using CPLEX 12.7.1

    Posted Thu April 08, 2021 10:24 AM
    Hello. I use CPLEX Auto-Benders in Visual Studio(C#), my question is that how can I get the number of optimality and feasibility cuts ?
    thanks in advance.

    ------------------------------
    faeze pooladi
    ------------------------------