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.