A MAX-CUT formulation of 0/1 programs. (English) Zbl 1408.90222

Lasserre, Jean B.

Oper. Res. Lett. 44, No. 2, 158-164 (2016).

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

Keywords:

linear and quadratic 0/1 programs; MAX-CUT problem; LP- and semidefinite relaxations

Software:

GloptiPoly; Mosek

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