Decision Optimization

 View Only
Expand all | Collapse all

solucion gap

  • 1.  solucion gap

    Posted Wed February 26, 2020 12:07 PM

    Originally posted by: RuiFig


    hi every one

    i have a more technical question today.

    I would like to understand how the cp optimizer calculates the gap between the solution obtained and the optimal one. how do cp know the value of the optimal solution and not the solution?


  • 2.  Re: solucion gap

    Posted Wed February 26, 2020 03:53 PM

    Originally posted by: Petr Vilím


    for simplicity, let's assume minimization problem. During the search CP Optimizer maintains upper bound (UB) and lower bound (LB). Upper bound is the value of the best solution so far. Lower bound is a value such that CP Optimizer already produced a proof that there is no solution with objective < LB. So during the search it is not known whether there is a solution with objective in the interval [LB, UB). When LB=UB then optimality of the current solution is proved.

    The values UB and LB are displayed in the log this way:

         61   13300k         56    4   F    12 <= startOf(itvs#23)
     ! Time = 427.75s, Average fail depth = 28, Memory usage = 13.3 MB
     ! Current bound is 37 (gap is 39.34%)

    In the example above UB=61 and LB=37. Gap is computed as (UB - LB) / UB = 39.34%.

    LB can be computed in various ways. For example:

    • By constraint propagation during the root node.
    • As a lower bound of linear relaxation of the model (in case of scheduling model).
    • In in restart search, after restart by propagation of new nogoods in the root node.
    • Using "shaving" in the root node.

    Note that CP Optimizer does not put much effort in the computation of lower bound. Lower bound is mostly byproduct of the search for better solution.

    Best regards, Petr


  • 3.  Re: solucion gap

    Posted Thu February 27, 2020 04:25 AM

    Originally posted by: RuiFig

    ok, so whenever cp stops running(except if you limit some parameter) means that it achived the optimal solution ? 


  • 4.  Re: solucion gap

    Posted Thu February 27, 2020 02:37 PM

    Originally posted by: Petr Vilím

    Yes, that's right. You can also see the reason why CP Optimizer stopped at the bottom of the log. For example, in case of optimality:

     ! ----------------------------------------------------------------------------
     ! Search completed, 6 solutions found.
     ! Best objective         : 45 (optimal - effective tol. is 0)
     ! Best bound             : 45
     ! ----------------------------------------------------------------------------

    Note that CP Optimizer may stop even in the case when LB < UB if the gap is very small. It is configured by parameters OptimalityTolerance and RelativeOptimalityTolerance. That's why there is also "effective tolerance" in the log: it shows UB-LB at the time when CP Optimizer stopped. Here is an example:

     ! ----------------------------------------------------------------------------
     ! Search completed, 11 solutions found.
     ! Best objective         : 5000 (optimal - effective tol. is 0.5)
     ! Best bound             : 4999.949
     ! ----------------------------------------------------------------------------

    In this example UB=5000 and LB=4999.949 and effective tolerance is 0.5. Because default RelativeOptimalityTolerance is 0.0001 CP Optimizer stops.