Optimization Online


A Lagrangean Decomposition Approach for Robust Combinatorial Optimization

Frank Baumann(frank.baumann***at***tu-dortmund.de)
Christoph Buchheim(christoph.buchheim***at***tu-dortmund.de)
Anna Ilyina(anna.ilyina***at***tu-dortmund.de)

Abstract: We address robust versions of combinatorial optimization problems, specializing on the discrete scenario case and the uncorrelated ellipsoidal uncertainty case. We present a branch and bound-algorithm for the min-max variant of these problems which uses lower bounds obtained from Lagrangean decomposition, allowing to separate the uncertainty aspect in the objective function from the combinatorial structure of the feasible set. For addressing the unrestricted binary subproblems arising in the uncorrelated ellipsoidal uncertainty case and in the twoscenario case, we devise fast combinatorial algorithms, where in the latter case we resort to solving a relaxation of the problem. In an extensive experimental evaluation we apply this approach to the robust versions of knapsack, shortest path, and minimum spanning tree problems. The results show that our approach clearly outperforms other solution methods in the uncorrelated ellipsoidal uncertainty case, as well as in the twoscenario case when the underlying problem is not given by a compact linear description.

Keywords: Robust combinatorial optimization, ellipsoidal uncertainty, discrete scenarios, Lagrangean decomposition

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 07/31/2014
Entry Accepted: 07/31/2014
Entry Last Modified: 07/31/2014

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