  


A MAXCUT 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 MAXCUT 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 MAXCUT can be applied. On a sample of 0/1 knapsack problems, we compare the lower bound on $f^*$ of the associated standard (Shor) SDPrelaxation 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 SDPrelaxation associated with the copositive formulation of $P$. Keywords: 0/1 programs; MAXCUT; SDPrelaxations; Category 1: Integer Programming (01 Programming ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Category 3: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: Download: [PDF] Entry Submitted: 05/23/2015 Modify/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  