Representations of the all_different Predicate of Constraint Satisfaction in Integer Programming

H. P. Williams, Hong Yan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

31 Citations (Scopus)

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 languageEnglish
Pages (from-to)96-103
Number of pages8
JournalINFORMS Journal on Computing
Volume13
Issue number2
DOIs
Publication statusPublished - 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

Cite this