Representations of the all_different Predicate of Constraint Satisfaction in Integer Programming

The use of predicates to state constraints in Constraint Satisfaction is explained. If, as an alternative, the traditional approach of Integer Programming (IP) is used, it is desirable to model these constraints so as to give as tight a linear programming relaxation as possible. One of the most commonly used predicates is the “all_different” predicate. Different applications of this are described together with different IP formulations. The facet defining constraints for the convex hull are then described and proved to be facet defining.