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 described together with different IP formulations. The facet defining constraints for the convex hull are then described and proved to be facet defining.
Original language | English |
---|---|
Pages (from-to) | 96-103 |
Number of pages | 8 |
Journal | INFORMS Journal on Computing |
Volume | 13 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 2001 |
Keywords
- All_different Predicate
- Constraint Logic Programming
- Constraint Satisfaction
- Convex Hull
- Facets
ASJC Scopus subject areas
- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research