Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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


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

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