de Meijer, Frank; Sotirov, Renata The quadratic cycle cover problem: special cases and efficient bounds. (English) Zbl 1442.90161 J. Comb. Optim. 39, No. 4, 1096-1128 (2020). Summary: The quadratic cycle cover problem is the problem of finding a set of node-disjoint cycles visiting all the nodes such that the total sum of interaction costs between consecutive arcs is minimized. In this paper we study the linearization problem for the quadratic cycle cover problem and related lower bounds. In particular, we derive various sufficient conditions for the quadratic cost matrix to be linearizable, and use these conditions to compute bounds. We also show how to use a sufficient condition for linearizability within an iterative bounding procedure. In each step, our algorithm computes the best equivalent representation of the quadratic cost matrix and its optimal linearizable matrix with respect to the given sufficient condition for linearizability. Further, we show that the classical Gilmore-Lawler type bound belongs to the family of linearization based bounds, and therefore apply the above mentioned iterative reformulation technique. We also prove that the linearization vectors resulting from this iterative approach satisfy the constant value property. The best among here introduced bounds outperform existing lower bounds when taking both quality and efficiency into account. Cited in 4 Documents MSC: 90C27 Combinatorial optimization Keywords:quadratic cycle cover problem; linearization problem; equivalent representations; Gilmore-Lawler bound PDFBibTeX XMLCite \textit{F. de Meijer} and \textit{R. Sotirov}, J. Comb. Optim. 39, No. 4, 1096--1128 (2020; Zbl 1442.90161) Full Text: DOI arXiv References: [1] Adams, WP; Forrester, RJ; Glover, FW, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs, Discrete Optim, 1, 2, 99-120 (2004) · Zbl 1091.90040 [2] Adams, WP; Sherali, HD, A tight linearization and an algorithm for zero-one quadratic programming problems, Manag Sci, 32, 10, 1274-1290 (1986) · Zbl 0623.90054 [3] Adams, WP; Sherali, HD, Linearization strategies for a class of zero-one mixed integer programming problems, Oper Res, 38, 2, 217-226 (1990) · Zbl 0724.90046 [4] Aggarwal, A.; Coppersmith, D.; Khanna, S.; Motwani, R.; Schieber, B., The angular-metric traveling salesman problem, SIAM J Comput, 29, 697-711 (1999) · Zbl 0941.68056 [5] Amaldi, E.; Galbiati, G.; Maffioli, F., On minimum reload cost paths, tours and flows, Networks, 57, 254-260 (2011) · Zbl 1219.68121 [6] Burkard, R.; Dell’Amico, M.; Martello, S., Assignment problems (2009), Philadelphia: SIAM, Philadelphia [7] Büyükçolak, Y.; Gözüpek, D.; Özkan, S., On minimum reload cost paths, tours and flows, Networks, 74, 3, 274-286 (2019) · Zbl 1434.05122 [8] Carraresi, P.; Malucelli, F., A new lower bound for the quadratic assignment problem, Oper Res, 40, 22-27 (1992) · Zbl 0755.90083 [9] Chiba, S.; Yamashita, T., On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs, SIAM J Discrete Math, 32, 1, 394-409 (2018) · Zbl 1379.05046 [10] Comellas, FCD; Fiol, MA, Multidimensional manhattan street networks, SIAM J Discrete Math, 22, 4, 1428-1447 (2008) · Zbl 1227.05156 [11] Ćustić, A.; Punnen, AP, A characterization of linearizable instances of the quadratic minimum spanning tree problem, J Comb Optim, 35, 2, 436-453 (2018) · Zbl 1394.90544 [12] de Meijer F (2018) Bounds on the minimum reload cost cycle cover problem. Master’s thesis, Tilburg University [13] Erdős, P.; Rényi, A., On random graphs, Publ Math, 6, 2, 197-290 (1959) [14] Fischer A (2013) A polyhedral study of quadratic traveling salesman problems. PhD thesis, Chemnitz University of Technology [15] Fischer, A.; Fischer, F.; Jäger, G.; Keilwagen, J.; Molitor, P.; Grosse, I., Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics, Discrete Appl Math, 166, 87-114 (2014) · Zbl 1288.90074 [16] Fischer, F.; Jäger, G.; Lau, A.; Molitor, P., Complexity and algorithms for the traveling salesman problem and the assignment problem of second order, Lect Notes Comput Sci, 5165, 211-224 (2009) [17] Galbiati, G., The complexity of a minimum reload cost diameter problem, Discrete Appl Math, 156, 3494-3497 (2008) · Zbl 1168.68035 [18] Galbiati, G.; Gualandi, S.; Maffioli, F., On minimum reload cost cycle cover, Discrete Appl Math, 164, 112-120 (2014) · Zbl 1321.05083 [19] Gamvros, I.; Gouveia, L.; Raghavan, S., Reload cost trees and network design, Networks, 59, 365-379 (2012) · Zbl 1248.68379 [20] Gilmore, P., Optimal and suboptimal algorithms for the quadratic assignment problem, J Soc Ind Appl Math, 10, 2, 305-313 (1962) · Zbl 0118.15101 [21] Glover, F., Improved linear integer programming formulations of nonlinear integer problems, Manag Sci, 22, 4, 455-460 (1975) · Zbl 0318.90044 [22] Gourvès, L.; Lyra, A.; Martinhon, C.; Monnot, J., The minimum reload s-t path, trail and walk problems, Discrete Appl Math, 158, 13, 1404-1417 (2010) · Zbl 1209.05131 [23] Hu, H.; Sotirov, R., Special cases of the quadratic shortest path problem, J Comb Optim, 35, 3, 754-777 (2018) · Zbl 1396.90094 [24] Hu H, Sotirov R (2019) The linearization problem of binary quadratic problems and its applications. arXiv:1802.02426 · Zbl 1478.90072 [25] Jäger, G.; Molitor, P., Algorithms and experimental study for the traveling salesman of second order, Lect Notes Comput Sci, 5165, 211-224 (2008) · Zbl 1168.90586 [26] Kabadi, SN; Punnen, AP, An \({\cal{O}}(n^4)\) algorithm for the QAP linearization problem, Math Oper Res, 36, 754-761 (2011) · Zbl 1243.90187 [27] Koopmans, TC; Beckmann, MJ, Assignment problems and the location of economic activities, Econometrica, 25, 53-76 (1957) · Zbl 0098.12203 [28] Lawler, EL, The quadratic assignment problem, Manag Sci, 9, 4, 586-599 (1963) · Zbl 0995.90579 [29] Lendl, S.; Ćustić; Punnen, AP, Combinatorial optimization problems with interaction costs: complexity and solvable cases, Discrete Optim, 33, 101-117 (2019) · Zbl 1474.90381 [30] Punnen, AP; Kabadi, SN, A linear time algorithm for the Koopmans Beckmann QAP linearization and related problems, Discrete Optim, 10, 3, 200-209 (2013) · Zbl 1506.90232 [31] Punnen AP, Pandey P, Friesen M (2019) Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems. Comput Oper Res 112:104769 · Zbl 1458.90503 [32] Punnen AP, Walter M, Woods BD (2018) A characterization of linearizable instances of the quadratic traveling salesman problem. arXiv: 1708.07217v3 [33] Rostami, B.; Chassein, A.; Hopf, M.; Frey, D.; Buchheim, C.; Malucelli, F.; Goerigk, M., The quadratic shortest path problem: complexity, approximability and solution methods, Eur J Oper Res, 268, 2, 473-485 (2018) · Zbl 1403.90645 [34] Rostami, B.; Malucelli, F., Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation, Comput Oper Res, 64, 178-188 (2015) · Zbl 1349.90721 [35] Sahni, S.; Gonzalez, T., P-complete approximation problems, J ACM, 23, 555-565 (1976) · Zbl 0348.90152 [36] Staněk, R.; Greistorfer, P.; Ladner, K.; Pferschy, U., Geometric and lp-based heuristics for angular travelling salesman problems in the plane, Comp Oper Res, 108, 97-111 (2019) · Zbl 1458.90561 [37] Wirth, H.; Steffan, J., Reload cost problems: minimum diameter spanning tree, Discrete Appl Math, 113, 73-85 (2001) · Zbl 1003.05061 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.