“The Price of Robustness” by Bertsimas and Sim represented a breakthrough in the development of a tractable robust counterpart of a Linear Programming problem. However, the central assumptions that the deviation band of each uncertain parameter is single and that the uncertainty distribution is symmetric may be too limitative in practice. Experience indeed suggests that the deviations often distribute asymmetrically over the band. Breaking the band into multiple sub-bands thus looks advisable in order to get a higher modeling resolution. Surprisingly, though the idea of using multiple bands is not new, no theoretical study of a general multi-band model has yet been done. The aim of our investigations is to bridge such knowledge gap.

In this work, we study the robust counterpart of a Mixed-Integer Linear Programming Problem with uncertain coefficient matrix and we model the uncertainty through a multi-band set. Our main results are that i) the robust counterpart corresponds to a compact Linear Programming formulation and that ii) the separation of cuts imposing robustness can be operated efficiently by solving a min-cost flow problem. Moreover, we show additional results about domination among uncertainty scenarios, pure 0-1 Programs and probability bound of constraint violation. Finally, we present computational experiments on realistic network design instances.

REFERENCES

D. Bertsimas, M. Sim, The Price of Robustness, Operations Research, 52 (1), 35–53, 2004

C. Büsing, F. D'Andreagiovanni, New Results about Multi-band Uncertainty in Robust Optimization. Proceedings of SEA 2012, LNCS, vol. 7276, pp. 63-74. Springer, Heidelberg (2012)

C. Büsing, F. D'Andreagiovanni, Robust Optimization under Multi-band Uncertainty, submitted for publication (2012)