Optimum Anytime Bounding for Constraint Optimization Problems
Simon de Givry · 1997
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 Satisfaction Problem framework, we develop some of them, based on the complete solving of problem simplifications, and we present experimental results. Motivation There are some difficulties in considering constraint optimization problems within a resource bounded framework. Most of these problems are NP-hard. The worstcase time, which is needed to solve them optimally, grows exponentially with the size of the problem. The mean or the median time, which can be experimentally observed, is far lower than the worst...