Bounding the optimum of constraint optimization problems - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 1997

Bounding the optimum of constraint optimization problems


Solving constraint optimization problems is computationally so expensive that it is often impossible to provide a guaranteed optimal solution, either when the problem is too large, or when time is bounded. In these cases, local search algorithms usually provide good solutions. However, and even if an optimality proof is unreachable, it is often desirable to have some guarantee on the quality of the solution found, in order to decide if it is worthwile to spend more time on the problem. This paper is dedicated to the production of intervals, that bound as precisely as possible the optimum of Valued Constraint Satisfaction Problems (VCSP). Such intervals provide an upper bound on the distance of the best available solution to the optimum i.e., on the quality of the optimization performed. Experimental results on random VCSPs and real problems are given.
No file

Dates and versions

hal-02768589 , version 1 (04-06-2020)


  • HAL Id : hal-02768589 , version 1
  • PRODINRA : 135963


Simon de Givry, G. Verfaillie, Thomas Schiex. Bounding the optimum of constraint optimization problems. International Conference on Principles and Practice of Constraint Programming, 1997, Schloss Hagenberg, Austria. ⟨hal-02768589⟩
7 View
0 Download


Gmail Facebook X LinkedIn More