Optimization Online


Oracle-Based Algorithms for Binary Two-Stage Robust Optimization

Nicolas Kämmerling (kaemmerling***at***itl.tu-dortmund.de)
Jannis Kurtz (kurtz***at***mathc.rwth-aachen.de)

Abstract: In this work we study binary two-stage robust optimization problems with objective uncertainty. The concept of two-stage robustness is tailored for problems under uncertainty which have two different kinds of decision variables, first-stage decisions which have to be made here-and-now and second-stage decisions which can be determined each time after an uncertain scenario occured. We adapt an oracle-based algorithm, originally introduced to solve binary min-max-min robust optimization problems, to efficiently calculate lower bounds for the binary two-stage robust problem by using an oracle for the underlying deterministic problem. We show that the latter lower bound can be implemented in a branch & bound procedure, where the branching is performed only over the first-stage decision variables. Additionally we show that the same procedure can be extended for non-linear binary problems which can be linearized. As an alternative solution method we apply a famous column-and-constraint generation algorithm to the binary two-stage robust problem with objective uncertainty. We test both algorithms on benchmark instances of the uncapacitated single-allocation hub-location problem, which is classically modeled by a quadratic binary formulation and show that the branch & bound procedure outperforms the column-and-constraint generation algorithm.


Category 1: Robust Optimization

Category 2: Integer Programming (0-1 Programming )

Category 3: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 05/13/2019
Entry Accepted: 05/13/2019
Entry Last Modified: 05/20/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society