Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées
Déposant : Migration Prodinra <>
Soumis le : jeudi 4 juin 2020 - 10:37:05
Dernière modification le : lundi 21 septembre 2020 - 19:32:01


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



Consultations de la notice