A polyhedral approach to the \textit{alldifferent} system
This paper deals with the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The key concept of the analysis is based on a property, called inclusion property, pertinent to such a system. The authors present two families of inequalities and establish that they are facet-defining and completely describe the convex hull of an alldifferent system bearing the inclusion property. It is shown that they can be separated in polynomial time. Consequently, the inclusion property characterises a group of alldifferent systems for which the linear optimization problem (i.e. the problem of optimizing a linear function over that system) can be solved in polynomial time. Under a technical condition, the reverse direction of this statement (i.e., if the convex hull is described by these families of inequalities then the inclusion property holds) is established for systems consisting of three predicates. For the systems for which the inclusion property does not hold, the authors have established another family of facet-defining inequalities and described a separation algorithm of polynomial complexity. All the separation algorithms are incorporated within a cutting-plane scheme. Experimentation, on a set of randomly generated alldifferent systems, has produced encouraging results as the integrality gap in most cases was considerably reduced.
- On the facial structure of the alldifferent system
- Representations of the all\_different predicate of constraint satisfaction in integer programming
- On the system of the multiple all different predicates
- A short convex-hull proof for the all-different system with the inclusion property
- On the facets of the multiple alldifferent constraint
- Algorithms and Computation
- All-different polytopes
- Cost-based arc consistency for global cardinality constraints
- Embedding optimisation algorithms with Mosel
- scientific article; zbMATH DE number 2080319 (Why is no real title available?)
- scientific article; zbMATH DE number 1550909 (Why is no real title available?)
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Mixed logical-linear programming
- Neural network-based heuristic algorithms for hypergraph coloring problems with applications.
- On the system of two all different\(\_\)predicates
- On unions and dominants of polytopes
- Principles and Practice of Constraint Programming – CP 2004
- Representations of the all\_different predicate of constraint satisfaction in integer programming
- The ellipsoid method and its consequences in combinatorial optimization
- The Linear Programming Polytope of Binary Constraint Problems with Bounded Tree-Width
- The role of integer programming techniques in constraint programming's global constraints
- Tight representation of logical constraints as cardinality rules
- Transversal theory. An account of some aspects of combinatorial mathematics
- Constraint programming and operations research
- A short convex-hull proof for the all-different system with the inclusion property
- Graph coloring inequalities from all-different systems
- Submodularity and its application to some global constraints
- Matrices with lexicographically-ordered rows
- Projection, consistency, and George Boole
- Cardinality constraints and systems of restricted representatives
- Representations of the all\_different predicate of constraint satisfaction in integer programming
- On the facets of the multiple alldifferent constraint
- On the facial structure of the alldifferent system
- Polyhedral analysis and branch-and-cut for the structural analysis problem
- On the system of the multiple all different predicates
- Facets of the alldifferent-except-zero predicate
- Facets of multiple alldifferent predicates of size 2 arranged in a cycle
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
This page was built for publication: A polyhedral approach to the \textit{alldifferent} system
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429475)
