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 ProgrammingMixed 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. |
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. |
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. |
Dynamic Graph ReliabilityDynamic 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. |
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. |
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. |
Iterative Aggregation for Network Design ProblemsAggregation 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. |
Phased Out Projects
Solving the Minimum Graph Bisection ProblemTwo 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. |
Binary Steiner Trees and their Application in PhylogenyBinary 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. |