Optimization Online


Lagrangean Decomposition for Mean-Variance 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, focusing on the uncorrelated ellipsoidal uncertainty case, which corresponds to so-called mean-variance optimization. We present a branch and bound-algorithm for such problems that uses lower bounds obtained from Lagrangean decomposition. This approach allows to separate the uncertainty aspect in the objective function from the combinatorial structure of the feasible set. We devise a combinatorial algorithm for solving the unrestricted binary subproblem efficiently, while the underlying combinatorial optimization problem can be addressed by any black box-solver. An experimental evaluation shows that our approach clearly outperforms other methods for mean-variance optimization when applied to robust shortest path problems and to risk-averse capital budgeting problems arising in portfolio optimization.

Keywords: robust combinatorial optimization, mean-risk optimization, Lagrangean decomposition

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: technical report

Download: [PDF]

Entry Submitted: 12/12/2013
Entry Accepted: 12/12/2013
Entry Last Modified: 12/13/2013

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