Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information

Krzysztof Postek, Ward Romeijnders, Dick den Hertog, Maartne H. van der Vlerk

Research output: Working paperDiscussion paperOther research output

207 Downloads (Pure)

Abstract

We consider decision making problems under uncertainty, assuming that only partial distributional information is available - as is often the case in practice. In such problems, the goal is to determine here-and-now decisions, which optimally balance deterministic immediate costs and worst-case expected future costs. These problems are challenging, since the worst-case distribution needs to be determined while the underlying problem is already a difficult multistage recourse problem. Moreover, as found in many applications, the model may contain integer variables in some or all stages. Applying a well-known result by Ben-Tal and Hochman (1972), we are able to efficiently solve such problems without integer variables, assuming only readily available distributional information on means and mean-absolute deviations. Moreover, we extend the result to the non-convex integer setting by means of convex approximations (see Romeijnders et al. (2016a)), proving corresponding performance bounds.
Our approach is straightforward to implement using of-the-shelf software as illustrated in our numerical experiments.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages48
Volume2016-039
Publication statusPublished - 22 Sep 2016

Publication series

NameCentER Discussion Paper
Volume2016-039

Fingerprint

Stochastic programming
Integer
Costs
Uncertainty
Deviation
Approximation
Numerical experiment
Software
Decision making

Keywords

  • robust
  • ambiguous
  • integer
  • recourse
  • stochastic
  • multi-stage

Cite this

Postek, K., Romeijnders, W., den Hertog, D., & van der Vlerk, M. H. (2016). Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information. (CentER Discussion Paper; Vol. 2016-039). Tilburg: Operations research.
Postek, Krzysztof ; Romeijnders, Ward ; den Hertog, Dick ; van der Vlerk, Maartne H. / Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information. Tilburg : Operations research, 2016. (CentER Discussion Paper).
@techreport{a03f895fb94141a984e0b257de5ca970,
title = "Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information",
abstract = "We consider decision making problems under uncertainty, assuming that only partial distributional information is available - as is often the case in practice. In such problems, the goal is to determine here-and-now decisions, which optimally balance deterministic immediate costs and worst-case expected future costs. These problems are challenging, since the worst-case distribution needs to be determined while the underlying problem is already a difficult multistage recourse problem. Moreover, as found in many applications, the model may contain integer variables in some or all stages. Applying a well-known result by Ben-Tal and Hochman (1972), we are able to efficiently solve such problems without integer variables, assuming only readily available distributional information on means and mean-absolute deviations. Moreover, we extend the result to the non-convex integer setting by means of convex approximations (see Romeijnders et al. (2016a)), proving corresponding performance bounds.Our approach is straightforward to implement using of-the-shelf software as illustrated in our numerical experiments.",
keywords = "robust, ambiguous, integer, recourse, stochastic, multi-stage",
author = "Krzysztof Postek and Ward Romeijnders and {den Hertog}, Dick and {van der Vlerk}, {Maartne H.}",
year = "2016",
month = "9",
day = "22",
language = "English",
volume = "2016-039",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Postek, K, Romeijnders, W, den Hertog, D & van der Vlerk, MH 2016 'Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information' CentER Discussion Paper, vol. 2016-039, Operations research, Tilburg.

Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information. / Postek, Krzysztof; Romeijnders, Ward; den Hertog, Dick; van der Vlerk, Maartne H.

Tilburg : Operations research, 2016. (CentER Discussion Paper; Vol. 2016-039).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information

AU - Postek, Krzysztof

AU - Romeijnders, Ward

AU - den Hertog, Dick

AU - van der Vlerk, Maartne H.

PY - 2016/9/22

Y1 - 2016/9/22

N2 - We consider decision making problems under uncertainty, assuming that only partial distributional information is available - as is often the case in practice. In such problems, the goal is to determine here-and-now decisions, which optimally balance deterministic immediate costs and worst-case expected future costs. These problems are challenging, since the worst-case distribution needs to be determined while the underlying problem is already a difficult multistage recourse problem. Moreover, as found in many applications, the model may contain integer variables in some or all stages. Applying a well-known result by Ben-Tal and Hochman (1972), we are able to efficiently solve such problems without integer variables, assuming only readily available distributional information on means and mean-absolute deviations. Moreover, we extend the result to the non-convex integer setting by means of convex approximations (see Romeijnders et al. (2016a)), proving corresponding performance bounds.Our approach is straightforward to implement using of-the-shelf software as illustrated in our numerical experiments.

AB - We consider decision making problems under uncertainty, assuming that only partial distributional information is available - as is often the case in practice. In such problems, the goal is to determine here-and-now decisions, which optimally balance deterministic immediate costs and worst-case expected future costs. These problems are challenging, since the worst-case distribution needs to be determined while the underlying problem is already a difficult multistage recourse problem. Moreover, as found in many applications, the model may contain integer variables in some or all stages. Applying a well-known result by Ben-Tal and Hochman (1972), we are able to efficiently solve such problems without integer variables, assuming only readily available distributional information on means and mean-absolute deviations. Moreover, we extend the result to the non-convex integer setting by means of convex approximations (see Romeijnders et al. (2016a)), proving corresponding performance bounds.Our approach is straightforward to implement using of-the-shelf software as illustrated in our numerical experiments.

KW - robust

KW - ambiguous

KW - integer

KW - recourse

KW - stochastic

KW - multi-stage

M3 - Discussion paper

VL - 2016-039

T3 - CentER Discussion Paper

BT - Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information

PB - Operations research

CY - Tilburg

ER -

Postek K, Romeijnders W, den Hertog D, van der Vlerk MH. Efficient Methods for Several Classes of Ambiguous Stochastic Programming Problems under Mean-MAD Information. Tilburg: Operations research. 2016 Sep 22. (CentER Discussion Paper).