Skip to Main content Skip to Navigation
New interface
Conference papers

Bounding the optimum of constraint optimization problems

Abstract : 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.
Document type :
Conference papers
Complete list of metadata
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Thursday, June 4, 2020 - 10:37:05 AM
Last modification on : Friday, November 18, 2022 - 4:13:24 AM


  • 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⟩



Record views