Record Details

The submodular knapsack polytope

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title The submodular knapsack polytope
 
Creator ATAMTURK, A
NARAYANAN, V
 
Subject programming approach
optimization
facets
risk
conic integer programming
submodular functions
probabilistic knapsacks
branch-and-cut algorithms
 
Description 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. (C) 2009
 
Publisher ELSEVIER SCIENCE BV
 
Date 2011-07-27T02:46:08Z
2011-12-26T12:53:11Z
2011-12-27T05:40:24Z
2011-07-27T02:46:08Z
2011-12-26T12:53:11Z
2011-12-27T05:40:24Z
2009
 
Type Article
 
Identifier DISCRETE OPTIMIZATION, 6(4), 333-344
1572-5286
http://dx.doi.org/10.1016/j.disopt.2009.03.002
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7088
http://hdl.handle.net/10054/7088
 
Language en