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

33 Citations (Scopus)


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
Issue number2
Publication statusPublished - 1 Jan 2001


  • 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


Dive into the research topics of 'Representations of the all_different Predicate of Constraint Satisfaction in Integer Programming'. Together they form a unique fingerprint.

Cite this