NDLI: A polyhedral approach to the alldifferent system

Content Provider	Springer Nature Link
Author	Mourtos, I. Magos, D. Appa, G.
Copyright Year	2010
Abstract	This paper examines the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The underlying analysis is based on a property, called inclusion, pertinent to such a system. For the alldifferent systems for which this property holds, we present two families of facet-defining inequalities, establish that they completely describe the convex hull and show 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. Furthermore, we establish that, for systems with three predicates, the inclusion property is also a necessary condition for the convex hull to be described by those two families of inequalities. For the alldifferent systems that do not possess that property, we establish another family of facet-defining inequalities and an accompanied polynomial-time separation algorithm. All the separation algorithms are incorporated within a cutting-plane scheme and computational experience on a set of randomly generated instances is reported. In concluding, we show that the pertinence of the inclusion property can be decided in polynomial time.
Ending Page	260
Page Count	52
Starting Page	209
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	132
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-07-14
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Separation Theoretical, Mathematical and Computational Physics Combinatorial optimization Complexity Programming involving graphs or networks Integer programming Convex hull Mathematical Methods in Physics alldifferent predicate Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Combinatorics Polyhedral combinatorics, branch-and-bound, branch-and-cut
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On the Facial Structure of the Alldifferent System

Uncapacitated lot sizing with backlogging: the convex hull

The convex recoloring problem: polyhedra, facets and computational experiments

Some properties of convex hulls of integer points contained in general convex sets

A large class of facets for the K-median polytope

Conic mixed-integer rounding cuts

Unbounded convex sets for non-convex mixed-integer quadratic programming

Polyhedral results and a Branch-and-cut algorithm for the $$k$$ -cardinality tree problem

The two-level diameter constrained spanning tree problem

A polyhedral approach to the alldifferent system

Similar Documents

On the Facial Structure of the Alldifferent System

Uncapacitated lot sizing with backlogging: the convex hull

The convex recoloring problem: polyhedra, facets and computational experiments

Some properties of convex hulls of integer points contained in general convex sets

A large class of facets for the K-median polytope

Conic mixed-integer rounding cuts

Unbounded convex sets for non-convex mixed-integer quadratic programming

Polyhedral results and a Branch-and-cut algorithm for the $$k$$ -cardinality tree problem

The two-level diameter constrained spanning tree problem

A polyhedral approach to the alldifferent system