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.
all_different predicate constraint satisfaction facets convex hull constraint logic programming