Originally posted by: AdamGregory

Hello all,

How does the CP Optimizer relative optimality tolerance (or absolute optimality tolerance) setting work in practice?

When using the constructive search strategies and constraint propagation to search the solution space for the optimal solution, does CP Optimizer apply some mechanism similar to the bounding function used by branch-and-bound algorithms to estimate the best possible objective function of a given branch and backtrack if the selected decision variable value cannot yield a solution with objective function value better (with regards to the relative optimiality tolerance) than the current incumbent solution?

Or is relative optimality tolerance implemented by some other mechanism?

Thank you,

Adam
 

Originally posted by: Philippe_Refalo

The mecanism is different in CP Optimzier than in traditional branch and bound since we don't have any lower bound to estimate nodes. Roughtly, the search procedures that tries to prove optimality in CPO will use these relative and absolute optimality tolerances to avoid exploring node that does not lead to a sufficient improvement in the incumbent so that if optimality is proven, we ensure that it is up to the most restrictive of these two tolerances. 

Philippe