zbMATH — the first resource for mathematics

An explicit exact SDP relaxation for nonlinear 0-1 programs. (English) Zbl 1010.90515
Aardal, Karen (ed.) et al., Integer programming and combinatorial optimization. 8th international IPCO conference, Utrecht, Netherlands, June 13-15, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2081, 293-303 (2001).
Summary: We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent convex positive semidefinite program in $$2^n-1$$ variables. The optimal values of both problems are identical. From every optimal solution of the former one easily find an optimal solution of the latter and conversely, from every solution of the latter one may construct an optimal solution of the former.
For the entire collection see [Zbl 0967.00091].

MSC:
 90C30 Nonlinear programming 90C22 Semidefinite programming 90C25 Convex programming
Full Text: