×

Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints. (English) Zbl 1437.90141

Summary: We consider the maximum \(k\)-cut problem that involves partitioning the vertex set of a graph into \(k\) subsets such that the sum of the weights of the edges joining vertices in different subsets is maximized. The associated semidefinite programming (SDP) relaxation is known to provide strong bounds, but it has a high computational cost. We use a cutting-plane algorithm that relies on the early termination of an interior point method, and we study the performance of SDP and linear programming (LP) relaxations for various values of \(k\) and instance types. The LP relaxation is strengthened using combinatorial facet-defining inequalities and SDP-based constraints. Our computational results suggest that the LP approach, especially with the addition of SDP-based constraints, outperforms the SDP relaxations for graphs with positive-weight edges and \(k \ge 7\).

MSC:

90C27 Combinatorial optimization
90C22 Semidefinite programming
90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ales Z, Knippel A (2016) An extended edge-representative formulation for the k-partitioning problem. Electron Notes Discrete Math 52(Supplement C):333-342 INOC 2015—7th international network optimization conference · Zbl 1351.90035
[2] Anjos, M. F.; Ghaddar, B.; Hupp, L.; Liers, F.; Wiegele, A.; Jünger, Michael (ed.); Reinelt, Gerhard (ed.), Solving \[k\] k-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method, 355-386 (2013), Berlin · Zbl 1317.90301
[3] Avis D, Umemoto J (2003) Stronger linear programming relaxations of max-cut. Math Program 97(3):451-469 · Zbl 1106.90379
[4] Barahona F, Grötschel M, Jünger M, Reinelt G (1988) An application of combinatorial optimization to statistical physics and circuit layout design. Oper Res 36(3):493-513 · Zbl 0646.90084
[5] Chopra S, Rao MR (1993) The partition problem. Math Program 59(1):87-115 · Zbl 0774.90082
[6] Chopra S, Rao MR (1995) Facets of the k-partition polytope. Discrete Appl Math 61(1):27-48 · Zbl 0835.90075
[7] de Klerk E, Pasechnik DV, Warners JP (2004) On approximate graph colouring and max-\[k\] k-cut algorithms based on the \[\theta\] θ-function. J Comb Optim 8(3):267-294 · Zbl 1084.68142
[8] Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201-213 · Zbl 1049.90004
[9] Eisenblätter, A.; Cook, WJ (ed.); Schulz, AS (ed.), The semidefinite relaxation of the \[k\] k-partition polytope is strong, No. 237, 273-290 (2002), Berlin · Zbl 1049.90136
[10] Fairbrother J, Letchford AN (2017) Projection results for the k-partition problem. Discrete Optim 26:97-111 · Zbl 1387.90213
[11] Fairbrother J, Letchford AN, Briggs K (2018) A two-level graph partitioning problem arising in mobile wireless communications. Comput Optim Appl 69(3):653-676 · Zbl 1397.90325
[12] Frieze A, Jerrum M (1997) Improved approximation algorithms for maxk-cut and max bisection. Algorithmica 18(1):67-81 · Zbl 0873.68078
[13] Galli L, Kaparis K, Letchford AN (2011) Gap inequalities for non-convex mixed-integer quadratic programs. Oper Res Lett 39(5):297-300 · Zbl 1235.90102
[14] Ghaddar B, Anjos MF, Liers F (2011) A branch-and-cut algorithm based on semidefinite programming for the minimum \[k\] k-partition problem. Ann Oper Res 188(1):155-174 · Zbl 1225.90144
[15] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115-1145 · Zbl 0885.68088
[16] Gondzio J (2012) Interior point methods 25 years later. Eur J Oper Res 218:587-601 · Zbl 1244.90007
[17] Gondzio J, González-Brevis P, Munari P (2016) Large-scale optimization with the primal-dual column generation method. Math Program Comput 8(1):47-82 · Zbl 1334.90072
[18] Guennebaud G, Jacob B, et al (2010) Eigen. http://eigen.tuxfamily.org. Accessed Feb 2018
[19] Heggernes P (2006) Minimal triangulations of graphs: a survey. Discrete Math 306(3):297-317 · Zbl 1086.05069
[20] Helmberg C (2000) Semidefinite programming for combinatorial optimization, 1st edn. Konrad-Zuse-Zentrum für Informationstechnik, Berlin · Zbl 0960.65074
[21] Helmberg C, Rendl F (1998) Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math Program 82(3):291-315. https://doi.org/10.1007/BF01580072 · Zbl 0919.90112 · doi:10.1007/BF01580072
[22] Hettich R, Kortanek KO (1993) Semi-infinite programming: theory, methods, and applications. SIAM Rev 35(3):380-429 · Zbl 0784.90090
[23] Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Commun ACM 16(6):372-378
[24] Karger D, Motwani R, Sudan M (1998) Approximate graph coloring by semidefinite programming. J ACM 45(2):246-265 · Zbl 0904.68116
[25] Krishnan K, Mitchell JE (2001) Semi-infinite linear programming approaches to semidefinite programming problems. Technical Report 37, Fields Institute Communications Series · Zbl 1028.65066
[26] Krishnan K, Mitchell JE (2006) A semidefinite programming based polyhedral cut and price approach for the maxcut problem. Comput Optim Appl 33(1):51-71 · Zbl 1103.90074
[27] Krislock N, Malick J, Roupin F (2012) Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math Program 143(1):61-86 · Zbl 1285.90030
[28] Laurent M, Poljak S (1996) Gap inequalities for the cut polytope. Eur J Comb 17(2):233-254 · Zbl 0849.52010
[29] Liers F, Jünger M, Reinelt G, Rinaldi G (2005) Computing exact ground states of hard Ising spin glass problems by branch-and-cut. In: New optimization algorithms in physics. Wiley-VCH Verlag GmbH & Co. KGaA, pp 47-69 · Zbl 1059.90147
[30] Lisser A, Rendl F (2003) Graph partitioning using linear and semidefinite programming. Math Program 95(1):91-101 · Zbl 1030.90079
[31] Ma F, Hao J-K (2017) A multiple search operator heuristic for the max-k-cut problem. Ann Oper Res 248(1):365-403 · Zbl 1357.90122
[32] Mitchell JE (2000) Computational experience with an interior point cutting plane algorithm. SIAM J Optim 10(4):1212-1227 · Zbl 0999.90050
[33] Mitchell JE (2003) Realignment in the National Football League: did they do it right? Naval Res Logist 50(7):683-701 · Zbl 1043.90559
[34] Mitchell JE, Pardalos PM, Resende MGC (1999) Interior point methods for combinatorial optimization. In: Du D-Z, Pardalos PM (eds) Handbook of combinatorial optimization, vol 1-3. Springer, Boston, pp 189-297 · Zbl 0934.90061
[35] Mladenović N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097-1100 · Zbl 0889.90119
[36] Moré JJ, Wild SM (2009) Benchmarking derivative-free optimization algorithms. SIAM J Optim 20(1):172-191 · Zbl 1187.90319
[37] Mosek ApS (2015) MOSEK http://www.mosek.com. Accessed Feb 2018
[38] Munari P, Gondzio J (2013) Using the primal-dual interior point algorithm within the branch-price-and-cut method. Comput Oper Res 40(8):2026-2036 · Zbl 1348.90478
[39] Niu C, Li Y, Qingyang Hu R, Ye F (2017) Femtocell-enhanced multi-target spectrum allocation strategy in LTE-A HetNets. IET Commun 11(6):887-896
[40] Palagi, L.; Piccialli, V.; Rendl, F.; Rinaldi, G.; Wiegele, A.; Anjos, MF (ed.); Lasserre, JB (ed.), Computational approaches to max-cut, 821-847 (2011), New York · Zbl 1334.90149
[41] Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425-440 · Zbl 0765.68036
[42] Rendl F (2012) Semidefinite relaxations for partitioning, assignment and ordering problems. 4OR 10(4):321-346 · Zbl 1262.90150
[43] Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math Program 121(2):307-335 · Zbl 1184.90118
[44] Rinaldi G (2018) Rudy, a graph generator. https://www-user.tu-chemnitz.de/ helmberg/sdp_software.html. Accessed Feb 2018
[45] Rodrigues de Sousa VJ, Anjos MF, Le Digabel S (2018) Computational study of valid inequalities for the maximum \[k\] k-cut problem. Ann Oper Res 265(1):5-27. https://doi.org/10.1007/s10479-017-2448-9 · Zbl 1392.90089 · doi:10.1007/s10479-017-2448-9
[46] Seidman SB (1983) Network structure and minimum degree. Soc Netw 5(3):269-287
[47] Sherali HD, Fraticelli BMP (2002) Enhancing RLT relaxations via a new class of semidefinite cuts. J Glob Optim 22(1-4):233-261 · Zbl 1045.90044
[48] Shor N Z (1998) Semidefinite programming bounds for extremal graph problems. Springer, Boston, pp 265-298
[49] Wang G, Hijazi H (2017) Exploiting sparsity for the min k-partition problem. arXiv e-prints. arXiv:1709.00485 · Zbl 1437.90143
[50] Wiegele A (2015) Biq mac library—binary quadratic and max cut library. http://biqmac.uni-klu.ac.at/biqmaclib.html. Accessed Feb 2018
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.