Decision Optimization

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?

Originally posted by: Petr Vilím

Hello,

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

Originally posted by: RuiFig

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

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.

Petr