[en] In modeling real-world applications of network design, a difficulty often encountered is the fact that capacity on the arcs are not ”all-or-nothing” but incur a more complex cost. Often, the associated cost function can be approximated with a piecewise linear function (possibly non-convex). We review in this chapter some pioneering work of Bernard Gendron on multicommodity flow and network design problems with piecewise linear costs, and we also briefly address related recent works that build on the ideas developed by Bernard Gendron.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt ; Computer Science Department, Université libre de Bruxelles (ULB), Brussels, Belgium ; INRIA, Université de Lille, Lille, France
Gendron, Bernard; CIRRELT and DIRO, Université de Montréal, Montréal, Canada
Gouveia, Luis; Departamento de Estatística e Investigação Operacional, Faculdade de Ciências da Universidade de Lisboa and CMAFcIO - Centro de Matemática, Aplicações Fundamentais e Investigação Operacional, Lisbon, Portugal
Language :
English
Title :
Models for Network Flow and Network Design Problems with Piecewise Linear Costs
Publication date :
2024
Main work title :
International Series in Operations Research and Management Science
Balakrishnan, A., & Graves, S. C. (1989). A composite algorithm for a concave-cost network flow problem. Networks, 19(2), 175–202.
Correia, I., Gouveia, L., & Saldanha-da Gama, F. (2010). Discretized formulations for capacitated location problems with modular distribution costs. European Journal of Operational Research, 204(2), 237–244.
Croxton, K. L., Gendron, B., & Magnanti, T. L. (2003). A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. Management Science, 49(9), 1268–1273.
Croxton, K. L., Gendron, B., & Magnanti, T. L. (2007). Variable disaggregation in network flow problems with piecewise linear costs. Operations Research, 55(1), 146–157.
Fortz, B., & Thorup, M. (2000). Internet traffic engineering by optimizing ospf weights. In: INFO COM 2000. Nineteenth annual joint conference of the IEEE computer and communications societies. Proceedings (Vol. 2, pp. 519–528). IEEE.
Fortz, B., Gouveia, L., & Joyce-Moniz, M. (2017). Models for the piecewise linear unsplittable multicommodity flow problems. European Journal of Operational Research, 261(1), 30–42.
Frangioni, A., & Gendron, B. (2009). 0–1 reformulations of the multicommodity capacitated network design problem. Discrete Applied Mathematics 157(6), 1229–1241. Reformulation Techniques and Mathematical Programming.
Frangioni, A., & Gendron, B. (2021). Piecewise linear cost network design. In: T. G. Crainic, M. Gendreau, & B. Gendron (Eds.), Network design with applications to transportation and logistics (pp. 167–185). Springer International Publishing.
Gendron, B., & Gouveia, L. (2017). Reformulations by discretization for piecewise linear integer multicommodity network flow problems. Transportation Science, 51(2), 629–649.
Gouveia, L. (1995). A 2n constraint formulation for the capacitated minimal spanning tree problem. Operations Research, 43(1), 130–141.
Gouveia, L., & Saldanha-da Gama, F. (2006). On the capacitated concentrator location problem: a reformulation by discretization. Computers & Operations Research, 33(5), 1242–1258.
Gouveia, L., & Moura, P. (2012). Enhancing discretized formulations: the knapsack reformulation and the star reformulation. Top, 20, 52–74.
Murthy, R. V., & Helgason, R. V. (1994). A direct simplex algorithm for network flow problems with convex piecewise linear costs. Optimization Methods and Software, 4(3), 191–207.
Papadimitriou, D., & Fortz, B. (2014a). Methods for time-dependent combined network design and routing optimization. In: IEEE global communications conference, GLOBECOM 2014, Austin, TX, USA, December 8–12, 2014 (pp. 1303–1309).
Papadimitriou, D., & Fortz, B. (2014b). Time-dependent combined network design and routing optimization. In: IEEE international conference on communications, ICC 2014, Sydney, Australia, June 10–14, 2014 (pp. 1124–1130)
Pinto, Y., & Shamir, R. (1994). Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs. Algorithmica, 11, 256–277.
