Optimization Online


Inexact cutting planes for two-stage mixed-integer stochastic programs

Ward Romeijnders(w.romeijnders***at***rug.nl)
Niels van der Laan(n.van.der.laan***at***rug.nl)

Abstract: We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs. Instead of using cutting planes that are always valid, our idea is to apply inexact 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 ane in the rst-stage decision variables, so that the approximation is convex, and can be solved eciently using techniques from convex optimization. We derive performance guarantees for using particular types of inexact cutting planes for simple integer recourse models. Moreover, we show in general that using inexact cutting planes leads to good rst-stage solutions if the total variations of the probability density functions of the random variables in the model are small enough.

Keywords: stochastic programming, integer programming, cutting plane techniques, convex approximations

Category 1: Stochastic Programming

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: October 2018 Groningen: University of Groningen, SOM research school, 36 p.(SOM Research Reports; vol. 2018013-OPERA)

Download: [PDF]

Entry Submitted: 10/23/2018
Entry Accepted: 10/23/2018
Entry Last Modified: 10/23/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