Decision Optimization

Decision Optimization

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

 View Only
Back to discussions
Expand all | Collapse all

A branching direction / cutoff causes loss of the optimal value

  • 1.  A branching direction / cutoff causes loss of the optimal value

    Posted Thu March 05, 2015 10:19 AM

    Originally posted by: DianaHuerta


    Hi, 
     
    I have a doubt, I hope someone has an idea of what is happening.
     
    I'm trying to solve a MIP problem, I have my basic model and I add global constraints through lazy & callbacks functions. I have two kind of binary variables Z and X. I tried to solve an instance but the optimal solution is not reached because, when cuts were generated inside the callback (in that node the Z variable was branched), an integer solution was obtained. Then, cplex cut the node off and the branching direction is not taking into account because that node is not explored anymore. The thing is the node, with the optimal solution, was child of that pruned node.
     
    How can I avoid that in order to get the optimal value?
     
    Any suggestion?, 
     
    Thank you.
     
    Regards. 

    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: A branching direction / cutoff causes loss of the optimal value

    Posted Fri March 06, 2015 01:38 AM

    Do I understand correctly: there is a node N at which the LP relaxation is integral. Since the relaxation is integral it should be OK to stop exploring this node. But in your case CPLEX should continue branching on N? Why do you expect CPLEX to do that? Is this because the integer solution at N violates a lazy constraint (do you add this lazy constraint?)? What actions do you take to make CPLEX continue branching on N? You would have to at least separate a lazy constraint for N or reject the solution in an incumbent callback.


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: A branching direction / cutoff causes loss of the optimal value

    Posted Fri March 06, 2015 05:33 AM

    Originally posted by: DianaHuerta


    Hi, 
     
    Ok, I could see in the log file, that solution was not considered integer (I have read that there must be an * beside the IDNode to consider a solution like that), but it is almost one. I know which is the optimal solution because  I have generated, and added all the constraints needed for a very small instance. When I remove the callback (not lazy) function, the optimal solution can be reached. When I add the callback again, in certain node N, this function generates 1 cut and (after resolve) cplex find a solution that is not integer at all but with a small fractional differences in some X variables (ex. -3.33e-11). Then, cplex pruned that node (but I observed that the generated cut is really needed). I thought it could be a tolerance trouble, but actually I don't know.
     
    I'm trying to find a way that helps me to know what is happening. I had analyzed my implementation but I cannot see until now what is wrong, the generated cuts seem to be correct.
     
    This is part of the log file where node 225 was pruned .

     

        221   135     4974.8415    34     5477.5643     3879.0918     2457   29.18%            z021 U    221    220      9
        222   136     5104.2700    18     5477.5643     3879.0918     2474   29.18%            z221 U    222    221     10
        223   137     5185.9327    24     5477.5643     3879.0918     2479   29.18%            z212 D    223    222     11
        224   138     5265.6467    21     5477.5643     3879.0918     2487   29.18%            z202 D    224    223     12
        225   137        cutoff           5477.5643     3879.0918     2498   29.18%            z222 N    225    224     13
        226   136        cutoff           5477.5643     3879.0918     2507   29.18%            z222 U    226    224     13
        227   135    infeasible           5477.5643     3883.5332     2641   29.10%           x3421 N    227     78      7
        228   134        cutoff           5477.5643     3903.3361     2678   28.74%            z422 U    228     68      9
        229   133    infeasible           5477.5643     3913.2930     2717   28.56%            z221 D    229     83     12
        230   134     4967.7603    31     5477.5643     3925.6737     2780   28.33%           x3412 U    230     70     11

     

    I'm working on that, but I consider it is good to have some different ideas to understand what is happening. I will check again my implementation to be completely sure it is correct.
     
    Thanks for your response.

    Regards.

    Diana

     

     

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: A branching direction / cutoff causes loss of the optimal value

    Posted Thu March 12, 2015 03:10 AM

    Node 225 was cut off. That means its objective function value exceeded the current incumbent's objective. So, unless there is numerical trouble, node 225 cannot contain any solution that is better than the current incumbent. In particular, it cannot contain the optimal solution.

    When you say that a solution with fractional values in the order of 1e-11 is not integral then I disagree. 1e-11 is basically 0, so such a solution can well be considered integral. If you want to avoid these things then you should set CPX_PARAM_EPINT to 0.

    Another thing: are you sure that the solution you get and think is non-optimal is indeed non-optimal? If CPX_PARAM_EPGAP and CPX_PARAM_EPAGAP then it can very well happen that the two runs produce two different optimal solutions but both solutions are optimal within the specified tolerances.

    A way to analyze what is going wrong could be the following:

    1. Solve the model without callbacks so that you get the (presumably) optimal solution.
    2. Solve the model with callbacks but also feed the optimal solution as a MIP start. Check if that MIP start is accepted or not.
    3. Also check for every lazy constraint you separate whether it cuts off the solution found in 1.

    This may give you an idea about whether the lazy constraints you separate cut off the optimal solution. Also (but this is very cumbersome), you could keep track of all open nodes and make sure that you always have at least one open node that contains the optimal solution found in 1 (the solution satisfies the node-local variable bounds and the node's objective estimate does not exceed the optimal solution's value).


    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: A branching direction / cutoff causes loss of the optimal value

    Posted Fri March 13, 2015 11:33 AM

    Originally posted by: DianaHuerta


    Hi Daniel,

    I've done something similar to your recommendations, and I could find the error. It was a wrong consideration in my implementation.

    Thanks for your support :-)

    Best Regards.

    Diana.

     


    #CPLEXOptimizers
    #DecisionOptimization


Related Content