Session MA11 - Conception de réseaux I / Network Design I
Day Monday, May 7, 2007 Room Trudeau Corporation Chair Mervat Chouman
Presentations
|
10h30 AM- 10h55 AM |
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 AM- 11h20 AM |
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 AM- 11h45 AM |
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. |