A. Ridha Mahjoub : Network Design and Polyhedra

A. Ridha Mahjoub
LAMSADE, Université Paris-Dauphine, Paris, France
mahjoub@lamsade.dauphine.fr

For the past few decades, combinatorial optimization techniques have shown to be powerful tools for formulating, analysing and solving problems arising from practical decision situations. In particular, polyhedral approaches have been successfully applied for many well known NP-hard problems. The equivalence between separation and optimization over a polyhedron has been behind a great evolution of these methods. The so-called « Branch and Cut » method, which is inspired from this equivalence, is now widely used for obtaining optimal and near-optimal solutions for hard combinatorial optimization problems. In this talk we will discuss applications of these techniques to some network design problems. In particular we will consider the so-called survivable network design problem. This has many real world applications (e.g. telecommunication and transportation networks, VLSI networks). A big amount of research has then been done for designing algorithmic approaches for that model. Network survivability means the ability to restore service in the event of a catastrophic failure of a network component, such as the complete loss of a link or the failure of a node. Service could be restored by routing traffic through other existing links and nodes, assuming that the network could provide additional connectivity. Designing a network meeting requirements concerning traffic survivability is now a major challenge with great economic impact. Survivability requirements are generally formulated in terms of network connectivity. We will first discuss some variants of this model and the related polyhedra. In particular, we will describe some classes of valid inequalities, which have shown to play an important role, and discuss their separation aspect.
Then we will consider network design problems when the routing paths have to be bounded. Connectivity requirements may not unfortunately be sufficient to guarantee a high routing quality in the network. Indeed, the alternative routing paths may be too long and so costly to be suitable. In order to limit the rerouting length, it is commonly required that the length of the paths between the origin-destinations is bounded by a given constant depending on technological parameters. So if a failure occurs, then the traffic can be rerouted through a bounded path. Integer programming formulations as well as cutting plane based algorithms will be discussed.
Finally some extensions related to dimensioning problems, when adequate capacities have to be installed in the network, will be considered.

A. Ridha Mahjoub is Classe Exceptionnelle Professor of Operations Research and Combinatorial Optimization at Université Paris-Dauphine, Paris, France. He is also member of the LAMSADE laboratory, CNRS. Previous positions include full professor at the University of Brest, France, from 1991 to 1998 and the University of Clermont-Ferrand, France, from 1998 to 2007. Professor Mahjoub holds an undergraduate degree in Mathematics from University of Tunis, Tunisia and a Ph.D. and a Thèse d’Etat in Operations Research and Combinatorial Optimization from the University of Grenoble, France. His research areas include the theory and applications of polyhedral approaches for modeling, analysing and solving large NP-hard combinatorial optimization problems, mixed integer programming as well as complexity and graph theory. A part of his research has recently focused on the design of cutting plane algorithms for network design problems. Professor Mahjoub is author and co-author of several papers that have appeared in leading journals such as Mathematical Programming, Mathematics of Operations Research, SIAM Journal on Discrete Mathematics, Discrete Mathematics, Discrete Applied Mathematics, Discrete Optimization, Informs Journal on Computing, Operations Research letters and Networks. He served as co-director of the Mathematics and Computer Science Department at Université Paris-Dauphine between 2008 and 2013. Dr Mahjoub edited and co-edited books and several special issues of journals. He currently serves as Editor-in-Chief of the international journal RAIRO-Operations Research and Associate Editor of Computers and Industrial Engineering.