A polyhedral approach to the \textit{alldifferent} system (Q2429475)

This paper deals with the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The key concept of the analysis is based on a property, called inclusion property, pertinent to such a system. The authors present two families of inequalities and establish that they are facet-defining and completely describe the convex hull of an alldifferent system bearing the inclusion property. It is shown that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Under a technical condition, the reverse direction of this statement (i.e., if the convex hull is described by these families of inequalities then the inclusion property holds) is established for systems consisting of three predicates. For the systems for which the inclusion property does not hold, the authors have established another family of facet-defining inequalities and described a separation algorithm of polynomial complexity. All the separation algorithms are incorporated within a cutting-plane scheme. Experimentation, on a set of randomly generated alldifferent systems, has produced encouraging results as the integrality gap in most cases was considerably reduced.