An exact approach for the multicommodity network optimization problem with a step cost function

Mejri, Imen; Haouari, Mohamed; Layeb, Safa Bhar; Mansour, Farah Zeghal

RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1279-1295.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

We investigate the Multicommodity Network Optimization Problem with a Step Cost Function (MNOP-SCF) where the available facilities to be installed on the edges have discrete step-increasing cost and capacity functions. This strategic long-term planning problem requires installing at most one facility capacity on each edge so that all the demands are routed and the total installation cost is minimized. We describe a path-based formulation that we solve exactly using an enhanced constraint generation based procedure combined with columns and new cuts generation algorithms. The main contribution of this work is the development of a new exact separation model that identifies the most violated bipartition inequalities coupled with a knapsack-based problem that derives additional cuts. To assess the performance of the proposed approach, we conducted computational experiments on a large set of randomly generated instances. The results show that it delivers optimal solutions for large instances with up to 100 nodes, 600 edges, and 4950 commodities while in the literature, the best developed approaches are limited to instances with 50 nodes, 100 edges, and 1225 commodities.

D. Aloise and C.C. Ribeiro, Adaptive memory in multistart heuristics for multicommodity network design. J. Heurist. 17 (2011) 153–179. | DOI | Zbl

Y.K. Agarwal, Design of capacitated multicommodity networks with multiple facilities. Oper. Res. 50 (2002) 333–344. | DOI | MR | Zbl

P. Avella, S. Mattia and A. Sassano, Metric inequalities and the network loading problem. Discret. Opt. 4 (2007) 103–114. | DOI | MR | Zbl

A. Balakrishnan, T.L. Magnanti and P. Mirchandani, Network design, edited by M. Dell Amico, F. Maffioli and S. Martello. In: Annotated Bibliographies in Combinatorial Optimization. Wiley, New York, USA (1997) 311–334. | Zbl

D. Bienstock, S. Chopra, O. Günlük and C.Y. Tsai, Minimum cost capacity installation for multicommodity network flows. Math. Progr. 81 (1998) 177–199. | DOI | MR | Zbl

D. Bienstock and O. Günlük, Capacitated network design—polyhedral structure and computation. Inf. J Comput. 8 (1996) 243–259. | DOI | Zbl

M. Chouman, T.G. Crainic and B. Gendron, Commodity representations and cut-set-based inequalities for multicommodity capacitated fixed-charge network design. Transp. Sci. 51 (2016) 650–667. | DOI

K.L. Croxton, B. Gendron and T.L. Magnanti, A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. Manage. Sci. 49 (2003) 1268–1273. | DOI | Zbl

A.M. Costa, A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32 (2005) 1429–1450. | DOI | MR | Zbl

V. Gabrel, A. Knippel and M. Minoux, Exact solution of multicommodity network optimization problems with general step cost functions. Oper. Res. Lett. 25 (1999) 15–23. | DOI | MR | Zbl

V. Gabrel, A. Knippel and M. Minoux, A comparison of heuristic for the discrete cost multicommodity network optimization problem. J. Heurist. 9 (2003) 429–445. | DOI

V. Gabrel and M. Minoux, LP relaxations better than convexification for multicommodity network optimization problems with step increasing cost functions. Acta Math. Vietnam. 22 (1997) 123–145. | MR | Zbl

B. Gendron, J.Y. Potvin and P. Soriano, Diversification strategies in local search for a nonbifurcated network loading problem, Eur. J. Oper. Res. 142 (2002) 231–241. | DOI | MR | Zbl

B. Gendron, J.Y. Potvin and P. Soriano, A tabu search with slope scaling for the multicommodity capacitated location problem with balancing requirements, Ann. Oper. Res. 122 (2003) 193–217. | DOI | MR | Zbl

O. Günlük, A branch-and-cut algorithm for capacitated network design problems, Math. Progr. 86 (1999) 17–39. | DOI | MR | Zbl

D.S. Johnson, J.K. Lenstra and A.H.G. Rinnooy Kan, The complexity of the network design problem. Networks 8 (1978) 279–285. | DOI | MR | Zbl

K. Onaga and O. Kakusho, On feasibility conditions of multicommodity flows in networks. IEEE Trans. Circ. Theory 18 (1971) 425–429. | DOI | MR

S.B. Layeb, MNOP-SCF Instances. Available at: https://www.researchgate.net/publication/330162116_MNOP-SCF_Instances (2019)

C. Lee, K. Lee and S. Park, Benders decomposition approach for the robust network design problem with flow bifurcations. Networks 62 (2013) 1–16. | DOI | MR | Zbl

I. Ljubić, P. Putz and J.J. Salazar-González, Exact approaches to the single-source network loading problem. Networks 59 (2012) 89–106. | DOI | MR | Zbl

S. Mattia, Separating tight metric inequalities by bilevel programming. Oper. Res. Lett. 40 (2012) 568–572. | DOI | MR | Zbl

M. Minoux, Network synthesis and optimum network design problems: Models, solution methods and application. Networks 19 (1989) 313–360. | DOI | MR | Zbl

M. Minoux, Discrete cost multicommodity network optimization problems and exact solution methods. Ann. Oper. Res. 106 (2001) 19–46. | DOI | MR | Zbl

M. Mrad and M. Haouari, Optimal solution of the discrete cost multicommodity network design problem. Appl. Math. Comput. 204 (2008) 745–753. | MR | Zbl

S. Orlowski, R. Wessäly, M. Pióro and A. Tomaszewski, SNDlib 1.0—survivable network design library. Networks 55 (2010) 276–286. | DOI

C. Raack, A.M. Koster, S. Orlowski and R. Wessäly, On cut-based inequalities for capacitated network design polyhedra. Networks 57 (2011) 141–156. | DOI | MR | Zbl

M. Stoer and G. Dahl, A polyhedral approach to multicommodity survivable network design. Numer. Math. 68 (1994) 149–167. | DOI | MR | Zbl