New partial aggregations for multicommodity network flow problems: an application to the fixed-charge network design problem. (English) Zbl 1511.90099
Summary: When solving hard multicommodity network flow problems using an LP-based approach, the number of commodities is a driving factor in the speed at which the LP can be solved, as it is linear in the number of constraints and variables. The conventional approach to improve the solve time of the LP relaxation of a Mixed Integer Programming (MIP) model that encodes such an instance is to aggregate all commodities that have the same origin or the same destination. However, the bound of the resulting LP relaxation can significantly worsen, which tempers the efficiency of aggregating techniques. In this paper, we introduce the concept of partial aggregation of commodities that aggregates commodities over a subset of the network instead of the conventional aggregation over the entire underlying network. This offers a high level of control on the trade-off between size of the aggregated MIP model and quality of its LP bound. We apply the concept of partial aggregation to two different MIP models for the multicommodity network design problem. Our computational study on benchmark instances confirms that the trade-off between solve time and LP bound can be controlled by the level of aggregation, and that choosing a good trade-off can allow us to solve the original large-scale problems faster than without aggregation or with full aggregation.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Andrews, M.; Antonakopoulos, S.; Zhang, L., Minimum-cost network design with (dis)economies of scale, (2010 IEEE 51st Annual Symposium on Foundations of Computer Science (2010)), 585-592 |
| [2] | Avella, P.; Mattia, S.; Sassano, A., Metric inequalities and the network loading problem, Discrete Optim., 4, 1, 103-114 (2007), Mixed Integer Programming · Zbl 1173.90333 |
| [3] | Belotti, P.; Malucelli, F.; Brunetta, L., Multicommodity network design with discrete node costs, Networks, 49, 1, 90-99 (2007) · Zbl 1131.90006 |
| [4] | Bienstock, D.; Chopra, S.; Günlük, O.; Tsai, C.-Y., Minimum cost capacity installation for multicommodity network flows, Math. Program., 81, 2, 177-199 (1998) · Zbl 0922.90064 |
| [5] | Bienstock, D.; Günlük, O., Computational experience with a difficult mixedinteger multicommodity flow problem, Math. Program., 68, 1-3, 213-237 (1995) · Zbl 0834.90054 |
| [6] | Bienstock, D.; Günlük, O., Capacitated network design—Polyhedral structure and computation, INFORMS J. Comput., 8, 3, 243-259 (1996) · Zbl 0871.90031 |
| [7] | Boland, N.; Dumitrescu, I.; Froyland, G.; Gleixner, A. M., LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity, Comput. Oper. Res., 36, 4, 1064-1089 (2009) · Zbl 1162.90446 |
| [8] | Chouman, M.; Crainic, T. G.; Gendron, B., Commodity representations and cut-set-based inequalities for multicommodity capacitated fixed-charge network design, Transp. Sci., 51, 2, 650-667 (2017) |
| [9] | Clautiaux, F.; Hanafi, S.; Macedo, R.; Voge, M.-E.; Alves, C., Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints, European J. Oper. Res., 258, 2, 467-477 (2017), URL: https://www.sciencedirect.com/science/article/pii/S0377221716308037 · Zbl 1394.90477 |
| [10] | Costa, A. M., A survey on benders decomposition applied to fixed-charge network design problems, Comput. Oper. Res., 32, 6, 1429-1450 (2005) · Zbl 1071.90009 |
| [11] | Costa, A. M.; Cordeau, J.-F.c.; Gendron, B., Benders, metric and cutset inequalities for multicommodity capacitated network design, Comput. Optim. Appl., 42, 3, 371-392 (2007) · Zbl 1208.90026 |
| [12] | Crainic, T. G.; Frangioni, A.; Gendron, B., Bundle-based relaxation methods for multicommodity capacitated fixed charge network design, Discrete Appl. Math., 112, 1, 73-99 (2001), Combinatorial Optimization Symposium, Selected Papers · Zbl 1026.90010 |
| [13] | Crainic, T. G.; Gendron, B.; Hernu, G., A slope scaling/Lagrangean perturbation heuristic with long-term memory for multicommodity capacitated fixed-charge network design, J. Heuristics, 10, 5, 525-545 (2004) · Zbl 1062.90009 |
| [14] | Croxton, K. L.; Gendron, B.; Magnanti, T. L., Variable disaggregation in network flow problems with piecewise linear costs, Oper. Res., 55, 1, 146-157 (2007) · Zbl 1167.90602 |
| [15] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004 |
| [16] | Elhallaoui, I.; Metrane, A.; Soumis, F.; Desaulniers, G., Multi-phase dynamic constraint aggregation for set partitioning type problems, Math. Program., 123, 2, 345-370 (2008) · Zbl 1189.90099 |
| [17] | Evans, J. R., A network decomposition/aggregation procedure for a class of multicommodity transportation problems, Networks, 13, 2, 197-205 (1983) |
| [18] | Francis, R. L.; Lowe, T. J.; Rayco, M. B.; Tamir, A., Aggregation error for location models: survey and analysis, Ann. Oper. Res., 167, 1, 171-208 (2008) · Zbl 1173.90005 |
| [19] | Gendron, B.; Crainic, T. G.; Frangioni, A., Multicommodity capacitated network design, (Sansò, B.; Soriano, P., Telecommunications Network Planning (1999), Springer US: Springer US Boston, MA), 1-19 |
| [20] | Gendron, B.; Hanafi, S.; Todosijević, R., Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design, European J. Oper. Res., 268, 1, 70-81 (2018) · Zbl 1403.90199 |
| [21] | Kazemi, A.; Ernst, A. T.; Krishnamoorthy, M.; Le Bodic, P., Locomotive fuel management with inline refueling, European J. Oper. Res., 293, 3, 1077-1096 (2021), URL: https://www.sciencedirect.com/science/article/pii/S0377221720310882 · Zbl 1487.90122 |
| [22] | Kliewer, N.; Mellouli, T.; Suhl, L., A time-space network based exact optimization model for multi-depot bus scheduling, European J. Oper. Res., 175, 3, 1616-1627 (2006) · Zbl 1142.90354 |
| [23] | Macedo, R.; Alves, C.; Valério de Carvalho, J.; Clautiaux, F.; Hanafi, S., Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model, European J. Oper. Res., 214, 3, 536-545 (2011), URL: https://www.sciencedirect.com/science/article/pii/S037722171100381X · Zbl 1219.90022 |
| [24] | Magnanti, T. L.; Wong, R. T., Network design and transportation planning: Models and algorithms, Transp. Sci., 18, 1, 1-55 (1984) |
| [25] | Nazari, A.; Ernst, A.; Dunstall, S.; Bryan, B.; Connor, J.; Nolan, M.; Stock, F., Combined aggregation and column generation for land-use trade-off optimisation, (Denzer, R.; Argent, R. M.; Schimak, G.; Hřebíček, J., Environmental Software Systems. Infrastructures, Services and Applications (2015), Springer International Publishing: Springer International Publishing Cham), 455-466 |
| [26] | Park, Y. W.; Klabjan, D., An aggregate and iterative disaggregate algorithm with proven optimality in machine learning, Mach. Learn., 105, 2, 199-232 (2016) · Zbl 1454.68127 |
| [27] | Raack, C.; Koster, A. M.; Orlowski, S.; Wessäly, R., On cut-based inequalities for capacitated network design polyhedra, Networks, 57, 2, 141-156 (2011) · Zbl 1207.90023 |
| [28] | Rardin, R. L.; Wolsey, L. A., Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems, European J. Oper. Res., 71, 1, 95-109 (1993) · Zbl 0807.90051 |
| [29] | Rodríguez-Martín, I.; José Salazar-González, J., A local branching heuristic for the capacitated fixed-charge network design problem, Comput. Oper. Res., 37, 3, 575-581 (2010), Hybrid Metaheuristics · Zbl 1175.90072 |
| [30] | Rogers, D. F.; Plante, R. D.; Wong, R. T.; Evans, J. R., Aggregation and disaggregation techniques and methodology in optimization, Oper. Res., 39, 4, 553-582 (1991) · Zbl 0729.90738 |
| [31] | Yaghini, M.; Rahbar, M.; Karimi, M., A hybrid simulated annealing and column generation approach for capacitated multicommodity network design, J. Oper. Res. Soc., 64, 7, 1010-1020 (2013) |
| [32] | Yen, J. Y., Finding the k shortest loopless paths in a network, Manage. Sci., 17, 11, 712-716 (1971) · Zbl 0218.90063 |
| [33] | Zetina, C. A.; Contreras, I.; cois Cordeau, J.-F., Exact algorithms based on benders decomposition for multicommodity uncapacitated fixed-charge network design, Comput. Oper. Res., 111, 311-324 (2019) · Zbl 1458.90180 |
| [34] | Zipkin, P. H., Bounds for row-aggregation in linear programming, Oper. Res., 28, 4, 903-916 (1980) · Zbl 0441.90057 |
| [35] | Zipkin, P. H., Bounds on the effect of aggregating variables in linear programs, Oper. Res., 28, 2, 403-418 (1980) · Zbl 0426.90056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
