Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01067459
Contributor : Joël Quinqueton <>
Submitted on : Monday, October 15, 2018 - 1:18:24 PM
Last modification on : Monday, July 20, 2020 - 1:06:05 PM
Long-term archiving on: : Wednesday, January 16, 2019 - 2:41:14 PM

File

bhkkpqwcp2014.pdf
Files produced by the author(s)

Identifiers

Citation

Christian Bessière, 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⟩

Share

Metrics