Optimization Online


Robust Metric Inequalities for the Γ-Robust Network Loading Problem

Grit Claßen(classen***at***math2.rwth-aachen.de)
Arie M.C.A. Koster(koster***at***math2.rwth-aachen.de)
Manuel Kutschka(kutschka***at***math2.rwth-aachen.de)
Issam Tahiri(issam.tahiri***at***inria.fr)

Abstract: In this paper, we consider the network loading problem under demand uncertainties with static routing, i.e, a single routing scheme based on the fraction of the demands has to be determined. We generalize the class of metric inequalities to the Γ-robust setting and show that they yield a formulation in the capacity space. We describe a polynomial time exact algorithm to separate violated robust metric inequalities as model constraints. Moreover, rounded and tight robust metric inequalities describing the convex hull of integer solutions are presented and separated in a cut-and-branch approach. Computational results using real-life telecommunication data demonstrate the major potential of (tight) robust metric inequalities by considering the integrality gaps at the root node and the overall optimality gaps. Speed-up factors between 2 and 5 for the compact flow and between 3 and 25 for the capacity formulation have been achieved by exploiting robust metric inequalities in the solving process.

Keywords: metric inequalities, network loading, robust optimization, capacity formulation

Category 1: Robust Optimization

Category 2: Network Optimization

Citation: Working paper

Download: [PDF]

Entry Submitted: 12/05/2012
Entry Accepted: 12/05/2012
Entry Last Modified: 12/05/2012

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