Séance TB5 - Théorie des graphes II / Graph Theory II
Jour mardi, le 8 mai 2007 Salle Dutailier International Président Johannes O. Royset
Présentations
|
13h30- 13h55 |
Lagrangian Relaxation and Enumeration for Solving Constrained Shortest-Path Problems |
|
Johannes O. Royset, Naval Postgraduate School, Operations Research Department, Monterey, CA, USA, 93943 W. Matthew Carlyle, Naval Postgraduate School, Operations Research Department, Monterey, CA, USA, 93943 R. Kevin Wood, Naval Postgraduate School, Operations Research Department, Monterey, CA, USA, 93943 We construct an algorithm for solving the constrained shortest-path problem based on Lagrangian relaxation, path enumeration, and network reduction. The network reduction procedure eliminates edges that cannot lie on any optimal path. Networks with a hundred thousand edges are typically solved in minutes. The algorithm is competitive with a label-setting algorithm. |
|
13h55- 14h20 |
Minimum Cost Degree Constrained Spanning Trees with Node-Degree Costs |
|
Luis Gouveia, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, Cidade Universitaria Bloco C6 Piso 4, Campo Grande, Lisboa, Portugal, 1749-016 Christophe Duhamel, Université Blaise Pascal, LIMOS, ISIMA, campus des Cézeaux, Clermont-Ferrand, France, 63173 Pedro Moura, Universidade de Lisboa, DEIO-CIO Faculdade de Ciências, Lisboa, Portugal Mauricio Souza, Universidade Federal de Minas Gerais - UFMG, Engenharia de Produção, Belo Horizonte, Brazil The Node Degree Constrained Minimum Spanning Tree Problem (NDMSTP) consists in finding a minimal cost spanning tree satisfying the condition that every node has a degree no greater than a fixed value. Here we consider a variant where beside the edge costs, a concave cost function is associated to the degree of each node. We discuss several formulations based on discretization techniques and compare the corresponding linear programming relaxations. |