A polyhedral approach to the alldifferent system

dc.contributor.author	Μάγος, Δημήτριος	el
dc.contributor.author	Μούρτος, Ιωάννης	el
dc.contributor.author	Appa, Gautam M.	en
dc.date.accessioned	2015-06-06T17:00:49Z
dc.date.available	2015-06-06T17:00:49Z
dc.date.issued	2015-06-06
dc.identifier.uri	http://hdl.handle.net/11400/15342
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ηνωμένες Πολιτείες	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/us/	*
dc.source	http://link.springer.com/journal/10107	en
dc.subject	Alldifferent predicate
dc.subject	Complexity
dc.subject	Convex hull
dc.subject	Separation
dc.subject	Διαφορικό κατηγόρημα
dc.subject	Πολυπλοκότητα
dc.subject	Κυρτό περίβλημα
dc.subject	Διαχωρισμός
dc.title	A polyhedral approach to the alldifferent system	en
heal.type	journalArticle
heal.classification	Computer science
heal.classification	Mathematics
heal.classification	Πληροφορική
heal.classification	Μαθηματικά
heal.classificationURI	http://skos.um.es/unescothes/C00750
heal.classificationURI	http://skos.um.es/unescothes/C02437
heal.classificationURI	N/A-Πληροφορική
heal.classificationURI	N/A-Μαθηματικά
heal.identifier.secondary	DOI: 10.1007/s10107-010-0390-6
heal.language	en
heal.access	campus
heal.recordProvider	Σχολή Τεχνολογικών Εφαρμογών. Τμήμα Μηχανικών Πληροφορικής Τ.Ε.	el
heal.publicationDate	2012-04
heal.bibliographicCitation	Magos, D., Mountos, I. and Appa, G. (2012) A polyhedral approach to the alldifferent system. "Mathematical Programming", 132 (1-2), p. 209-260. Available from: http://link.springer.com/article/10.1007%2Fs10107-010-0390-6 [Accessed: 06/06/2015].	en
heal.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.	en
heal.publisher	Shapiro, Alexander	en
heal.journalName	Mathematical Programming	en
heal.journalType	peer-reviewed
heal.fullTextAvailability	true