Reformulations by Discretization for Piecewise Linear Integer Multicommodity Network Flow Problems

Bernard Gendron () and Luis Gouveia ()
Additional contact information
Bernard Gendron: Département d’informatique et de recherche opérationnelle, Université de Montréal, Montréal, Québec H3T 1J4, Canada; and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montréal, Québec H3C 3J7, Canada
Luis Gouveia: Department of Statistics and Operations Research–CMAFCIO, Faculdade de Ciencias da Universidade de Lisboa, 1749-016 Lisboa, Portugal

Transportation Science, 2017, vol. 51, issue 2, 629-649

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 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 cut-set 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 efficiency of the different modeling alternatives (flow disaggregation plus addition of cut-set inequalities with or without discretization), when used within the Lagrangian relaxation approach.

Keywords: multicommodity network flow problem; piecewise linear cost; reformulation; discretization; disaggregation; valid inequalities (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/trsc.2015.0634 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:51:y:2017:i:2:p:629-649

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().