Originally posted by: pimvdb

Hello,

I am experiencing a peculiarity in CP Optimizer where the solver concludes optimality even though the lower and upper bounds are not equal. In fact, there is an example of this in the User's Manual (p.77):
https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.studio.help/pdf/usrcpoptimizer.pdf
Here, the objective of 4 is proven optimal with a lower bound of 0. The User's Manual doesn't seem to elaborate on this.
I was wondering if one can assume that the final objective, if claimed optimal, is also a lower bound. If so, does the (smaller) lower bound have any particular meaning?

Thanks.

Originally posted by: Philippe_Refalo

Hi,

In CP 12.8 we display the lower bound that we were able to compute with inferences. The optimality is proven by failling to find a solution having an objective value better than the best found so far taking into account optimality tolerances (relative and optimal). See https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.8.0/ilog.odms.cpo.help/CP_Optimizer/User_manual/topics/search_settingParams.html

These two tolerances are used to compute the effective tolerance displayed at the end of the log. For instance:
Best objective : 4 (optimal - effective tol. is 0)

The effective tolerance can in turn be used to compute a lower bound.  So, no the final objective value is not the lower bound when proving optimality. In a minimization problem, the lower bound is equal to (objective value of the incumbent) - (effective tolerance). All this is not obvious and we will clearly display this lower bound in a future version.

Regards,

Philippe