Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set

K.S. Postek, D. den Hertog

Research output: Working paperDiscussion paperOther research output

513 Downloads (Pure)

Abstract

In this paper we propose a methodology for constructing decision rules for in-
teger and continuous decision variables in multiperiod robust linear optimization
problems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period decisions based on the revealed uncertain parameters. At the same time, the problem’s computational complexity stays at the same level as for the static robust problem. This holds also in the non-fixed recourse situation. In the fixed recourse situation our approach can be combined with linear decision rules for the continuous decision variables. We provide theoretical results how to split the uncertainty set by identifying sets of uncertain parameter scenarios to be divided for an improvement in the worst-case objective value. Based on this theory, we propose several splitting heuristics. Numerical examples entailing a capital budgeting and a lot sizing problem illustrate the advantages of the proposed approach.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages32
Volume2014-056
Publication statusPublished - 25 Sep 2014

Publication series

NameCentER Discussion Paper
Volume2014-056

Fingerprint

Budget control
Computational complexity
Uncertainty

Keywords

  • adjustable
  • decision rules
  • integer
  • multi-stage
  • robust optimization

Cite this

Postek, K. S., & den Hertog, D. (2014). Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set. (CentER Discussion Paper; Vol. 2014-056). Tilburg: Operations research.
Postek, K.S. ; den Hertog, D. / Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set. Tilburg : Operations research, 2014. (CentER Discussion Paper).
@techreport{8649012b1bb04d3483f1792d61863249,
title = "Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set",
abstract = "In this paper we propose a methodology for constructing decision rules for in-teger and continuous decision variables in multiperiod robust linear optimizationproblems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period decisions based on the revealed uncertain parameters. At the same time, the problem’s computational complexity stays at the same level as for the static robust problem. This holds also in the non-fixed recourse situation. In the fixed recourse situation our approach can be combined with linear decision rules for the continuous decision variables. We provide theoretical results how to split the uncertainty set by identifying sets of uncertain parameter scenarios to be divided for an improvement in the worst-case objective value. Based on this theory, we propose several splitting heuristics. Numerical examples entailing a capital budgeting and a lot sizing problem illustrate the advantages of the proposed approach.",
keywords = "adjustable, decision rules, integer, multi-stage, robust optimization",
author = "K.S. Postek and {den Hertog}, D.",
year = "2014",
month = "9",
day = "25",
language = "English",
volume = "2014-056",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

Postek, KS & den Hertog, D 2014 'Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set' CentER Discussion Paper, vol. 2014-056, Operations research, Tilburg.

Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set. / Postek, K.S.; den Hertog, D.

Tilburg : Operations research, 2014. (CentER Discussion Paper; Vol. 2014-056).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set

AU - Postek, K.S.

AU - den Hertog, D.

PY - 2014/9/25

Y1 - 2014/9/25

N2 - In this paper we propose a methodology for constructing decision rules for in-teger and continuous decision variables in multiperiod robust linear optimizationproblems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period decisions based on the revealed uncertain parameters. At the same time, the problem’s computational complexity stays at the same level as for the static robust problem. This holds also in the non-fixed recourse situation. In the fixed recourse situation our approach can be combined with linear decision rules for the continuous decision variables. We provide theoretical results how to split the uncertainty set by identifying sets of uncertain parameter scenarios to be divided for an improvement in the worst-case objective value. Based on this theory, we propose several splitting heuristics. Numerical examples entailing a capital budgeting and a lot sizing problem illustrate the advantages of the proposed approach.

AB - In this paper we propose a methodology for constructing decision rules for in-teger and continuous decision variables in multiperiod robust linear optimizationproblems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period decisions based on the revealed uncertain parameters. At the same time, the problem’s computational complexity stays at the same level as for the static robust problem. This holds also in the non-fixed recourse situation. In the fixed recourse situation our approach can be combined with linear decision rules for the continuous decision variables. We provide theoretical results how to split the uncertainty set by identifying sets of uncertain parameter scenarios to be divided for an improvement in the worst-case objective value. Based on this theory, we propose several splitting heuristics. Numerical examples entailing a capital budgeting and a lot sizing problem illustrate the advantages of the proposed approach.

KW - adjustable

KW - decision rules

KW - integer

KW - multi-stage

KW - robust optimization

M3 - Discussion paper

VL - 2014-056

T3 - CentER Discussion Paper

BT - Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set

PB - Operations research

CY - Tilburg

ER -

Postek KS, den Hertog D. Multi-stage Adjustable Robust Mixed-Integer Optimization via Iterative Splitting of the Uncertainty set. Tilburg: Operations research. 2014 Sep 25. (CentER Discussion Paper).