Optimization Online


Efficient approaches for the robust network loading problem

Sara Mattia (sara.mattia***at***iasi.cnr.it)
Michael Poss (mjposs***at***gmail.com)

Abstract: We consider the Robust Network Loading problem with splittable flows and demands that belong to the budgeted uncertainty set. We compare the optimal solution cost and computational cost of the problem when using static routing, volume routing, affine routing, and dynamic routing. For the first three routing types, we compare the compact formulation with a well-engineered Benders decomposition algorithm. For dynamic routing, we use a Benders-based reformulation to generate the extreme points of the uncertainty set on the fly within branch-and-cut algorithms. We test whether it is more efficient to incorporate the extreme points via Benders cuts or via flow variables and constraints, thus mimicking branch-and-cut-and-price algorithms. We test the effect of robust cutset inequalities for all models and algorithms. In addition, we introduce robust three-partition inequalities and show their effectiveness. Our computational experiments are realized on several realistic instances from SNDlib, including some instances based on historical traffic data.

Keywords: Robust network loading, budgeted uncertainty, benders decomposition, affine routing, dynamic routing

Category 1: Network Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Robust Optimization

Citation: October 2014

Download: [PDF]

Entry Submitted: 10/14/2014
Entry Accepted: 10/15/2014
Entry Last Modified: 07/13/2016

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