Pseudo-Valid Cutting Planes for Two-Stage Mixed-Integer Stochastic Programs with Right-Hand-Side Uncertainty

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
20 Downloads (Pure)

Abstract

We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs with uncertainty in the right-hand side. Instead of using cutting planes that are always valid, our idea is to apply pseudo-valid cutting planes to the second-stage feasible regions that may cut away feasible integer second-stage solutions for some scenarios and may be overly conservative for others. The advantage is that it allows us to use cutting planes that are affine in the first-stage decision variables, so that the approximation is convex and can be efficiently solved using techniques from convex optimization. We derive tight performance guarantees for using particular types of pseudo-valid cutting planes for simple integer recourse models. Moreover, we show in general that using pseudo-valid cutting planes leads to good first-stage solutions if the total variations of the one-dimensional conditional probability density functions of the random variables in the model converge to zero.
Original languageEnglish
Pages (from-to)1199-1217
Number of pages19
JournalOperations Research
Volume68
Issue number4
Early online date7-May-2020
DOIs
Publication statusPublished - 2020

Keywords

  • CONVEX APPROXIMATIONS
  • RECOURSE MODELS
  • DECOMPOSITION ALGORITHMS
  • CUTS

Cite this