Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set

Krzysztof Postek, Dick den Hertog

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problem 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 also holds in the nonfixed 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 on splitting 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
Pages (from-to)553-574
JournalINFORMS Journal on Computing
Volume28
Issue number3
DOIs
Publication statusPublished - Jul 2016

Fingerprint

Budget control
Computational complexity
Uncertainty
Integer
Decision rules
Lot sizing
Manpower
Scenarios
Inventory management
Optimization problem
Methodology
Heuristics
Capital budgeting

Keywords

  • adjustable
  • decision rules
  • integer
  • multistage
  • robust optimization

Cite this

@article{402b404fc9d34ca0bd5150052b5a59be,
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 integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problem 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 thestatic robust problem. This also holds in the nonfixed 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 on splitting 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 theproposed approach.",
keywords = "adjustable, decision rules, integer, multistage, robust optimization",
author = "Krzysztof Postek and {den Hertog}, Dick",
year = "2016",
month = "7",
doi = "10.1287/ijoc.2016.0696",
language = "English",
volume = "28",
pages = "553--574",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set. / Postek, Krzysztof; den Hertog, Dick.

In: INFORMS Journal on Computing, Vol. 28, No. 3, 07.2016, p. 553-574.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set

AU - Postek, Krzysztof

AU - den Hertog, Dick

PY - 2016/7

Y1 - 2016/7

N2 - In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problem 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 thestatic robust problem. This also holds in the nonfixed 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 on splitting 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 theproposed approach.

AB - In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problem 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 thestatic robust problem. This also holds in the nonfixed 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 on splitting 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 theproposed approach.

KW - adjustable

KW - decision rules

KW - integer

KW - multistage

KW - robust optimization

U2 - 10.1287/ijoc.2016.0696

DO - 10.1287/ijoc.2016.0696

M3 - Article

VL - 28

SP - 553

EP - 574

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 3

ER -