Optimization Online


Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information

Yiling Zhang (zyiling***at***umich.edu)
Ruiwei Jiang (ruiwei***at***umich.edu)
Siqian Shen (siqian***at***umich.edu)

Abstract: We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satis ed 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 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.

Keywords: chance-constrained binary program; distributionally robust optimization; conic integer program; submodularity; extended polymatroid

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 3: Integer Programming (0-1 Programming )


Download: [PDF]

Entry Submitted: 09/30/2016
Entry Accepted: 09/30/2016
Entry Last Modified: 06/12/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society