The master equality polyhedron with multiple rows

• 成果类型: Article
• 署名作者: Dash, Sanjeeb; Fukasawa, Ricardo; Guenluek, Oktay
• 署名单位: International Business Machines (IBM); IBM USA; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0384-4
• 发表日期: 2012
• 页码: 125-151
• 关键词: valid inequalities; facets

摘要

The master equality polyhedron (MEP) is a canonical set that generalizes the master cyclic group polyhedron (MCGP) of Gomory. We recently characterized a nontrivial polar for the MEP, i.e., a polyhedron T such that an inequality defines a nontrivial facet of the MEP if and only if its coefficient vector forms a vertex of T. In this paper, we study the MEP when it is defined by m > 1 rows. We define the notion of a polaroid, a set containing all nontrivial facet defining inequalities. We show how to use linear programming (LP) to efficiently solve the separation problem for the MEP when the polaroid has a compact polyhedral description. We obtain such descriptions via subadditivity conditions when m = 2 or m = 3 and, using LP duality, show how to efficiently optimize over the MEP. These results yield a pseudo-polynomial time LP-based algorithm to solve the problem min{cx : Ax = b, x >= o, x is an element of Z(n)} when A has at most three constraints. For the MCGP and the MEP defined by a single constraint, the notions of two-term subadditivity and valid inequalities for MEP are essentially equivalent. We show this is not true in the case of the MEP when m >= 3; In fact, we prove that subadditivity conditions with a sub-exponential number of terms do not imply validity. In particular, when m = 3, we show that four-term subadditivity conditions are necessary and sufficient for validity.