An Introduction to Two-Stage Stochastic Mixed-Integer Programming

Simge Kucukyavuz, Suvrajeet Sen

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

This paper provides an introduction to algorithms for two-stage stochastic mixed-integer programs. Our focus is on methods that decompose the problem by scenarios representing randomness in the problem data. The design of these algorithms depends on where the uncertainty appears (right-hand side, recourse matrix, or technology matrix) and where the continuous and discrete decision variables are (first stage or second stage). In addition, we provide computational evidence that, similar to other classes of stochastic programming problems, decomposition methods can provide desirable theoretical properties (such as finite convergence) as well as enhanced computational performance when compared with solving a deterministic equivalent formulation using an advanced commercial mixed-integer programming solver.
Original languageEnglish (US)
Title of host publicationINFORMS TutORials in Operations Research
EditorsRajan Batta, Jiming Peng
Pages1-27
Number of pages27
StatePublished - Sep 2017

Fingerprint

Integer programming
Stochastic programming
Decomposition
Uncertainty

Cite this

Kucukyavuz, S., & Sen, S. (2017). An Introduction to Two-Stage Stochastic Mixed-Integer Programming. In R. Batta, & J. Peng (Eds.), INFORMS TutORials in Operations Research (pp. 1-27)
Kucukyavuz, Simge ; Sen, Suvrajeet. / An Introduction to Two-Stage Stochastic Mixed-Integer Programming. INFORMS TutORials in Operations Research. editor / Rajan Batta ; Jiming Peng. 2017. pp. 1-27
@inbook{f059060eb9244575a152f405b1a4758a,
title = "An Introduction to Two-Stage Stochastic Mixed-Integer Programming",
abstract = "This paper provides an introduction to algorithms for two-stage stochastic mixed-integer programs. Our focus is on methods that decompose the problem by scenarios representing randomness in the problem data. The design of these algorithms depends on where the uncertainty appears (right-hand side, recourse matrix, or technology matrix) and where the continuous and discrete decision variables are (first stage or second stage). In addition, we provide computational evidence that, similar to other classes of stochastic programming problems, decomposition methods can provide desirable theoretical properties (such as finite convergence) as well as enhanced computational performance when compared with solving a deterministic equivalent formulation using an advanced commercial mixed-integer programming solver.",
author = "Simge Kucukyavuz and Suvrajeet Sen",
note = "https://doi.org/10.1287/educ.2017.0171",
year = "2017",
month = "9",
language = "English (US)",
isbn = "978-0990615309",
pages = "1--27",
editor = "Rajan Batta and Jiming Peng",
booktitle = "INFORMS TutORials in Operations Research",

}

Kucukyavuz, S & Sen, S 2017, An Introduction to Two-Stage Stochastic Mixed-Integer Programming. in R Batta & J Peng (eds), INFORMS TutORials in Operations Research. pp. 1-27.

An Introduction to Two-Stage Stochastic Mixed-Integer Programming. / Kucukyavuz, Simge; Sen, Suvrajeet.

INFORMS TutORials in Operations Research. ed. / Rajan Batta; Jiming Peng. 2017. p. 1-27.

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - An Introduction to Two-Stage Stochastic Mixed-Integer Programming

AU - Kucukyavuz, Simge

AU - Sen, Suvrajeet

N1 - https://doi.org/10.1287/educ.2017.0171

PY - 2017/9

Y1 - 2017/9

N2 - This paper provides an introduction to algorithms for two-stage stochastic mixed-integer programs. Our focus is on methods that decompose the problem by scenarios representing randomness in the problem data. The design of these algorithms depends on where the uncertainty appears (right-hand side, recourse matrix, or technology matrix) and where the continuous and discrete decision variables are (first stage or second stage). In addition, we provide computational evidence that, similar to other classes of stochastic programming problems, decomposition methods can provide desirable theoretical properties (such as finite convergence) as well as enhanced computational performance when compared with solving a deterministic equivalent formulation using an advanced commercial mixed-integer programming solver.

AB - This paper provides an introduction to algorithms for two-stage stochastic mixed-integer programs. Our focus is on methods that decompose the problem by scenarios representing randomness in the problem data. The design of these algorithms depends on where the uncertainty appears (right-hand side, recourse matrix, or technology matrix) and where the continuous and discrete decision variables are (first stage or second stage). In addition, we provide computational evidence that, similar to other classes of stochastic programming problems, decomposition methods can provide desirable theoretical properties (such as finite convergence) as well as enhanced computational performance when compared with solving a deterministic equivalent formulation using an advanced commercial mixed-integer programming solver.

M3 - Chapter

SN - 978-0990615309

SP - 1

EP - 27

BT - INFORMS TutORials in Operations Research

A2 - Batta, Rajan

A2 - Peng, Jiming

ER -

Kucukyavuz S, Sen S. An Introduction to Two-Stage Stochastic Mixed-Integer Programming. In Batta R, Peng J, editors, INFORMS TutORials in Operations Research. 2017. p. 1-27