The Submodular Knapsack Polytope
Alper Atamturk (atamturkberkeley.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.
Entry Submitted: 07/23/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|