Bounding the optimum of constraint optimization problems - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement
Communication Dans Un Congrès Année : 1997

Bounding the optimum of constraint optimization problems

Résumé

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.
Fichier non déposé

Dates et versions

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

Identifiants

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

Citer

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⟩
10 Consultations
0 Téléchargements

Partager

More