The goal of this work is to design a minimum cost resilient overlay network, where a data network is on top of a transport network. Two major challenges are addressed. On one hand, a single failure in the transport network causes multiple simultaneous failures; on the other, the multicommodity flow must respect integrality. | Yugoslav Journal of Operations Research 26 (2016), Number 3, 343–360 DOI: RESILIENT OVERLAY DESIGN IN DWDM SYSTEMS Cecilia PARODI Facultad de Ingenier´ıa, Universidad de la Republica–Uruguay ´ cparodi@ Franco ROBLEDO Facultad de Ingenier´ıa, Universidad de la Republica–Uruguay ´ frobledo@ Pablo ROMERO Facultad de Ingenier´ıa, Universidad de la Republica–Uruguay ´ promero@ Carlos E. TESTURI Facultad de Ingenier´ıa, Universidad de la Republica–Uruguay ´ ctesturi@ Received: July 2015 / Accepted: November 2015 Abstract: The goal of this work is to design a minimum cost resilient overlay network, where a data network is on top of a transport network. Two major challenges are addressed. On one hand, a single failure in the transport network causes multiple simultaneous failures; on the other, the multicommodity flow must respect integrality. An integer programming formulation is presented to design an overlay, meeting the previous constraints. We prove that the problem belongs to the class NP-Hard. Then, a decomposition approach is introduced, where the problem is solved in two steps by means of relaxations of the original formulation. Experiments carried out with real-life instances, coming from the Uruguayan telecommunication operator, show that the approach is competitive with respect to previous metaheuristics, to know, Tabu-Search (TS) and Variable Neighborhood Search (VNS). A modest percentage of cost-reduction is achieved in some instances, which means millionaire savings in practice. Keywords: Network Survivability, Network Optimization, Overlay. 344 C. Parodi, F. Robledo, P. Romero, C. Testuri / Optimal Flows in Overlay MSC: 68M10, 90B10, 90C10. 1. INTRODUCTION The increasing importance of the telecommunications services pushed most companies to deploy optical fiber networks. Since the volume requirements of the telephony service were low, the design process was guided by cost and .