The convex hull of the all-different system with the inclusion property: a simple proof

Marco Di Summa ()
Additional contact information
Marco Di Summa: Dipartimento di Matematica, Università degli Studi di Padova, Italy

No 2013069, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: An all-different constraint for a given family of discrete variables imposes the condition that no two variables in the family are allowed to take the same value. Magos et al. [Mathematical Programming, 132 (2012), pp. 209–260] gave a linear-inequality description of the convex hull of solutions to a system of all-different constraints, under a special assumption called inclusion property. The convex hull of solutions is in this case the intersection of the convex hulls of each of the all-different constraints of the system. We give a short and simple proof of this result, that in addition shows the total dual integrality of the linear system.

Keywords: all-different constraint; convex hull; integral polyhedron; total dual integrality (search for similar items in EconPapers)
JEL-codes: C10 (search for similar items in EconPapers)
Date: 2013-12-31
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2013.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2013069

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().