A max-cut formulation of 0/1 programs

Abstract

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

To appear in Operations Research Letters. Rapport LAAS 15190