Sanjeeb Dash

Title:
The general master knapsack polyhedron

Abstract:
We propose a generalization of Gomory's Master Cyclic Group Polyhedron
which we call the General Master Knapsack Polyhedron (GMKP). We give a compact
dual description of the facets of this polyhedron, by giving a polynomial
set of inequalities whose extreme points are the nontrivial facets of the
GMKP. This result generalizes similar results of Gomory (1969) and Araoz.
Our dual description yields a polynomial time algorithm to separate over
the GMKP, and yields a pseudo-polynomial algorithm to separate over the
convex hull of solutions of a knapsack problem with positive and
negative constraint coefficients and no upper bounds on variables.