Representatons of the all_different predicate of constraint satisfaction in integer programming

Representatons of the all_different predicate of constraint satisfaction in integer programming

0.00 Avg rating0 Votes
Article ID: iaor20032978
Country: United States
Volume: 13
Issue: 2
Start Page Number: 96
End Page Number: 103
Publication Date: Apr 2001
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: constraint programming
Abstract:

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 decribed together with different IP formulations. The facet defining constraints for the convex hull are then described and proved to be facet defining.

Reviews

Required fields are marked *. Your email address will not be published.