Decision Optimization

Decision Optimization

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

 View Only
Back to discussions
Expand all | Collapse all

Obtaining a bound via the MIPInfoCallback

  • 1.  Obtaining a bound via the MIPInfoCallback

    Posted Mon September 02, 2013 11:06 AM

    Originally posted by: JorisK


    Dear,
     
    I'm currently implementing a Benders decomposition using the java interface to cplex 12.5.1. The principle is simple: a master problem is solved for a subset of the variables. Next, a subproblem determines whether the variable value obtained from the master problem are feasible. If not, a cut is added to the master problem and the process is repeated. If the subproblem determines that the values assignment by the master problem are indeed feasible, a provable optimal solution is obtained.
     
    As for the implementation, the master problem is solved in a Branch-and-cut framework. Each time an integer solution is encountered, a LazyCutCallback is invoked. This callback implements the subproblem.
     
    For most instances, solving the entire problem takes too much time. To limit the solution time, I've put a time limit on the master problem via the IloCplex.DoubleParam.TiLim parameter. As a consequence, no feasible solution to a problem instance may be found within the alloted time. Nevertheless, the master problem may still yield a valid bound on the optimal solution. My question is: how do I obtain this bound in cplex? I have added a MIPInfoCallback to the master problem, which gives me access to the "getBestObjValue()" method. According to the description:
     
    "This method returns a bound on the optimal solution value of the active problem at the moment the callback is called. When a model has been solved to optimality, this value matches the optimal solution value. Before optimality has been proven, this value is computed for a minimization (maximization) problem as the minimum (maximum) objective function value of all remaining unexplored nodes. "
     
    This seems to be exactly what I need. However, the behavior of the MIPInfoCallback seems to be rather hard to predict. For some small instances, which I can solve to optimality in a few seconds, the MIPInfoCallback isn't invoked at all. For other instances, the MIPInfoCallback is indeed invoked but, according to some other replies on this forum there seems to be no guarantee that the MIPInfoCallback is invoked at every node of the branch-and-bound tree? How can I guarantee that the MIPInfoCallback is at least invoked right before cplex terminates due to the time restriction?

    Should I perhaps use the MIPInfoCallback together with the LazyCutCallback to obtain the bound via the getBestObjValue() function?

     
    br,
     
    Joris

    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Obtaining a bound via the MIPInfoCallback

    Posted Mon September 02, 2013 12:46 PM

    Note that class IloCplex also has a getBestObjValue() method. After the time limit expired this should give you the best bound CPLEX could prove -- exactly what a callback's getBestObjValue() would give before the time limit expires.

    You are right, the info callback is not invoked at every node (and that is even stated somewhere in the docs). There is no exact specification with which frequency this callback is invoked.

    If you want a callback that is invoked at every node then use for example the branch callback or a heuristic callback (and do nothing in any of those callbacks).


    #CPLEXOptimizers
    #DecisionOptimization


Related Content