Enhancing Pigeon-Hole based Encoding of Boolean Cardinality Constraints

Soukaina Hattad, Said Jabbour, Lakhdar Sais, Yakoub Salhi

2017

Abstract

In this paper, we propose to deal with the encoding of cardinality constraints ∑ni=1 xi ≥ b into conjunctive normal form. We consider the one proposed recently (Jabbour et al., 2014) based on pigeon-hole problem. Then, we show that even if the number of clauses of the CNF based encoding is in O(b x (n - b)),, the number of literals of resulting formula can be much more higher O(b(n-b)²)$. To decrease the complexity in terms of number of literals, we propose a compact representation of some clauses of the encoding. Our approach allows to have a quadratic encoding in terms of literals while maintaining the same complexity in terms of clauses and additional variables. An experimental evaluation is performed to show the competitiveness of the new encoding.

Paper Citation

in Harvard Style

Hattad S., Jabbour S., Sais L. and Salhi Y. (2017). Enhancing Pigeon-Hole based Encoding of Boolean Cardinality Constraints . In Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART, ISBN 978-989-758-220-2, pages 299-307. DOI: 10.5220/0006252502990307

in Bibtex Style

@conference{icaart17,
author={Soukaina Hattad and Said Jabbour and Lakhdar Sais and Yakoub Salhi},
title={Enhancing Pigeon-Hole based Encoding of Boolean Cardinality Constraints},
booktitle={Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,},
year={2017},
pages={299-307},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0006252502990307},
isbn={978-989-758-220-2},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 9th International Conference on Agents and Artificial Intelligence - Volume 2: ICAART,
TI - Enhancing Pigeon-Hole based Encoding of Boolean Cardinality Constraints
SN - 978-989-758-220-2
AU - Hattad S.
AU - Jabbour S.
AU - Sais L.
AU - Salhi Y.
PY - 2017
SP - 299
EP - 307
DO - 10.5220/0006252502990307