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

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.