Survavibility in Multilayer Networks: models and Polyhedra

Raouia Taktak

in Economics Thesis from University Paris Dauphine from Paris Dauphine University

Abstract: This thesis deals with a problem related to survivability issues in multilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, the aim is determine the corresponding survivable topology in the WDM layer. We show that the problem is NP-hard even for a single demand. Moreover, we propose four integer linear programming formulations for the problem. The first one is based on the so-called cut inequalities. We consider the polyhedron associated with the formulation. We identify several families of valid inequalities and discuss their facial aspect. We also develop separation routines. Using this, we devise a Branch-and-Cut algorithm and present experimental results. The second formulation uses paths between terminals of the underlying graph as variables. We devise a Branch-and-Price algorithm based on that formulation. In addition, we investigate a natural formulation for the problem which uses only the design variables. Finally, we propose an extended compact formulation which, in addition to the design variables, uses routing variables. We show that this formulation provides a tighter bound for the problem.

Keywords: Réseaux IP-Sur-WDM; Sécurisation; Complexité; Polytope; Facette; Algorithme de coupes et branchements; Algorithme de branchements et génération de colonnes; Formulation étendue; IP-Over-WDM networks; Survivability; Complexity; Facet; Branch-And-Cut algorithm; Branch-And-Price algorithm; Extended formulation (search for similar items in EconPapers)
JEL-codes: C44 C6 (search for similar items in EconPapers)
Date: 2013 Written 2013
Note: dissertation
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://basepub.dauphine.fr/xmlui/bitstream/123456789/15093/2/2013PA090076.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to basepub.dauphine.psl.eu:443 (Bad file descriptor) (http://basepub.dauphine.fr/xmlui/bitstream/123456789/15093/2/2013PA090076.pdf [301 Moved Permanently]--> https://basepub.dauphine.psl.eu/xmlui/bitstream/123456789/15093/2/2013PA090076.pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:dau:thesis:123456789/15093

Ordering information: This item can be ordered from
http://basepub.dauph ... ndle/123456789/15093

Access Statistics for this book

More books in Economics Thesis from University Paris Dauphine from Paris Dauphine University Contact information at EDIRC.
Bibliographic data for series maintained by Alexandre Faure ( this e-mail address is bad, please contact ).