Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
Back to discussions
Expand all | Collapse all

In Benders Decomposition, how can we add feasibility cut to master problem if dual subproblem is a SOCP problem

  • 1.  In Benders Decomposition, how can we add feasibility cut to master problem if dual subproblem is a SOCP problem

    Posted Wed October 17, 2018 06:23 PM

    Originally posted by: Nadere


    Dear All,

     

    I have conic primal sub-problem with SOCP constraints. Therefore, I solve my problem with the barrier algorithm in CPLEX (IBM ILOG CPLEX 12.6.1).

    I devise Benders decomposition to solve my problem. Since the primal problem is a SOCP problem, the dual sub-problem is a SOCP problem. In some iterations, the dual of my problem is unbounded and I want to add feasibility cut to the master problem but the barrier algorithm does not allow me to have "getRay".

    I was wondering if you could let me know how  I can have extreme ray in SOCP problem in order to add feasibility cut to master problem.

     

    Thanks,


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: In Benders Decomposition, how can we add feasibility cut to master problem if dual subproblem is a SOCP problem

    Posted Tue December 04, 2018 08:52 AM

    Originally posted by: AndreaTramontani


    Dear Nadere,

    sorry for the delay of this reply.

    Unfortunately, if you have an unbounded SOCP, in CPLEX there is no way to query an unbounded ray. This functionality is only available for an LP.
    However, there is an easy workaround for this.
    In summary, talking about Benders, if you have an unbounded SOCP, you know you have a violated feasibility cut. Thus, you can take the homogeneous version of your SOCP, add a normalization
    constraint that makes it bounded, solve it again and construct a feasibility cut from the optimal solution of this bounded SOCP.

    Note that CPLEX (starting from release 12.7.0) has a Benders decomposition solver.
    This is for Mixed Integer Linear Programming (MILP) only, but feasibility cuts in CPLEX are separated following an approach pretty similar to what described above.
    I.e., when the Benders sub-problem (in the dual space) is unbounded, in order to separate a feasibility cut CPLEX considers the homogeneous version of the problem,
    adds a normalization constraint that makes the sub-problem bounded (and that maps extreme rays to vertices), and solves again the bounded sub-problem to construct a feasibility
    cut from the optimal solution.

    The idea implemented in CPLEX is inspired to this paper:
    M. Fischetti, D. Salvagnin, A. Zanette, "A note on the selection of Benders' cuts", Mathematical Programming 124, 175-182, 2010.
    And you can find a preliminary (and longer) version of the paper at http://www.dei.unipd.it/~fisch/papers/Benders_mis_extended_draft.pdf

    Also, for what concern CPLEX 12.8.0 implementation of Benders, you can have a look at slide 12 of the attached presentation that explains (in quick summary) the normalization.

    As I said, in CPLEX Benders decomposition is supported for MILP only, and also the paper I mentioned above is focused on MILP.
    However, the normalization of the Benders sub-problem is a general idea that can be extended to SOCP as well.


    Hope this can help you.
    Andrea
     


    #CPLEXOptimizers
    #DecisionOptimization


Related Content