Optimum Anytime Bounding for Constraint Optimization Problems

Simon de Givry and Girard Verfaillie

In this paper, we consider Constraint Optimization Problems in a Resource-Bounded context. We observe that both exact and approximate methods produce only an anytime upper bound of the optimum (in case of minimization). No lower bound, and thus no quality is available at run time. For a meta-reasoning system, it is difficult to reason on the basis of a so poor piece of information. Therefore, we discuss some ways of producing an anytime lower bound. In the Valued Constraint Saris]action Problem framework, we develop some of them, based on the complete solving of problem simplifications, and we present experimental results.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.