Monday, December 13, 2010
Konrad-Zuse-Zentrum für Informationstechnik Berlin
Lecture - 14:15
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
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.