×

Layered graph approaches for combinatorial optimization problems. (English) Zbl 1458.90612

Summary: Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that have been used in the (recent) scientific literature and review methods to successfully solve the resulting large-scale, extended formulations. Modeling guidelines and important observations concerning the solution of layered graph formulations by decomposition methods are given together with several future research directions.

MSC:

90C35 Programming involving graphs or networks
90C10 Integer programming
90C27 Combinatorial optimization

Software:

stprbh
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abeledo, H.; Fukasawa, R.; Pessoa, A.; Uchoa, E., The time dependent traveling salesman problem: polyhedra and algorithm, Math. Program. Comput., 5, 1, 27-55, (2013) · Zbl 1269.90064
[2] Baptiste, P.; Sadykov, R., On scheduling a single machine to minimize a piecewise linear objective function: a compact MIP formulation, Naval Res. Logist. (NRL), 56, 6, 487-502, (2009) · Zbl 1182.90040
[3] Bendali, F.; Diarrassouba, I.; Mahjoub, A. R.; Mailfert, J., The k edge-disjoint 3-hop-constrained paths polytope, Discrete Optim., 7, 4, 222-233, (2010) · Zbl 1241.90155
[4] Bigras, L.-P.; Gamache, M.; Savard, G., Time-indexed formulations and the total weighted tardiness problem, INFORMS J. Comput., 20, 1, 133-142, (2008) · Zbl 1243.90057
[5] Boland, N.; Clement, R.; Waterer, H., A bucket indexed formulation for nonpreemptive single machine scheduling problems, INFORMS J. Comput., 28, 1, 14-30, (2016) · Zbl 1338.90159
[6] Boland, N.; Hewitt, M.; Marshall, L.; Savelsbergh, M., The continuous-time service network design problem, Oper. Res., 65, 5, 1303-1321, (2017) · Zbl 1380.90069
[7] Botton, Q.; Fortz, B.; Gouveia, L., On the hop-constrained survivable network design problem with reliable edges, Comput. Oper. Res., 64, 159-167, (2015) · Zbl 1349.90158
[8] Botton, Q.; Fortz, B.; Gouveia, L.; Poss, M., Benders decomposition for the hop-constrained survivable network design problem, INFORMS J. Comput., 25, 1, 13-26, (2013)
[9] Brandstätter, G.; Leitner, M.; Ljubić, I., Location of charging stations in electric car sharing systems, Technical Report, (2016), Department of Statistics and Operations Research, University of Vienna, Vienna, Austria
[10] 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, Eur. J. Oper. Res., 258, 2, 467-477, (2017) · Zbl 1394.90477
[11] Costa, A. M.; Cordeau, J.-F.; Laporte, G., Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Networks, 53, 2, 141-159, (2009) · Zbl 1180.90348
[12] Dantzig, G.; Fulkerson, R.; Johnson, S., Solution of a large-scale traveling-salesman problem, J.Oper.Res.Soc.Am., 2, 4, 393-410, (1954)
[13] Dash, S.; Günlük, O.; Lodi, A.; Tramontani, A., A time bucket formulation for the traveling salesman problem with time windows, INFORMS J. Comput., 24, 1, 132-147, (2010) · Zbl 1462.90103
[14] De Boeck, J.; Fortz, B., Extended formulation for hop constrained distribution network configuration problems, Eur. J. Oper. Res., 265, 2, 488-502, (2018) · Zbl 1374.90082
[15] Diarrassouba, I.; Gabrel, V.; Mahjoub, A. R.; Gouveia, L.; Pesneau, P., Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem, Networks, 67, 2, 148-169, (2016) · Zbl 1390.90104
[16] Drexl, M., On some generalized routing problems, (2007), Faculty of Business and Economics, RWTH Aachen University, Aachen, Germany
[17] Drexl, M., Synchronization in vehicle routing-a survey of VRPs with multiple synchronization constraints, Transp. Sci., 46, 3, 297-316, (2012)
[18] Fischer, F.; Helmberg, C., Dynamic graph generation for the shortest path problem in time expanded networks, Math. Program., 143, 1-2, 257-297, (2014) · Zbl 1303.90116
[19] Fischetti, M.; Leitner, M.; Ljubić, I.; Luipersbeck, M.; Monaci, M.; Resch, M.; Salvagnin, D., Thinning out Steiner trees: a node based model for uniform edge costs, Math. Program. Comput;., 9, 2, 203-229, (2017) · Zbl 1387.90132
[20] Fischetti, M.; Salazar González, J. J.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Oper. Res., 45, 3, 378-394, (1997) · Zbl 0893.90164
[21] Fleischer, L.; Skutella, M., Quickest flows over time, SIAM J. Comput., 36, 6, 1600-1630, (2007) · Zbl 1146.90014
[22] Fox, K. R.; Gavish, B.; Graves, S. C., An n-constraint formulation of the (time-dependent) traveling salesman problem, Oper. Res., 28, 4, 1018-1021, (1980) · Zbl 0507.90060
[23] Godinho, M. T.; Gouveia, L.; Magnanti, T., Combined route capacity and route length models for unit demand vehicle routing problems, Discrete Optim., 5, 2, 350-372, (2008) · Zbl 1168.90359
[24] Godinho, M. T.; Gouveia, L.; Pesneau, P., Natural and extended formulations for the time-dependent traveling salesman problem, Discrete Appl. Math., 164, 1, 138-153, (2014) · Zbl 1331.90066
[25] Gonçalves de Deus, R. P., Estimating the Efficacy of Mass Rescue Operations in Ocean Areas with Vehicle Routing Models and Heuristics, (2018), Universidade de Lisboa, Ph.D. thesis
[26] Gouveia, L., A 2n constraint formulation for the capacitated minimal spanning tree problem, Oper. Res., 43, 1, 130-141, (1995) · Zbl 0830.90049
[27] Gouveia, L., Using hop-indexed models for constrained spanning and Steiner tree models, (Sanso, B.; Soriano, P., Telecommunications Network Planning, (1999), Kluwer Academic Publishers), 21-32
[28] Gouveia, L.; Leitner, M.; Ljubić, I., Hop constrained Steiner trees with multiple root nodes, Eur. J. Oper. Res., 236, 1, 100-112, (2014) · Zbl 1338.90266
[29] Gouveia, L.; Leitner, M.; Ljubić, I., The two-level diameter constrained spanning tree problem, Math. Program., 150, 1, 49-78, (2015) · Zbl 1309.90065
[30] Gouveia, L.; Leitner, M.; Ruthmair, M., Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem, Eur. J. Oper. Res., 262, 3, 908-928, (2017) · Zbl 1375.90223
[31] Gouveia, L.; Paias, A.; Sharma, D., Modeling and solving the rooted distance-constrained minimum spanning tree problem, Comput. Oper. Res., 35, 2, 600-613, (2008) · Zbl 1141.90031
[32] Gouveia, L.; Patrício, P.; de Sousa, A., Compact models for hop-constrained node survivable network design: an application to MPLS, Telecommunications Planning: Innovations in Pricing, Network Design and Management, 167-180, (2006), Springer
[33] Gouveia, L.; Patrício, P.; de Sousa, A., Hop-constrained node survivable network design: an application to MPLS over WDM, Netw. Spat. Econ., 8, 1, 3-21, (2008) · Zbl 1172.90339
[34] Gouveia, L.; Patrício, P.; de Sousa, A., Models for optimal survivable routing with a minimum number of hops: comparing disaggregated with aggregated models, Int. Trans. Oper. Res., 18, 3, 335-358, (2011) · Zbl 1219.90176
[35] Gouveia, L.; Patrício, P.; de Sousa, A., Lexicographical minimization of routing hops in hop-constrained node survivable networks, Telecommun. Syst., 62, 2, 417-434, (2016)
[36] Gouveia, L.; Requejo, C., A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem, Eur. J. Oper. Res., 132, 3, 539-552, (2001) · Zbl 1055.90084
[37] Gouveia, L.; Ruthmair, M., Load-dependent and precedence-based models for pickup and delivery problems, Comput. Oper. Res., 63, 56-71, (2015) · Zbl 1349.90087
[38] Gouveia, L.; Ruthmair, M.; Santos, D., Um modelo de fluxo para o electric traveling salesman problem, (Antunes, C. H.; Cardoso, D. M.; da Silva, F. N., A Investigação Operacional em Portugal - novos desafios novas ideias, homenagem ao Professor Luís Valadares Tavares, (2016), IST Press, Lisboa), 133-143
[39] Gouveia, L.; Simonetti, L. G.; Uchoa, E., Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs, Math. Program., 128, 1, 123-148, (2011) · Zbl 1218.90201
[40] Hansknecht, C.; Joormann, I.; Stiller, S., Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem, Technical Report, (2018), Technische Universität Braunschweig
[41] Laporte, G.; Desrochers, M.; Nobert, Y., Two exact algorithms for the distance-constrained vehicle routing problem, Networks, 14, 1, 161-172, (1984) · Zbl 0538.90093
[42] Leitner, M., Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem, Comput. Oper. Res., 65, 1-18, (2016) · Zbl 1349.90636
[43] Leitner, M.; Ljubić, I.; Luipersbeck, M.; Sinnl, M., Decomposition methods for the two-stage stochastic Steiner tree problem, Comput. Optim. Appl., 69, 3, 713-752, (2018) · Zbl 1401.90249
[44] Leitner, M.; Ljubić, I.; Luipersbeck, M.; Sinnl, M., A dual-ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems, INFORMS J. Comput., 30, 2, 402-420, (2018)
[45] Leitner, M.; Ljubić, I.; Riedler, M.; Ruthmair, M., Exact approaches for the directed network design problem with relays, Technical Report, (2018), Algorithms and Complexity Group, Vienna University of Technology Vienna, Austria
[46] Leitner, M.; Ljubić, I.; Salazar-González, J.-J.; Sinnl, M., An algorithmic framework for the exact solution of tree-star problems, Eur. J. Oper. Res., 261, 1, 54-66, (2017) · Zbl 1403.90577
[47] Letchford, A. N.; Salazar-González, J.-J., Projection results for vehicle routing, Math. Program., 105, 2-3, 251-274, (2006) · Zbl 1085.90032
[48] Ljubić, I.; Gollowitzer, S., Layered graph approaches to the hop constrained connected facility location problem, INFORMS J. Comput., 25, 2, 256-270, (2013)
[49] Macedo, R.; Alves, C.; de Carvalho, J. M.V.; Clautiaux, F.; Hanafi, S., Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model, Eur. J. Oper. Res., 214, 3, 536-545, (2011) · Zbl 1219.90022
[50] Mahjoub, A. R.; Poss, M.; Simonetti, L.; Uchoa, E., Distance transformation for network design problems, Technical Report, (2017)
[51] Mahjoub, A. R.; Simonetti, L.; Uchoa, E., Hop-level flow formulation for the survivable network design with hop constraints problem, Networks, 61, 2, 171-179, (2013) · Zbl 1269.90023
[52] Oncan, T.; Altinel, I. K.; Laporte, G., A comparative analysis of several asymmetric traveling salesman problem formulations, Comput. Oper. Res., 36, 3, 637-654, (2009) · Zbl 1179.90321
[53] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Rev., 33, 1, 60-100, (1991) · Zbl 0734.90060
[54] Pereira, D. L.; Salles da Cunha, A., Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem, Comput. Oper. Res., 98, 38-55, (2018) · Zbl 1391.90614
[55] Pessoa, A.; Uchoa, E.; de Aragão, M. P., A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem, Networks, 54, 4, 167-177, (2009) · Zbl 1205.90081
[56] Pessoa, A.; Uchoa, E.; de Aragão, M. P.; Rodrigues, R., Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems, Math. Program. Comput., 2, 3-4, 259-290, (2010) · Zbl 1208.90119
[57] Picard, J. C.; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Oper. Res., 26, 1, 86-110, (1978) · Zbl 0371.90066
[58] Pulleyblank, W. R., Chapter v polyhedral combinatorics, Optimization, Handbooks in Operations Research and Management Science, 1, 371-446, (1989), Elsevier
[59] Riedler, M.; Jatschka, T.; Maschler, J.; Raidl, G. R., An iterative time-bucket refinement algorithm for a high-resolution resource-constrained project scheduling problem, Int Transactions in Operational Research, (2017)
[60] Roberti, R.; Toth, P., Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison, EURO J. Transp. Logist., 1, 1, 113-133, (2012)
[61] Ruthmair, M., On Solving Constrained Tree Problems and an Adaptive Layers Framework, (2012), Vienna University of Technology, Institute of Computer Graphics and Algorithms Vienna, Austria
[62] Ruthmair, M.; Raidl, G. R., A layered graph model and an adaptive layers framework to solve delay-constrained minimum tree problems, (Günlük, O.; Woeginger, G. J., Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO XV), (2011), Springer), 376-388 · Zbl 1341.68008
[63] Ruthmair, M.; Raidl, G. R., On solving the rooted delay- and delay-variation-constrained Steiner tree problem, (Mahjoub, A. R.; etal., Proceedings of the 2nd International Symposium on Combinatorial Optimization, (2012), Springer), 225-236 · Zbl 1370.68237
[64] Sinnl, M.; Ljubić, I., A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints, Math. Program. Comput., 8, 4, 461-490, (2016) · Zbl 1391.90421
[65] Uchoa, E., Cuts over extended formulations by flow discretization, (Mahjoub, A.. R., Progress in Combinatorial Optimization, (2011), ISTE-Wiley), 255-282 · Zbl 1242.90204
[66] Uchoa, E.; Fukasawa, R.; Lysgaard, J.; Pessoa, A.; de Aragão, M. P.; Andrade, D. V., Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation, Math. Program., 112, 2, 443-472, (2008) · Zbl 1146.90059
[67] Uchoa, E.; Toffolo, T. A.M.; de Souza, M. C.; Martins, A. X.; Fukasawa, R., Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem, Networks, 59, 1, 148-160, (2012) · Zbl 1241.90187
[68] Van den Akker, J. M.; Hurkens, C. A.J.; Savelsbergh, M. W.P., Time-indexed formulations for machine scheduling problems: column generation, INFORMS J. Comput., 12, 2, 111-124, (2000) · Zbl 1034.90004
[69] Wang, X.; Regan, A. C., Local truckload pickup and delivery with hard time window constraints, Transp. Res. Part B: Methodol., 36, 2, 97-112, (2002)
[70] Wang, X.; Regan, A. C., On the convergence of a new time window discretization method for the traveling salesman problem with time window constraints, Comput. Ind. Eng., 56, 1, 161-164, (2009)
[71] Wong, R. T., A dual ascent approach for Steiner tree problems on a directed graph, Math. Program., 28, 3, 271-287, (1984) · Zbl 0532.90092
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.