Two-stage adaptive linear optimization: Faster computation and stronger bounds

D. Bertsimas, Frans de Ruiter

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. We show that the optimal primal affine policy can be directly obtained from
the optimal affine policy in the dual formulation. We provide empirical evidence that the dualized model in the context of two-stage lot-sizing on a network and two-stage facility location problems solves an order of magnitude faster than the primal formulation with affine policies. We also provide an explanation and associated empirical evidence that offer insight on which characteristics of the dualized formulation make computations faster. Furthermore, the affine policy of the dual formulations can be used to provide stronger lower bounds on the optimality of affine policies.
Original languageEnglish
Pages (from-to)500-511
JournalINFORMS Journal on Computing
Volume28
Issue number3
DOIs
Publication statusPublished - Jul 2016

Fingerprint

Empirical evidence
Optimization model
Uncertainty
Facility location
Duality
Location problem
Lot sizing
Lower bounds
Optimality

Keywords

  • two-stage problems
  • robust optimization
  • duality
  • affine control policies

Cite this

Bertsimas, D. ; de Ruiter, Frans. / Two-stage adaptive linear optimization : Faster computation and stronger bounds. In: INFORMS Journal on Computing. 2016 ; Vol. 28, No. 3. pp. 500-511.
@article{3e3be4c414b84d69afdc969ab606e576,
title = "Two-stage adaptive linear optimization: Faster computation and stronger bounds",
abstract = "In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. We show that the optimal primal affine policy can be directly obtained fromthe optimal affine policy in the dual formulation. We provide empirical evidence that the dualized model in the context of two-stage lot-sizing on a network and two-stage facility location problems solves an order of magnitude faster than the primal formulation with affine policies. We also provide an explanation and associated empirical evidence that offer insight on which characteristics of the dualized formulation make computations faster. Furthermore, the affine policy of the dual formulations can be used to provide stronger lower bounds on the optimality of affine policies.",
keywords = "two-stage problems, robust optimization, duality, affine control policies",
author = "D. Bertsimas and {de Ruiter}, Frans",
year = "2016",
month = "7",
doi = "10.1287/ijoc.2016.0689",
language = "English",
volume = "28",
pages = "500--511",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

Two-stage adaptive linear optimization : Faster computation and stronger bounds. / Bertsimas, D.; de Ruiter, Frans.

In: INFORMS Journal on Computing, Vol. 28, No. 3, 07.2016, p. 500-511.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Two-stage adaptive linear optimization

T2 - Faster computation and stronger bounds

AU - Bertsimas, D.

AU - de Ruiter, Frans

PY - 2016/7

Y1 - 2016/7

N2 - In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. We show that the optimal primal affine policy can be directly obtained fromthe optimal affine policy in the dual formulation. We provide empirical evidence that the dualized model in the context of two-stage lot-sizing on a network and two-stage facility location problems solves an order of magnitude faster than the primal formulation with affine policies. We also provide an explanation and associated empirical evidence that offer insight on which characteristics of the dualized formulation make computations faster. Furthermore, the affine policy of the dual formulations can be used to provide stronger lower bounds on the optimality of affine policies.

AB - In this paper we derive and exploit duality in general two-stage adaptive linear optimization models. The equivalent dualized formulation we derive is again a two-stage adaptive linear optimization model. Therefore, all existing solution approaches for two-stage adaptive models can be used to solve or approximate the dual formulation. The new dualized model differs from the primal formulation in its dimension and uses a different description of the uncertainty set. We show that the optimal primal affine policy can be directly obtained fromthe optimal affine policy in the dual formulation. We provide empirical evidence that the dualized model in the context of two-stage lot-sizing on a network and two-stage facility location problems solves an order of magnitude faster than the primal formulation with affine policies. We also provide an explanation and associated empirical evidence that offer insight on which characteristics of the dualized formulation make computations faster. Furthermore, the affine policy of the dual formulations can be used to provide stronger lower bounds on the optimality of affine policies.

KW - two-stage problems

KW - robust optimization

KW - duality

KW - affine control policies

U2 - 10.1287/ijoc.2016.0689

DO - 10.1287/ijoc.2016.0689

M3 - Article

VL - 28

SP - 500

EP - 511

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 3

ER -