Facet-inducing inequalities of the convex hull of integer solutions satisfying the comb structure of the multiple- alldifferent predicate

One of the strengths of constraint programming, as contrasted with integer programming, lies in the use of predicates, or constraints, on a few variables to model large and varied problem structure. One of the most important predicates is the alldifferent predicates as it has wide applications in several different fields. In this dissertation, a generalization of the alldifferent predicate is analyzed from a polyhedral standpoint. This generalization is known as the multiple- alldifferent predicate or the k- alldifferent predicate where k≥2. In this case, several alldifferent predicates, whose sets of variables need not be disjoint, must be satisfied simultaneously. This predicates has numerous applications such as machine scheduling and timetabling. Instances of substructures, referred to as comb structures, of the multiple- alldifferent predicate are defined and characterized. Two classes of facet-inducing inequalities of the convex hull of feasible integer solutions are given. Experimental results based on these facet-inducing inequalities in a hybrid constraint programming-integer programming solver are given. The interactions between search in constraint programming and the linear programming relaxation of integer programming are exploited to prune variable domains and to provide bounds on the objective function, which cannot be easily achieved by either technique on its own.