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

Anytime lower bounds for constraint violation minimization problems

Abstract : Constraint Violation Minimization Problems arise when dealing with over-constrained CSPs. Unfortunately, experiments and practice show that they quickly become too large and too difficult to be optimally solved. In this context, multiple methods (limited tree search, heuristic or stochastic local search) are available to produce non-optimal, but good quality solutions, and thus to provide the user with anytime upper bounds of the problem optimum. On the other hand, few methods are available to produce anytime lower bounds of this optimum. In this paper, we explore some ways of producing such bounds. All of them are algorithmic variants of a Branch and Bound search. More specifically, we show that a new algorithm, resulting from a combination of the Russian Doll Search and Iterative Deepening algorithms, clearly outperforms five known algorithms and allows high lower bounds to be rapidly produced.
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 - 11:55:34
Dernière modification le : mercredi 14 octobre 2020 - 03:56:34

Lien texte intégral




Bertrand Cabon, Simon de Givry, Gérard Verfaillie. Anytime lower bounds for constraint violation minimization problems. 4th International Conference on Principles and Practice of Constraint Programming - CP 1998, Oct 1998, Pise, Italy. 15 p., ⟨10.1007/3-540-49481-2_10⟩. ⟨hal-02770666⟩



Consultations de la notice