×

zbMATH — the first resource for mathematics

A MAX-CUT formulation of 0/1 programs. (English) Zbl 1408.90222
Summary: We show that the linear or quadratic 0/1 program \(\mathbf{P} \text{: } \min \{\mathbf{c}^T \mathbf{x} + \mathbf{x}^T \mathbf{F} \mathbf{x} : \mathbf{A} \mathbf{x} = \mathbf{b}; \mathbf{x} \in \{0, 1 \}^n \},\) can be formulated as a MAX-CUT problem whose associated graph is simply related to the matrices \(\mathbf{F}\) and \(\mathbf{A}^T \mathbf{A}\). Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. We also compare the lower bound of the resulting semidefinite (or Shor) relaxation with that of the standard LP-relaxation and the first semidefinite relaxations associated with the Lasserre hierarchy and the copositive formulations of \(\mathbf{P}\).

MSC:
90C20 Quadratic programming
90C10 Integer programming
90C22 Semidefinite programming
Software:
GloptiPoly; Mosek
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, E. D.; Andersen, K. D., The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm, (Frenk, H.; Roos, K.; Terlaky, T.; Zhang, S., High Performance Optimization, (2000), Kluwer Academic Publishers Dordrecht, the Netherlands), 197-232 · Zbl 1028.90022
[2] Bomze, I. M., Copositive optimization—recent developments and applications, European J. Oper. Res., 216, 509-520, (2012) · Zbl 1262.90129
[3] Bomze, I. M.; de Klerk, E., Solving standard quadratic optimization problems via linear, semidenite and copositive programming, J. Global Optim., 24, 163-185, (2002) · Zbl 1047.90038
[4] Burer, S., Copositive programming, (Anjos, M.; Lasserre, J. B., Handbook of Semidefinite, Conic and Polynomial Optimization, (2012), Springer New York), 201-218 · Zbl 1334.90098
[5] de Klerk, E.; Pasechnik, D. V., Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 875-892, (2002) · Zbl 1035.90058
[6] Dür, M., Copositive programming—a survey, (Diehl, M.; Glineur, F.; Jarlebring, E.; Michiels, W., Recent Advances in Optimization and its Applications in Engineering, (2010), Springer New York), 3-20
[7] Henrion, D.; Lasserre, J. B.; Lofberg, J., Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 761-779, (2009) · Zbl 1178.90277
[8] Lasserre, J. B., Optimisation globale et théorie des moments, C. R. Acad. Sci. Paris Sér. 1, 331, 929-934, (2000) · Zbl 1016.90031
[9] Lasserre, J. B., Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[10] Lasserre, J. B., Moments, positive polynomials and their applications, (2010), Imperial College Press London · Zbl 1211.90007
[11] Lasserre, J. B., An introduction to polynomial and semi-algebraic optimization, (2015), Cambridge University Press Cambridge
[12] Laurent, M.; Sun, Zhao, Handelman’s hierarchy for the maximum stable set problem, J. Global Optim., 60, 393-423, (2014) · Zbl 1326.90073
[13] Marshall, M., Error estimates in the optimization of degree two polynomials on a discrete hypercube, SIAM J. Optim., 16, 297-309, (2005) · Zbl 1132.90011
[14] Nesterov, Y., Semidefinite relaxation and nonconvex quadratic optimization, Optim. Methods Softw., 9, 141-160, (1998) · Zbl 0904.90136
[15] Palagi, L.; Piccialli, V.; Rendl, F.; Rinaldi, G.; Wiegele, A., Computational approaches to MAX-cut, (Anjos, M.; Lasserre, J. B., Handbook of Semidefinite, Conic and Polynomial Optimization, (2012), Springer New York), 821-847 · Zbl 1334.90149
[16] Rendl, F., Semidefinite relaxations for partitioning, assignment and ordering problems, 4OR, 10, 321-346, (2012) · Zbl 1262.90150
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.