A Lagrangian dual method for two-stage robust optimization with binary uncertainties

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

This paper presents a new exact method to calculate worst-case parameter realizations in two-stage robust optimization problems with categorical or binary-valued uncertain data. Traditional exact algorithms for these problems, notably Benders decomposition and column-and-constraint generation, compute worst-case parameter realizations by solving mixed-integer bilinear optimization subproblems. However, their numerical solution can be computationally expensive not only due to their resulting large size after reformulating the bilinear terms, but also because decision-independent bounds on their variables are typically unknown. We propose an alternative Lagrangian dual method that circumvents these difficulties and is readily integrated in either algorithm. We specialize the method to problems where the binary parameters switch on or off constraints as these are commonly encountered in applications, and discuss extensions to problems that lack relatively complete recourse and to those with integer recourse. Numerical experiments provide evidence of significant computational improvements over existing methods.

Original languageEnglish (US)
Pages (from-to)1831-1871
Number of pages41
JournalOptimization and Engineering
Volume23
Issue number4
DOIs
StatePublished - Dec 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Civil and Structural Engineering
  • Aerospace Engineering
  • Mechanical Engineering
  • Control and Optimization
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'A Lagrangian dual method for two-stage robust optimization with binary uncertainties'. Together they form a unique fingerprint.

Cite this