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.

The Balance Constraint Family

KIZILTAN, ZEYNEP;
2014

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.
Proceedings of the 20th International Conference on Principles and Practice of Constraint Programming (CP’14)
174
189
C. Bessiere; E. Hebrard; G. Katsirelos; Z. Kiziltan; E. Picard-Cantin; C.-G. Quimper; T. Walsh
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/508971
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact