The Submodular Knapsack Polytope

Alper Atamturk (atamturkberkeley.edu)
Vishnu Narayanan (vishnuieor.berkeley.edu)

Abstract: The submodular knapsack set is the discrete lower level set of a submodular function. The modular case reduces to the classical linear 0-1 knapsack set. One motivation for studying the submodular knapsack polytope is to address 0-1 programming problems with uncertain coefficients. Under various assumptions, a probabilistic constraint on 0-1 variables can be modeled as a submodular knapsack set. In this paper we describe cover inequalities for the submodular knapsack set and investigate their lifting problem. Each lifting problem is itself an optimization problem over a submodular knapsack set. We give sequence-independent upper and lower bounds on the valid lifting coefficients and show that whereas the upper bound can be computed in polynomial time, the lower bound problem is NP-hard. Furthermore, we present polynomial algorithms based on parametric linear programming and computational results for the conic quadratic 0-1 knapsack case.

Keywords: Conic integer programming; submodular functions; probabilistic knapsacks; branch-and-cut algorithms

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Robust Optimization

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Forthcoming in Discrete Optimization. Check http://www.ieor.berkeley.edu/~atamturk/ Research Report BCOL.08.03, IEOR, University of California-Berkeley. June 2008.

Download:

Entry Submitted: 07/23/2008
Entry Accepted: 07/23/2008
Entry Last Modified: 05/21/2009

Modify/Update this entry