A polyhedral approach to the alldifferent system

• 成果类型: Article
• 署名作者: Magos, D.; Mourtos, I.; Appa, G.
• 署名单位: University of West Attica; Athens University of Economics & Business; University of London; London School Economics & Political Science
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0390-6
• 发表日期: 2012
• 页码: 209-260
• 关键词: Constraint; polytope

摘要

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.