Article ID Journal Published Year Pages File Type
1142298 Operations Research Letters 2015 5 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,