期刊
SIAM JOURNAL ON OPTIMIZATION
卷 24, 期 3, 页码 1485-1506出版社
SIAM PUBLICATIONS
DOI: 10.1137/130915315
关键词
stochastic programming; chance constraints; distributionally robust optimization; semidefinite programming; knapsack problem
资金
- CSC (China Scholarship Council)
- HADAMARD/PGMO grant
This paper considers a distributionally robust version of a quadratic knapsack problem. In this model, a subsets of items is selected to maximizes the total profit while requiring that a set of knapsack constraints be satisfied with high probability. In contrast to the stochastic programming version of this problem, we assume that only part of the information on random data is known, i.e., the first and second moment of the random variables, their joint support, and possibly an independence assumption. As for the binary constraints, special interest is given to the corresponding semidefinite programming (SDP) relaxation. While in the case that the model only has a single knapsack constraint we present an SDP reformulation for this relaxation, the case of multiple knapsack constraints is more challenging. Instead, two tractable methods are presented for providing upper and lower bounds (with its associated conservative solution) on the SDP relaxation. An extensive computational study is given to illustrate the tightness of these bounds and the value of the proposed distributionally robust approach.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据