CIISE Distinguished Seminar: Piecewise Linear Integer Multicommodity Network Flow Problems

Dr. Bernard Gendron,
Université de Montréal

Date: Nov. 28 (4:00 pm)
Location: EV3.309

Abstract

We consider the piecewise linear multicommodity network flow problem with the addition of a constraint specifying that the total flow on each arc must be an integer. This problem has many applications in transportation and logistics, where total flows might represent vehicles or containers filled with different products. We introduce formulations that exploit this integrality constraint by adapting to our problem a technique known as discretization that has been used to derive mixed-integer programming models for several combinatorial optimization problems. We enhance the discretized models either by adding valid inequalities derived from cutset inequalities or by using flow disaggregation techniques. Since the size of the formulations derived from discretization and flow disaggregation rapidly increases with problem dimensions, we develop an efficient and effective Lagrangian relaxation method to compute lower and upper bounds. We perform computational results on a large set of randomly generated instances that allow us to compare the relative effciency of the different modeling alternatives (addition of cutset inequalities with or without discretization, plus flow disaggregation), when used within the Lagrangian relaxation approach.

(Joint work with Luis Gouveia, DEIO-CIO, University of Lisbon)

Biography

Bernard Gendron is a Professor at the Département d’informatique et de recherche opérationelle, Université de Montréal, and Director, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT). His research interests focus on the optimization of logistics and transportation networks. He has held positions of Principal Scientist at ILOG, Paris, and of Visiting Professor at MIT, EPFL, Pisa, Nice-Sophia-Antipolis, Blaise-Pascal, Versailles and Valenciennes. He has served as Chair of the Canadian Operational Research Society (CORS), Chair of the Montreal Chapter of CORS, and Chair of the Section on Transportation Science & Logistics of INFORMS (the Institue for Operations Research and the Management Sciences). He was awarded the CORS Practice Prize (2004), the CORS Service Award (2006) and the CORS Merit Award (2010).