Tractable approximations to a robust capacity assignment model in telecommunications under demand uncertainty

In a previous work, a min-max-min model has been proposed for robust capacity assignment in telecommunications where the demand is uncertain but belongs to a polyhedral set. As the problem appears hardly solvable, lower bounds and upper bounds computations have been proposed, but the latter were poor. It was then suggested that better upper bounds can be obtained using the so-called Affinely Adjustable Robust Counterpart (AARC) concept proposed by Ben-Tal et al. where the adjustable variables are restricted to depend affinely on the uncertain data. In this paper, we revisit this model from a dual perspective: Given an amount of traffic μ¯, we seek for an optimal link capacity assignment that, given an uncertainty set containing possible demand realizations, limits the loss of traffic to μ¯ in any realization of the demand. Our motivation is mainly computational, borrowing ingredients from earlier works and the AARC approach. We propose four tractable approximations to this problem and conduct some numerical experiments to compare them.