Robust Metric Inequalities for Network Loading Under Demand Uncertainty

Grit Claßen (), Arie M. C. A. Koster (), Manuel Kutschka () and Issam Tahiri ()
Additional contact information
Grit Claßen: RWTH Aachen University, Lehrstuhl II für Mathematik, Pontdriesch 14-16, 52062 Aachen, Germany
Arie M. C. A. Koster: RWTH Aachen University, Lehrstuhl II für Mathematik, Pontdriesch 14-16, 52062 Aachen, Germany
Manuel Kutschka: INFORM GmbH, Aviation Division, Pascalstraße 35, 52076 Aachen, Germany
Issam Tahiri: Université Bordeaux, Institut de Mathématiques de Bordeaux, 351, Cours de la Libération 33405 Talence Cedex, France

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 05, 1-27

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 potential of (tight) robust metric inequalities by considering the integrality gaps at the root node and the overall optimality gaps. Average speed-up factors between 2 and 5 for the compact flow and between 3 and 25 for the capacity formulation in the case of mid-sized instances have been achieved by exploiting robust metric inequalities in the solving process.

Keywords: Metric inequalities; network loading; robust optimization; capacity formulation (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500384
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:32:y:2015:i:05:n:s0217595915500384

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500384

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().