Anytime lower bounds for constraint violation minimization problems - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 1998

Anytime lower bounds for constraint violation minimization problems

Bertrand Cabon
  • Fonction : Auteur
  • PersonId : 1072176
Simon de Givry

Résumé

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.

Dates et versions

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

Identifiants

Citer

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⟩

Collections

ONERA INRAE
1 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More