Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142298 | Operations Research Letters | 2015 | 5 Pages |
Abstract
An all-different constraint on some discrete variables imposes the condition that no two variables take the same value. A linear-inequality description of the convex hull of solutions to a system of all-different constraints is known under the so-called inclusion property: the convex hull is the intersection of the convex hulls of each of the all-different constraints of the system. We give a short proof of this result, which in addition shows the total dual integrality of the linear system.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Marco Di Summa,