A note on the Lovasz-Schrijver Semidefinite Programming Relaxation for Binary Integer Programs

arXiv1208.2263MaRDI QIDQ6234971FDOQ6234971

Publication date: 10 August 2012

Abstract: Binary Integer Programming (BIP) problems are of interest due in part to the difficulty they pose and because of their various applications, including those in graph theory, combinatorial optimization and network optimization. In this note, we explicitly state the Lovasz-Schrijver Semidefinite Programming (SDP) relaxation (in primal-standard form) for a BIP problem, a relaxation that yields a tighter upper-bound than the canonical Linear Programming relaxation.

This page was built for publication: A note on the Lovasz-Schrijver Semidefinite Programming Relaxation for Binary Integer Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6234971)