Mixed Integer Programming

Model driven deployment and extention of mixed integer programming methods to specific problems is the key technology in most of our projects. In this section you will find those projects which address general problems with more than one specific application.

Ongoing Projects

Solver for Relaxations in Mixed Integer Nonlinear Programming

Mixed Integer Nonlinear Programming (MINLP) generalizes classical Mixed Integer Programming (MIP) by allowing nonlinearities in the objective function and constraints. The aim of the project is to integrate a nonlinear nearly active set sqp algorithm into SCIP as a replacement for the simplex algorithm. The main advantage of those algorithms over classical Interior Point algorithms are better resolve capabilities. Further they do not require local convexity of the problem which is important for the use in minlp heuristics during the Branch&Bound Process. Classical primal-dual implementations of actives set SQP algorithms like SNOPT fail to handle problems with high degrees of freedom which is relevant in global optimization.
Details
Participants: Thorsten Gellermann

Development of new Linear and MIP Techniques for Supply Chain Management

The method of choice to find optimal solutions in SCM is linear and integer programming. Nevertheless, there are big challenges to overcome - concerning both hardware and algorithms - due to very detailed and therefore large models. Additionally there may occur numerical difficulties that standard techniques cannot deal with.
Details
Participants: Dieter Weninger

Lamatto++

Lamatto++ is a framework to model mixed-integer nonlinear programming problems especially on (but not limited to) networks. Lamatto++ is completely written in C++ and has interfaces to CPLEX, GUROBI, SCIP and GAMS, where the latter provides access to a large collection of solvers for roughly all kinds of mathematical programming problems.
Details
Participants:
Antonio Morsi, Björn Geißler

Dynamic Graph Reliability

Dynamic Graph Reliability is a PSPACE-hard problem. In a graph whose edges are subject to failure one searches an optimal strategy to traverse this graph from a given start node s to a given target node t. The graph is falling apart while we traverse it. In this project we investigate a variety of restricted subclasses in order to gain insight in the structural aspects that induce the high complexity of the problem. We identified several tractable subclasses that are proven to be in P. We are currently searching for a subclass located in the complexity class NP.
Details
Participants: Nicole Ziems

Constrained Nonlinear Binary Optimization

The problem of optimizing a nonlinear objective function over integer variables subject to linear constraints arises in many applications. However, it is much harder to solve than integer linear programs in general. Previous approaches are either restricted to very special problems or can only solve small instances. In the project, we focus on nonlinear integer problems that could be solved efficiently for linear objectives. Furthermore, the structure of the feasible solutions is known. Quadratic objectives are a prominent special case. The quadratic assignment problem, the quadratic linear ordering problem and the quadratic matching problem are examples for problems in this class. Starting from a linearization of the nonlinear problem version, we aim at developing general cutting plane approaches leading to improved branch-and-cut algorithms.
Participants:  Frauke Liers

Exact Solution Approaches for Quadratic Matching

For an undirected graph with real edge costs the well known matching problem (MP) asks for a subset of non-adjacent edges such that the sum of the edge costs of the matched edges is maximum. It is well known, that the matching problem can be solved in polynomial time. However, the situation changes when additional costs for each edge pair are introduced that occur whenever the edge pair is contained in a solution. The problem can be modelled as a matching problem that maximises a quadratic objective in the edge variables. This quadratic matching problem (QMP) generalises the quadratic assignment problem (QAP), as the QAP is a perfect QMP on a bipartite graph. Just as the QAP the QMP is an NP-hard optimization problem. Applications of the QMP exist in computer vision, when for example a moving person needs to be identified automatically on photos that are taken within a short period of time. In general quadratic binary optimization problems are hard to solve even for small instances. In this project we focus on exact solution approaches for quadratic matching problems. We study the structure of these problems and develop and implement algorithms to solve QMPs exactly.
Participants: Frauke Liers, Lena Hupp

Iterative Aggregation for Network Design Problems

Aggregation is a coarsening process that omits details but ensures a global view on the complete problem. We investigate exact approaches for solving network expansion problems based on an iterative graph aggregation procedure. Starting with an initial aggregation, a sequence of master problems are solved over increasingly fine-grained representations of the original network. In each step, a set of subproblems is solved that either prove optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. We aim at expanding our algorithms, that have successfully been used for linear single-commodity network design problems, to problem settings that involve additional complicating features.
Participants: Maximilian Merkert, Christoph Thurner

Phased Out Projects

Solving the Minimum Graph Bisection Problem

Two approaches to solve combinatorial optimization problems have established themselves in the recent years. These are: integer programming methods, like branch-and-cut algorithm based on a linear relaxation, and the semidefinite programming methods with spectral bundle algorithms. In our project we combine both methods and investigate the magnitude of semidefinite relaxation in a branch-and-cut algorithm applied for the minimum graph bisection problem.
Contact: Alexander Martin


Binary Steiner Trees and their Application in Phylogeny

Binary Steiner trees are very important in biological and evolutionary questions. According to current theories of evolution, all species share a common history and are linked by common ancestors. These ancestral relationships can be represented by evolutionary trees such as tree alignments or phylogenetic trees. The problem of constructing such trees can be modeled as a binary Steiner tree problem. We study binary Steiner trees and their extension to general degree-constrained Steiner trees.
Details
Contact: Alexander Martin