- A MAX-CUT formulation of 0/1 programs Jean B Lasserre(lasserrelaas.fr) Abstract: 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$. Keywords: 0/1 programs; MAX-CUT; SDP-relaxations; Category 1: Integer Programming (0-1 Programming ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: Download: [PDF]Entry Submitted: 05/23/2015Entry Accepted: 05/23/2015Entry Last Modified: 05/23/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.