The Balance Constraint Family - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2014

The Balance Constraint Family

Abstract

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, AllBalance with a similar semantics that is only polynomial to propagate. We consider various forms of AllBalance and focus on AtMostallBalance 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 principal
Vignette du fichier
bhkkpqwcp2014.pdf (277.58 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01067459 , version 1 (15-10-2018)

Identifiers

Cite

Christian Bessiere, Emmanuel Hébrard, George Katsirelos, Zeynep Kiziltan, Emilie Picard-Cantin, et al.. The Balance Constraint Family. CP: Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. pp.174-189, ⟨10.1007/978-3-319-10428-7_15⟩. ⟨lirmm-01067459⟩
300 View
125 Download

Altmetric

Share

More