A MAX-CUT formulation of 0/1 programs

We consider the linear or quadratic 0/1 program \[P:\quad f^*=\min\{ c^Tx+x^TFx : \:A\,x =\b;\:x\in\{0,1\}^n\},\] for some vectors $c\in R^n$, $b\in Z^m$, some matrix $A\in Z^{m\times n}$ and some real symmetric matrix $F\in R^{n\times n}$. We show that $P$ can be formulated as a MAX-CUT problem whose quadratic form criterion is explicit from the data of $P$. In particular, to $P$ one may associate a graph whose connectivity is related to the connectivity of the matrices $F$ and $A^TA$, and $P$ reduces to finding a maximum (weighted) cut in such a graph. Hence the whole arsenal of approximation techniques for MAX-CUT can be applied. On a sample of 0/1 knapsack problems, we compare the lower bound on $f^*$ of the associated standard (Shor) SDP-relaxation with the standard linear relaxation where $\{0,1\}^n$ is replaced with $[0,1]^n$ (resulting in an LP when $F=0$ and a quadratic program when $F$ is positive definite). We also compare our lower bound with that of the first SDP-relaxation associated with the copositive formulation of $P$.

Article

Download

View A MAX-CUT formulation of 0/1 programs