INFORMS journal on computing · 2001 · 50 citations · 12 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDiscrete MathematicsOptimizationCombinatorial OptimizationConstraint SatisfactionDiscrete OptimizationInteger ProgrammingLinear ProgrammingOptimization TheoryAll-different ConstraintConstraint Satisfaction ModelingConvex Hull FacetsFacet IdentificationInteger Programming ConstraintsInteger Programming ModelsInteger Programming Relaxations
Constraint satisfaction problems often express constraints via predicates, and for integer‑programming formulations it is important to model these predicates so that the linear‑programming relaxation is as tight as possible, especially for the widely used all_different predicate. The authors present several applications of the all_different predicate and describe corresponding integer‑programming formulations for each. They identify and prove that the facet‑defining constraints for the convex hull of the all_different predicate are indeed facet‑defining.
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.
12
Faces for a linear inequality in 0–1 variables
Laurence A. Wolsey · Mathematical Programming · 1975 · 303 citations
Facet of regular 0–1 polytopes
P. L. Hammer, E. L. Johnson, Uri N. Peled · Mathematical Programming · 1975 · 168 citations