Mixed Integer Programming

MINOA: Mixed-Integer Non-Linear Optimisation: Algorithms and Applications

MINOA will train a new generation of scientists in the rather young but fast growing field of mixed-integer nonlinear optimisation applications and algorithms, by enhancing research-related and transferable competences and exposure to the non-academic sector. Through self-organizing training events, the young researchers take responsibility at an early stage of their career. The settings provided by the hosting institutions empower the ESRs to become independent and creative researchers, which increases their employability. Mobility and internationality is provided through secondments within our international consortium that includes institutions from 6 European countries. Furthermore, network-wide events take place regularly.
Details
Participants: Frauke Liers, Martin Schmidt, Dennis Adelhütte

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