Distributionally robust stochastic knapsack problem

Jianqiang Cheng, Erick Delage, Abdel Lisser

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1485-1506
Number of pages22
JournalSIAM Journal on Optimization
Volume24
Issue number3
DOIs
StatePublished - 2014
Externally publishedYes

Keywords

  • Chance constraints
  • Distributionally robust optimization
  • Knapsack problem
  • Semidefinite programming
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Distributionally robust stochastic knapsack problem'. Together they form a unique fingerprint.

Cite this