On mixing sets arising in chance-constrained programming

Simge Küçükyavuz*

*Corresponding author for this work

Research output: Contribution to journalArticle

58 Scopus citations

Abstract

The mixing set with a knapsack constraint arises in deterministic equivalent of chance-constrained programming problems with finite discrete distributions. We first consider the case that the chance-constrained program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set with a knapsack constraint. In addition, we propose a compact extended reformulation (with polynomial number of variables and constraints) that characterizes a linear programming equivalent of a single chance constraint with equal scenario probabilities. We introduce a blending procedure to find valid inequalities for intersection of multiple mixing sets. We propose a polynomial-size extended formulation for the intersection of multiple mixing sets with a knapsack constraint that is stronger than the original mixing formulation. We also give a compact extended linear program for the intersection of multiple mixing sets and a cardinality constraint for a special case. We illustrate the effectiveness of the proposed inequalities in our computational experiments with probabilistic lot-sizing problems.

Original languageEnglish (US)
Pages (from-to)31-56
Number of pages26
JournalMathematical Programming
Volume132
Issue number1-2
DOIs
StatePublished - Apr 1 2012

Keywords

  • Chance constraints
  • Compact extended formulations
  • Computation
  • Facets
  • Lot-sizing
  • Mixed-integer programming

ASJC Scopus subject areas

  • Mathematics(all)
  • Software

Fingerprint Dive into the research topics of 'On mixing sets arising in chance-constrained programming'. Together they form a unique fingerprint.

Cite this