On the polytope of the at-least-m-different predicate

Abstract

Constraint Programming (CP) is a method used to model and solve complex combinatorial problems. An alternative to Integer Programming for solving large-scale industrial problems, it is, under some circumstances, more efficient than IP, but its strength lies mainly in the use of predicates to model problems. This paper presents the at-least-$m$-different predicate and provides a class of facet-defining inequalities of the convex hull of integer solutions. This predicate bounds the number of values that variables in a set may receive. The paper also presents a polynomial-time separation algorithm to be used in the context of a branch-and-bound optimization approach.