The balance constraint family - 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 : 2014

The balance constraint family

Résumé

The BALANCE constraint introduced by Beldiceanu ensures solutions are balanced. This is useful when, for example, there is a requirement for solutions to be fair. BALANCE bounds the difference B between the minimum and maximum number of occurrences of the values assigned to the variables. We show that achieving domain consistency on BALANCE is NP-hard. We therefore introduce a variant, BALANCE with a similar semantics that is only polynomial to propagate. We consider various forms of BALANCE and focus on ATMOSTBALANCE which achieves what is usually the main goal, namely constraining the upper bound on B.We provide a specialized propagation algorithm, and a powerful decomposition both of which run in low polynomial time. Experimental results demonstrate the promise of these new filtering methods.
Fichier non déposé

Dates et versions

hal-02743284 , version 1 (03-06-2020)

Identifiants

  • HAL Id : hal-02743284 , version 1
  • PRODINRA : 263231
  • WOS : 000345088200015

Citer

Christian Bessiere, Emmanuel Hébrard, George Katsirelos, Zeynep Kiziltan, Emilie Picard-Cantin, et al.. The balance constraint family. CP 2014 - 20th International Conference on Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. ⟨hal-02743284⟩
15 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More