SCIP - Solving Constraint Integer Programs

Contact: Marc Pfetsch (pfetsch [ a t ] opt [ d o t ] tu-darmstadt [ d o t ] de)

Solving Mixed-Integer Semidefinite Programms

We developed a framework for solving general MISDPs. This framework is using SCIP as branch-and-bound implementation and DSDP as SDP solver.

Details

Contact: Sonja Mars (smars [ a t ] opt [ d o t ] tu-darmstadt [ d o t ] de)

SPP 1253: Adaptive Multilevel SQP-Methods for PDAE-Constrained Optimization with Restrictions on Control and State. Theory and Applications

The aim of this project is to develop, analyze and apply highly efficient optimization methods for optimal control problems with control- and state-constraints governed by time-dependent PDAEs. We combine in a modular way modern space-time adaptive multilevel finite elements methods with linearly implicit time integrators of higher order for time-dependent PDAEs and modern multilevel optimization techniques. The aim is to reduce the computational costs for the optimization process to the costs of only a few state solves. This can only be achieved by controlling the accuracy of the PDAE state solver and adjoint solver adaptively in such a way that most of the optimization iterations are performed on comparably cheap discretizations of the PDAE. We will focus on two exemplary applications.
Details
Contact: Stefan Ulbrich (ulbrich [at] mathematik.tu-darmstadt.de), J. Carsten Ziems (ziems [at] mathematik.tu-darmstadt.de

Solvers for Mixed Integer Second Order Cone Programming

Mixed Integer Second Order Cone  Programs (MISOCPs) are characterized by a linear objective function that is minimized over the intersection of an affine subspace and the cartesian product of second order cones of various dimensions plus the additional constraint that a subset of the variables have to attain integer values. These problems have various applications in finance or engineering, for example simplified optimization models in the context of gas networks, cardinality-constrained portfolio optimization problems or the design of minimum length connection networks. 
MISOCPs are not solvable by standard convex MINLP solvers, since the constraint functions are not differentiable.
We develop two approaches to solve MISOCPs: a classical branch and bound framework and a branch-and-bound based outer approximation approach, which is an extension of the outer approximation approach for continuously differentiable problems to subdifferentiable second order cone constraint functions.
In the context of both approaches lift-and-project based cutting techniques for mixed 0-1 problems can be applied.

Contact: Sarah Drewes (drewes [at] mathematik [dot] tu-darmstadt [dot] de)

Solving Copositive Programs

Copositive programs are linear optimization problems over the cone of copositive matrices, i.e. the cone of those matriceswhich induce a quadratic form that is nonnegative on the nonnegative orthant. They can be viewed as the next step of generalization starting from ordinary linear programs and semidefinite programs. Copositive programs arise in many applications: Combinatorial problems like max clique, graph partitioning or the quadratic assignment problem can be stated in this form. Moreover, every quadratic problem with binary constraints also fall into this framework. From a complexity point of view, copositive problems are NP-hard, and even to decide whether a given matrix has this property is an NP-hard problem. The aim of this research project is therefore to formulate necessary and suffcient conditions for copositivity, to find polyhedral approximations of the copositive cone and, based on this theory, to develop effcient algorithms to solve these problems.

Contact: Stefan Bundfuss (bundfuss [at] mathematik.tu-darmstadt.de)