TITRE : Benders Decomposition for the Fixed-Charge Multicommodity Network Design Problem

CONFÉRENCIER : Alysson Machado Costa, HEC Montréal

DATE et ENDROIT : 14 janvier 2005, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Jean-François Cordeau (340-6278)

RÉSUMÉ : Network design problems concern the selection of arcs in a graph in order to satisfy, at minimum cost, some flow requirements. We deal with the Multicommodity Capacitated Fixed-Charge Network Design Problem, for which we propose a Benders decomposition method. The approach hierarchically makes the integer (arc selection) and continuous (flow) decisions, and iterates between them in order to obtain optimality. Several extensions to the standard Benders decomposition algorithm are suggested. In particular, we introduce a new lifting procedure for the cutset inequalities and a strategy for generating extra cuts during the solution of the linear relaxation of the problem. These extra cuts allow a significant reduction in the number of mixed-integer problems that need to be solved.