×

Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem. (English) Zbl 1430.90473

Summary: In this paper, we investigate semidefinite programming (SDP) lower bounds for the quadratic minimum spanning tree problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new branch-and-bound algorithms stands out as the new best exact solution approach for the problem.

MSC:

90C27 Combinatorial optimization
90C22 Semidefinite programming
90C35 Programming involving graphs or networks

Software:

Gurobi; LAPACK; SQPlab; PLCP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T.; Koch, T.; Martin, A., Branching rules revisited, Operations Research Letters, 33, 42-54 (2005) · Zbl 1076.90037
[2] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM Journal on Optimization, 5, 13-51 (1995) · Zbl 0833.90087
[3] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J.; Sorensen, D., LAPACK users’ guide (1999), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0934.65030
[4] Assad, A.; Xu, W., The quadratic minimum spanning tree problem, Naval Research Logistics (NRL), 39, 3, 399-417 (1992) · Zbl 0769.90078
[5] Bartle, R. G.; Sherbert, D. R., Introduction to real analysis (2011), Wiley · Zbl 0494.26002
[6] Bonnans, J. F.; Gilbert, J. C.; Lemarechal, C.; Sagastizábal, C. A., Numerical optimization: Theoretical and practical aspects (2006), Universitext. Springer: Universitext. Springer Berlin Heidelberg · Zbl 1108.65060
[7] Buchheim, C.; Klein, L., The spanning tree problem with one quadratic term, Proceedings of the 12th cologne-twente workshop on graphs and combinatorial optimization (CTW 2013), 31-34 (2013)
[8] Buchheim, C.; Klein, L., Combinatorial optimization with one quadratic term: Spanning trees and forests, Discrete Applied Mathematics, 177, 34-52 (2014) · Zbl 1303.90086
[9] Cela, E., The quadratic assignment problem: Theory and algorithms (combinatorial optimization) (1997), Springer
[10] Cordone, R.; Passeri, G., Heuristic and exact approaches to the quadratic minimum spanning tree problem, Proceedings of the Seventh cologne-twente workshop on graphs and combinatorial optimization (2008)
[11] Cordone, R.; Passeri, G., Solving the quadratic minimum spanning tree problem, Applied Mathematics and Computation, 218, 23, 11597-11612 (2012) · Zbl 1278.05071
[12] Ćustić, A.; Punnen, A. P., A characterization of linearizable instances of the quadratic minimum spanning tree problem, Journal of Combinatorial Optimization, 35, 2, 436-453 (2018) · Zbl 1394.90544
[13] Ćustić, A.; Zhang, R.; Punnen, A. P., The quadratic minimum spanning tree problem and its variations, Discrete Optimization, 27, 73-87 (2018) · Zbl 1506.90256
[14] Edmonds, J., Matroids and the greedy algorithm, Mathematical Programming, 1, 1, 127-136 (1971) · Zbl 0253.90027
[15] Fischer, A.; Fischer, F., Complete description for the spanning tree problem with one linearised quadratic term, Operations Research Letters, 41, 6, 701-705 (2013) · Zbl 1287.90089
[16] Fu, Z.; Hao, J., A three-phase search approach for the quadratic minimum spanning tree problem, Engineering Applications of Artificial Intelligence, 46, 113-130 (2015)
[17] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (series of books in the mathematical sciences) (1979), W. H. Freeman · Zbl 0411.68039
[18] Geoffrion, A. M., Lagrangian relaxation for integer programming, Mathematical Programming Study, 2, 82-114 (1974) · Zbl 0395.90056
[19] Gilmore, P. C., Optimal and suboptimal algorithms for the quadratic assignment problem, Journal of the Society for Industrial and Applied Mathematics, 10, 2, 305-313 (1962) · Zbl 0118.15101
[20] Goberna, M. A.; López, M. A., Linear semi-infinite programming theory: An updated survey, European Journal of Operational Research, 143, 2, 390-405 (2002) · Zbl 1058.90067
[21] Guimarães, D.; Cunha, A. S.d.; Pereira, D. L., Exploiting SDP bounds for the quadratic minimum spanning tree problem, Proceedings of the EURO/ALIO international conference 2018 on applied combinatorial optimization, 56 (2018)
[22] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Mathematical Programming, 6, 1, 62-88 (1974) · Zbl 0284.90057
[23] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10, 3, 673-696 (2000) · Zbl 0960.65074
[24] Helmberg, C.; Rendl, F.; Vanderbei, R. J.; Wolkowicz, H., An interior-point method for semidefinite programming, SIAM Journal on Optimization, 6, 342-361 (1996) · Zbl 0853.65066
[25] Katagiri, H.; Sakawa, M.; Kato, K.; Nishizaki, I.; Uno, T.; Hayashida, T., Tabu search algorithm based on strategic oscillation for nonlinear minimum spanning tree problems, (Chand, A. H.S.; Ao, S. I., Advances in industrial engineering and operations research, vol. 5 (2008)) · Zbl 1154.90508
[26] Koopmans, T. C.; Beckmann, M., Assignment problems and the location of economic activities, Econometrica, 25, 1, 53-76 (1957) · Zbl 0098.12203
[27] Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, 1, 48-50 (1956) · Zbl 0070.18404
[28] Lawler, E. L., The quadratic assignment problem, Management Science, 9, 4, 586-599 (1963) · Zbl 0995.90579
[29] Lee, J.; Leung, J., On the Boolean quadric forest polytope, INFOR, 42, 2, 125-141 (2004) · Zbl 07682322
[30] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM Journal on Optimization, 12, 166-190 (1991) · Zbl 0754.90039
[31] Lucena, A., Non delayed relax-and-cut algorithms, Annals of Operations Research, 140, 1, 375-410 (2005) · Zbl 1091.90082
[32] Maia, S. M.D. M.; Goldbarg, E. F.G.; Goldbarg, M. C., On the biobjective adjacent only quadratic spanning tree problem, Electronic Notes in Discrete Mathematics, 41, 535-542 (2013)
[33] Mifflin, R., An algorithm for constrained optimization with semismooth functions, Mathematics of Operations Research, 2, 2, 191-207 (1977) · Zbl 0395.90069
[34] Monteiro, R. D.C., Primal-dual path-following algorithms for semidefinite programming, SIAM Journal on Optimization, 7, 663-678 (1997) · Zbl 0913.65051
[35] Nesterov, Y. E.; Todd, M. J., Self-scaled barriers and interior-point methods for convex programming, Mathematics of Operations Research, 22, 1-42 (1997) · Zbl 0871.90064
[36] Öncan, T.; Punnen, A. P., The quadratic minimum spanning tree problem: A lower bounding procedure and an efficient search algorithm, Computers & Operations Research, 37, 10, 1762-1773 (2010) · Zbl 1188.90268
[37] LLC Gurobi Optimization (2018). Gurobi optimizer reference manual. http://www.gurobi.com; LLC Gurobi Optimization (2018). Gurobi optimizer reference manual. http://www.gurobi.com
[38] Padberg, M., The boolean quadric polytope: Some characteristics, facets and relatives, Mathematical Programming, 45, 1-3, 139-172 (1989) · Zbl 0675.90056
[39] Palubeckis, G.; Rubliauskas, D.; Targamadzė, A., Metaheuristic approaches for the quadratic minimum spanning tree problem, Information Technology and Control, 39, 257-268 (2010)
[40] Pereira, D. L.; Cunha, A. S.d., Poyhedral results, branch-and-cut and lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem, Networks, 71, 1, 31-50 (2018) · Zbl 1418.90072
[41] Pereira, D. L.; Gendreau, M.; Cunha, A. S.d., Branch-and-cut and branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem, Networks, 65, 4, 367-379 (2015)
[42] Pereira, D. L.; Gendreau, M.; Cunha, A. S.d., Lower bounds and exact algorithms for the quadratic minimum spanning tree problem, Computers & OR, 63, 149-160 (2015) · Zbl 1349.90823
[43] Prim, R. C., Shortest connection networks and some generalizations, The Bell System Technical Journal, 36, 6, 1389-1401 (1957)
[44] Rostami, B.; Malucelli, F., Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation, Computers & Operations Research, 64, 178-188 (2015) · Zbl 1349.90721
[45] Schramm, H.; Zowe, J., A version of the bundle idea for minimizing an nonsmooth function: Conceptual idea, convergence analysis, numerical results, The SIAM Journal on Optimization, 2, 1, 121-152 (1992) · Zbl 0761.90090
[46] Sherali, H. D.; Adams, W. P., A reformulation-linearization technique for solving discrete and continuous nonconvex problems (Nonconvex optimization and its applications) (2013), Springer
[47] Sotirov, R., Bundle methods in combinatorial optimization, dissertation (2003), Universität Klagenfurt - Fakultät für x Wirtschaftswissenschaften und Informatik
[48] Sundar, S.; Singh, A., A swarm intelligence approach to the quadratic minimum spanning tree problem, Information Sciences, 180, 17, 3182-3191 (2010)
[49] Tunçel, L., Polyhedral and semidefinite programming methods in combinatorial optimization (2010), Fields Institute Monographs: Fields Institute Monographs Ontario, Canada · Zbl 1207.90005
[50] Zhout, G.; Gen, M., An effective genetic algorithm approach to the quadratic minimum spanning tree problem, Computers & Operations Research, 25, 3, 229-237 (1998) · Zbl 0904.90169
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.