×

Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem. (English) Zbl 1272.90045

Summary: The stable-set problem is an NP-hard problem that arises in numerous areas such as social networking, electrical engineering, environmental forest planning, bioinformatics clustering and prediction, and computational chemistry. While some relaxations provide high-quality bounds, they result in very large and expensive conic optimization problems. We describe and test an integrated interior-point cutting-plane method that efficiently handles the large number of nonnegativity constraints in the popular doubly-nonnegative relaxation. This algorithm identifies relevant inequalities dynamically and selectively adds new constraints in a build-up fashion. We present computational results showing the significant benefits of this approach in comparison to a standard interior-point cutting-plane method.

MSC:

90C22 Semidefinite programming
90C51 Interior-point methods
90C09 Boolean programming
90C20 Quadratic programming
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C90 Applications of mathematical programming

Software:

SDPT3; Biq Mac; CLIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F, Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J Optim, 5, 13-51, (1995) · Zbl 0833.90087 · doi:10.1137/0805002
[2] Anjos, MF; Vannelli, A, Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes, INFORMS J Comput, 20, 611-617, (2008) · Zbl 1243.90174 · doi:10.1287/ijoc.1080.0270
[3] Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math Program 58(3, Ser. A):295-324 · Zbl 0796.90041
[4] Barahona, F; Epstein, R; Weintraub, A, Habitat dispersion in forest planning and the stable set problem, Oper Res, 40, s14-s21, (1992) · Zbl 0745.90078 · doi:10.1287/opre.40.1.S14
[5] Benson, HY; Shanno, DF, An exact primal-dual penalty method approach to warmstarting interior-point methods for linear programming, Comput Optim Appl, 38, 371-399, (2007) · Zbl 1171.90546 · doi:10.1007/s10589-007-9048-6
[6] Bomze, IM, Copositive optimization-recent developments and applications, Eur J Oper Res, 216, 509-520, (2012) · Zbl 1262.90129 · doi:10.1016/j.ejor.2011.04.026
[7] Bomze, IM; Klerk, E, Solving standard quadratic optimization problems via linear, semidefinite and copositive programming, J Global Optim, 24, 163-185, (2002) · Zbl 1047.90038 · doi:10.1023/A:1020209017701
[8] Bomze IM, Dür M, Teo CP (2012) Copositive optimization. Optima MOS Newsl 89:2-10. http://www.mathopt.org/Optima-Issues/optima89.pdf · Zbl 0444.94009
[9] Bomze IM, Frommlet F, Locatelli M (2010) Copositivity cuts for improving SDP bounds on the clique number. Math Program 124(1-2, Ser. B):13-32 · Zbl 1198.90312
[10] Bomze IM, Locatelli M, Tardella F (2008) New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math Program 115(1, Ser. A):31-64 · Zbl 1171.90007
[11] Bomze, IM; Schachinger, W; Uchida, G, Think co(mpletely)positive! matrix properties, examples and a clustered bibliography on copositive optimization, J Global Optim, 52, 423-445, (2012) · Zbl 1268.90051 · doi:10.1007/s10898-011-9749-3
[12] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge · Zbl 1058.90049
[13] Burer, S, Optimizing a polyhedral-semidefinite relaxation of completely positive programs, Math Program Comput, 2, 1-19, (2010) · Zbl 1190.90135 · doi:10.1007/s12532-010-0010-8
[14] Burer S (2011) Copositive programming. In: Anjos MF, Lasserre JB (eds) Handbook of semidefinite, cone and polynomial optimization: theory, algorithms, software and applications. International Series in Operations Research and Management Science. Springer, New York, pp 201-218
[15] Dantzig GB, Ye Y (1991) A build-up interior method for linear programming: affine scaling form. Technical report, Stanford University/The University of Iowa · Zbl 0999.90050
[16] Davi T, Jarre F (2011) Solving large scale problems over the doubly nonnegative cone. Technical report, Institut für Informatik, Universität Düsseldorf (submitted). http://www.optimization-online.org/DB_HTML/2011/04/3000.html · Zbl 1312.90050
[17] de Klerk E (2002) Aspects of semidefinite programming, applied optimization. Interior point algorithms and selected applications, vol 65. Kluwer, Dordrecht · Zbl 0991.90098
[18] Klerk, E, Exploiting special structure in semidefinite programming: a survey of theory and applications, Eur J Oper Res, 201, 1-10, (2010) · Zbl 1177.90315 · doi:10.1016/j.ejor.2009.01.025
[19] Klerk, E; Pasechnik, DV, Approximation of the stability number of a graph via copositive programming, SIAM J Optim, 12, 875-892, (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[20] den Hertog D, Roos C, Terlaky T (1994) Adding and deleting constraints in the logarithmic barrier method for LP. In: Advances in optimization and approximation, vol 1. Nonconvex Optim Appl. Kluwer, Dordrecht, pp 166-185 · Zbl 0828.90084
[21] Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2, Ser. A):201-213 · Zbl 1049.90004
[22] Dukanovic I, Rendl F (2007) Semidefinite programming relaxations for graph coloring and maximal clique problems. Math Program 109(2-3, Ser. B):345-365 · Zbl 1278.90299
[23] Dukanovic I, Rendl F (2010) Copositive programming motivated bounds on the stability and the chromatic numbers. Math Program 121(2, Ser. A):249-268 · Zbl 1194.90109
[24] Dür M (2010) Copositive programming—a survey. In: Moritz D, Francois G, Elias J, Wim M (eds) Recent advances in optimization and its applications in engineering. Springer, Berlin, pp 3-20 · Zbl 1176.90611
[25] El-Bakry, AS; Tapia, RA; Zhang, Y, A study of indicators for identifying zero variables in interior-point methods, SIAM Rev, 36, 45-72, (1994) · Zbl 0801.65056 · doi:10.1137/1036003
[26] Engau A (2012) Recent progress in interior-point methods: cutting plane methods and warm starts. In: Anjos MF, Lasserre JB (eds) Handbook of semidefinite, conic, and polynomial optimization, International Series in Operations Research & Management Science, Chapter 17, vol 166. Springer, New York, pp 471-498 · Zbl 1334.90101
[27] Engau A, Anjos MF (2011) A primal-dual interior-point algorithm for linear programming with selective addition of inequalities. Technical Report G-2011-44, GERAD, Montréal, QC, Canada · Zbl 1243.90174
[28] Engau A, Anjos MF, Vannelli A (2009) A primal-dual slack approach to warmstarting interior-point methods for linear programming. In: Chinneck JW, Kristjansson B, Saltzman MJ (eds) Operations research and cyber-infrastructure. Springer, Berlin, pp 195-217 · Zbl 0444.94009
[29] Engau A, Anjos MF, Vannelli A (2010a) An improved interior-point cutting-plane method for binary quadratic optimization. Electron Notes Discret Math 36:743-750 · Zbl 1237.90179
[30] Engau A, Anjos MF, Vannelli A (2010b) On interior-point warmstarts for linear and combinatorial optimization. SIAM J Optim 10(4):1828-1861 · Zbl 1206.90215
[31] Engau A, Anjos MF, Vannelli A (2012) On handling cutting-planes in interior-point methods for solving semidefinite relaxations of binary quadratic optimization problems. Optim Methods Softw 27(3): 539-559 · Zbl 1242.90193
[32] Fischer I, Gruber G, Rendl F, Sotirov R (2006) Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition. Math Program 105(2-3, Ser. B):451-469 · Zbl 1085.90044
[33] Fortunato, S, Community detection in graphs, Phys Rep, 486, 75-174, (2010) · doi:10.1016/j.physrep.2009.11.002
[34] Gondzio, J; Grothey, A, A new unblocking technique to warmstart interior point methods based on sensitivity analysis, SIAM J Optim, 19, 1184-1210, (2008) · Zbl 1177.90411 · doi:10.1137/060678129
[35] Gruber G, Rendl F (2003) Computational experience with stable set relaxations. SIAM J Optim 13(4): 1014-1028 · Zbl 1049.90075
[36] Gvozdenović N, Laurent M (2008a) Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization. SIAM J Optim 19(2):592-615 · Zbl 1213.05081
[37] Gvozdenović N, Laurent M (2008b) The operator \(Ψ \) for the chromatic number of a graph. SIAM J Optim 19(2):572-591 · Zbl 1213.05080
[38] Hamzaoglu I, Patel JH (1998) Test set compaction algorithms for combinational circuits. In: Proceedings of the 1998 IEEE/ACM international conference on computer-aided design (ICCAD ’98), New York, NY, USA, pp 283-289 · Zbl 1047.90038
[39] Helmberg C (2004) A cutting plane algorithm for large scale semidefinite relaxations. In: The sharpest cut. SIAM, Philadelphia, PA, pp 233-256 · Zbl 1136.90431
[40] Helmberg C, Rendl F (1998) Solving quadratic \((0,1)\)-problems by semidefinite programs and cutting planes. Math Program 82(3, Ser. A):291-315 · Zbl 0919.90112
[41] John, E; Yıldırım, EA, Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension, Comput Optim Appl, 41, 151-183, (2008) · Zbl 1168.90554 · doi:10.1007/s10589-007-9096-y
[42] Johnson DS, Trick MA, eds (1996) Cliques, coloring, and satisfiability. DIMACS series in discrete mathematics and theoretical computer science, 26. American Mathematical Society, Providence, RI · Zbl 1168.90554
[43] Jung, J; O’Leary, D; Tits, A, Adaptive constraint reduction for convex quadratic programming, Comput Optim Appl, 51, 125-157, (2012) · Zbl 1245.90082 · doi:10.1007/s10589-010-9324-8
[44] Kaliski, JA; Ye, Y, A short-cut potential reduction algorithm for linear programming, Manag Sci, 39, 757-776, (1993) · Zbl 0783.90073 · doi:10.1287/mnsc.39.6.757
[45] Karp RM (1972) Reducibility among combinatorial problems. In Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972). Plenum, New York, pp 85-103 · Zbl 1177.90411
[46] Laurent M, Rendl F (2005) Integer programming and semidefinite programming. In: Aardal K, Nemhauser GL, Weismantel R (eds) Discrete optimization. Handbooks in operations research and management science, vol 12. Elsevier, Amsterdam, pp 393-514 · Zbl 1194.90066
[47] Lovász, L; Schrijver, A, Cones of matrices and set-functions and 0-1 optimization, SIAM J Optim, 1, 166-190, (1991) · Zbl 0754.90039 · doi:10.1137/0801013
[48] McEliece, RJ; Rodemich, ER; Rumsey, HC, The lovász bound and some generalizations, J Combin Inform Syst Sci, 3, 134-152, (1978) · Zbl 0408.05031
[49] Mitchell, JE, Computational experience with an interior point cutting plane algorithm, SIAM J Optim, 10, 1212-1227, (2000) · Zbl 0999.90050 · doi:10.1137/S1052623497324242
[50] Mitchell JE (2009) Cutting plane methods and subgradient methods. In: Oskoorouchi M (ed) Tutorials in operations research Chapter 2, INFORMS, pp 34-61
[51] Mitchell, JE; Borchers, B, Solving real-world linear ordering problems using a primal-dual interior point cutting plane method, Ann Oper Res, 62, 253-276, (1996) · Zbl 0848.90086 · doi:10.1007/BF02206819
[52] Nesterov Y, Nemirovskii A (1994) Interior-point polynomial algorithms in convex programming volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 0824.90112
[53] Palagi L, Piccialli V, Rendl F, Rinaldi G, Wiegele A (2011) Computational approaches to max-cut. In: Handbook of semidefinite, conic and polynomial optimization: theory, algorithms, software and applications. International Series in Operations Research and Management Science. Springer, New York, pp 821-847 · Zbl 1334.90149
[54] Peña, J; Vera, J; Zuluaga, LF, Computing the stability number of a graph via linear and semidefinite programming, SIAM J Optim, 18, 87-105, (2007) · Zbl 1176.90611 · doi:10.1137/05064401X
[55] Rendl F (2012) Matrix relaxations in combinatorial optimization. In: Mixed integer nonlinear programming, vol 154. The IMA volumes in mathematics and its applications. Springer, Berlin, pp 483-511 · Zbl 1242.90201
[56] Rendl F, Rinaldi G, Wiegele A (2010) Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math Program 121(2, Ser. A):307-355 · Zbl 1184.90118
[57] Rhodes, N; Willett, P; Calvet, A; Dunbar, JB; Humblet, C, Clip: similarity searching of 3D databases using clique detection, J Chem Inf Comput Sci, 43, 443-448, (2003) · doi:10.1021/ci025605o
[58] Schrijver, A, A comparison of the delsarte and lovász bounds, IEEE Trans Inf Theory, 25, 425-429, (1979) · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072
[59] Sherali, HD; Adams, WP, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J Discret Math, 3, 411-430, (1990) · Zbl 0712.90050 · doi:10.1137/0403036
[60] Sloane, NJA, Unsolved problems in graph theory arising from the study of codes, Graph Theory Notes NY, 18, 11-20, (1989)
[61] Szegedy M, (1994) A note on the Theta number of Lovász and the generalized Delsarte bound. In: 35th Annual symposium on foundations of computer science, 20-22 November 1994, Santa Fe. New Mexico, USA, pp 36-39
[62] Tanay, A; Sharan, R; Shamir, R, Discovering statistically significant biclusters in gene expression data, Bioinformatics, 1, s136-s144, (2002) · doi:10.1093/bioinformatics/18.suppl_1.S136
[63] Tütüncü RH, Toh K, Todd MJ (2003) Solving semidefinite-quadratic-linear programs using SDPT3. Math Program 95(2, Ser. B):189-217 · Zbl 1030.90082
[64] Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev, 38, 49-95, (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[65] Wen, Z; Goldfarb, D; Yin, W, Alternating direction augmented Lagrangian methods for semidefinite programming, Math Program Comput, 2, 203-230, (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1
[66] Zhao, XY; Sun, D; Toh, KC, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J Optim, 20, 1737-1765, (2010) · Zbl 1213.90175 · doi:10.1137/080718206
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.