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, CORE Discussion Papers from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)
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)
References: View references in EconPapers View complete reference list from CitEc
Citations Track citations by RSS feed
Downloads: (external link)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2013069
Access Statistics for this paper
More papers in CORE Discussion Papers 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 ().