Sanjeeb Dash, Oktay Günlük
SIAM Journal on Optimization
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 ≥ 0 x ∈ ℤ 2} 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. © 2010 Springer and Mathematical Programming Society.
Sanjeeb Dash, Oktay Günlük
SIAM Journal on Optimization
Rui Chen, Sanjeeb Dash, et al.
Discrete Optimization
Sanjeeb Dash, Oktay Günlük
Mathematical Programming
Sanjeeb Dash, Oktay Günlük, et al.
NeurIPS 2018