Optimization Online


A MAX-CUT formulation of 0/1 programs

Jean B Lasserre(lasserre***at***laas.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 )


Download: [PDF]

Entry Submitted: 05/23/2015
Entry Accepted: 05/23/2015
Entry Last Modified: 05/23/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society