A Polyhedral Study of the Alldifferent System
      - Dimitris Magos, Technological Educational Institute of Athens

    We establish that the facet-defining inequalities for the single alldifferent predicate are, under a technical condition, also facet-defining for any alldifferent system. Furthermore, we establish a property which provides a necessary and sufficient condition for those facets to define the convex hull of integer vectors satisfying such a system. We show that deciding whether that property holds for an arbitrary alldifferent system can be done in polynomial time. Also we present further classes of facet-defining inequalities when that property does not hold.

Last updated: November 7, 2009.