Retour

Séance MA11 - Conception de réseaux I / Network Design I

Jour lundi, le 7 mai 2007
Salle Trudeau Corporation
Président Mervat Chouman

Présentations

10h30-
10h55
Lagrangean Decomposition for the Multicommodity Capacitated Network Design Problem
  Tolga Bektas, Université de Montréal, CRT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Teodor Gabriel Crainic, Université du Québec à Montréal et CRT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Bernard Gendron, Université de Montréal, CRT

Traditional Lagrangean relaxations for the multicommodity capacitated network design problem (MCNDP) involve dualizing either arc capacity or flow conservation constraints. The former (shortest-path relaxation) results in loosing the capacity structure whereas the latter (knapsack relaxation) does not maintain any information related to the network structure. In this talk, we discuss a new relaxation for the MCNDP, based on Lagrangean decomposition, which allows one to decompose the problem by nodes, and the subproblems partially preserve both the network and the capacity structure.


10h55-
11h20
Multicommodity Network Design with Hop Constraints
  Babacar Thiongane, HEC Montréal, ISCI (Senegal) and CRT
Jean-François Cordeau, GERAD, HEC Montréal et CRT, Chaire de recherche du Canada en distributique, 3000, chemin de la Côte-Sainte-Catherine, Montréal, Québec, Canada, H3T 2A7
Bernard Gendron, Université de Montréal, CRT

We consider the multicommodity network design problem in which demands have to be satisfied through a single path, where hop constraints are added, i.e. the length of a path for commodity k has to be lower or equal to a given value. Many formulations are compared in terms on their linear relaxation value and computational results are presented.


11h20-
11h45
A Lagrangian-Based Branch-and-Cut Algorithm for Multicommodity Capacitated Fixed Charge Network Design
  Mervat Chouman, Université de Montréal, CRT et Informatique et recherche opérationnelle, C.P. 6128, Succ. Centre-ville, Montréal, Québec, H3C 3J7
Teodor Gabriel Crainic, Université du Québec à Montréal et CRT, C.P. 6128, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3J7
Bernard Gendron, Université de Montréal, CRT

We present a Branch-and-Cut algorithm to solve the multicommodity capacitated fixed charge network design problem. The algorithm is based on a cutting-plane method that incorporates special implementations of well-known cutset-based valid inequalities. Instead of performing this cutting-plane at every node of the B&C tree, which is computationally too heavy, we solve Lagrangian subproblems to perform variable fixing, generate local cuts, and derive branching rules.


Retour