#
Monday Lecture and Colloquium

**Monday, December 13, 2010**

Konrad-Zuse-Zentrum für Informationstechnik Berlin

Takustrasse 7

14195 Berlin

room 2005

** Lecture - 14:15**

###
Giovanni Rinaldi - Istituto di Analisi dei Sistemi ed Informatica "Antonio Ruberti", Rom

### Polyhedral vs. SDP Methods for Max-Cut

*Abstract:*

Very large (but very sparse) instances of Max-Cut can be solved to
optimality using the methods of Polyhedral Combinatorics.
Unfortunately, for dense graphs these methods can only
solve instances of rather small size. For these graphs, methods based on
Semidefinite Programming appear to be much more effective. However, the
solution engines that these methods utilize do not exploit the sparsity
of the graph. Moreover, the bounds that they produce are typically
weaker than those obtained by polyhedral techniques. In the talk these
issues will be addresses and some recent results that overcome some of
the mentioned difficulties will be presented.

**Colloquium - 16:00**

###
Timo Berthold - ZIB, Berlin

### Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set
covering

*Abstract:*

We present Undercover, a primal heuristic for mixed-integer nonlinear
programming (MINLP). The heuristic constructs a mixed-integer linear
subproblem (sub-MIP) of a given MINLP by fixing a subset of the
variables. We solve a set covering problem to identify a minimal set
of variables which need to be fixed in order to linearise each
constraint. Subsequently, these variables are fixed to approximate
values, e.g. obtained from a linear outer approximation. The resulting
sub-MIP is solved by a mixed-integer linear programming solver. Each
feasible solution of the sub-MIP corresponds to a feasible solution of
the original problem.

Although general in nature, the heuristic seems most promising for
mixed-integer quadratically constrained programmes (MIQCPs). We
present computational results on a general test set of MIQCPs selected
from the MINLPLib.

Letzte Aktualisierung:
01.11.2010