This page shows **all publications** that appeared in the IASI annual research reports.
Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with
author names.

**
Show all publications of the year
ALL, with author Rinaldi G., in the category IASI Research Reports
(or show them all):**

IASI Research Report n. 08-11 (Previous Next) Rendl F.,

Giovanni Rinaldi,

Wiegele A.Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxationsABSTRACT We present a method for finding exact solutions of
Max-Cut, the problem of finding a cut of maximum weight in a weighted
graph. We use a Branch-and-Bound setting, that applies a dynamic
version of the bundle method as bounding procedure. This approach
uses Lagrangian duality to obtain a ``nearly optimal''
solution of the basic semidefinite Max-Cut
relaxation, strengthened by triangle inequalities. The expensive
part of our bounding procedure is solving the basic semidefinite
relaxation of the Max-Cut problem, which has to be done several times
during the bounding process.
We review other solution approaches and compare the numerical results
with our method. We also extend our experiments to instances of
unconstrained quadratic 0-1 optimization and to instances of the graph
equipartition problem.
The experiments show, that our method nearly always outperforms all
other approaches. In particular, for dense graphs, where linear
programming based methods fail, our method performs very well. Exact
solutions are obtained in a reasonable time for any instance of size
up to $n=100$, independent of the density. For some problems of special
structure we can solve even larger problem classes. We could prove
optimality for several problems of the literature where, to the best
of our knowledge, no other method is able to do so.
Keywords: maximum cut; cut polytope; semidefinite programming;
unconstrained binary quadratic optimization.