Ambiguous chance-constrained binary programs under mean-covariance information

Yiling Zhang, Ruiwei Jiang, Siqian Shen

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satisfied probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. We further exploit the submodularity of 0-1 SOC constraints under special and general covariance matrices, and we utilize the submodularity as well as lifting to derive extended polymatroid inequalities to strengthen the 0-1 SOC formulations. We incorporate the valid inequalities in a branch-and-cut algorithm for efficiently solving DCBPs. We demonstrate the computational efficacy and solution performance using diverse instances of a chance-constrained bin packing problem.

Original languageEnglish (US)
Pages (from-to)2922-2944
Number of pages23
JournalSIAM Journal on Optimization
Volume28
Issue number4
DOIs
StatePublished - 2018
Externally publishedYes

Bibliographical note

Funding Information:
This research was supported by National Science Foundation grants CMMI-1433066 and CMMI-1662774. The authors are grateful to Profs. Alper Atamt and Andr'es G'omez for their comments on an earlier version of this paper and for bringing to our attention the works [2, 3, 7]. The authors are grateful to the two referees and the associate editor for their constructive comments and helpful suggestions.

Keywords

  • Bin packing
  • Chance-constrained binary program
  • Conic integer program
  • Distributionally robust optimization
  • Extended polymatroid
  • Submodularity

Fingerprint Dive into the research topics of 'Ambiguous chance-constrained binary programs under mean-covariance information'. Together they form a unique fingerprint.

Cite this