EFFICIENT APPROACHES FOR THE ROBUST NETWORK LOADING PROBLEM

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. 3