A MAX-CUT FORMULATION OF 0/1 PROGRAMS
UNE FORMULATION MAX-CUT DES PROGRAMMES 0/1
Résumé
We consider the linear or quadratic 0/1 program
$$\P:\quad f^*=\min\{ \c^T\x+\x^T\F\x : \:\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 $(G,V)$ whose connectivity is related to the
connectivity of the matrix $\F$ and $\A^T\A$, 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$.
On considère le programme 0/1 linéaire ou quadratique $$\P:\quad f^*=\min\{ \c^T\x+\x^T\F\x : \:\A\,\x =\b;\:\x\in\{0,1\}^n\},$$ où $\c\in\R^n$ , $\b\in\Z^m$ , $\A\in\Z^{m\times n}$ et $\F\in\R^{n\times n}$ est symmétrique. On montre que P peut être formulé comme un problème MAX-CUT dont la forme quadratique forme associée est explicite. En particulier, à P on peut associer un graphe (G, V) dont la connectivité est liée à lea connectivité des matrices F et A^TA, et P revient à trouver une coupe pondérée maximale dans ce graphe. Donc on peut appliquer tout l'arsenal des techniques d'appoximation du problème MAX-CUT can be applied. Sur un échantillon de prpblèmes de sac-à-dos 0/1, on compare la borne inférieure f * de la relaxation SDP de Shor avec la relaxation linéaire classique où {0, 1}^n est remplacé par [0, 1]^n (qui résulte donc en un PL si F = 0 et un programme quadratique si F est positive définie). On compare aussi notre borne inférieure avec celle de la première relaxation SDP associée à la formulation copositive de P.
Origine : Fichiers produits par l'(les) auteur(s)