• Skip navigation
  • Skip to navigation
  • Skip to the bottom
Simulate organization breadcrumb open Simulate organization breadcrumb close
Department of Mathematics
  • FAUTo the central FAU website
  • de
  • UnivIS
  • StudOn
  • meincampus
  • CRIS
  • emergency help

Department of Mathematics

Navigation Navigation close
  • Department
    • Chairs and Professorships
    • Boards and Commissions
    • Organisation
    • Development Association
    • System Administration
    • Contact and Directions
    • Actual
    Portal Department of Mathematics
  • Research
    • Research Projects
    • Publications
    • Preprint Series Applied Mathematics
    Portal Research
  • Study
  • Events
  1. Home
  2. EDOM
  3. Projects
  4. Mixed Integer Programming

Mixed Integer Programming

In page navigation: EDOM
  • Overview
  • Team
    • Kevin-Martin Aigner
    • Edeltraud Balser
    • Andreas Bärmann
    • Kristin Braun
    • Jana Dienstbier
    • Patrick Gemander
    • Yiannis Giannakopoulos
    • Lukas Hager
    • Katrin Halbig
    • Beate Kirchner
    • Martina Kuchlbauer
    • Frauke Liers
    • Alexander Martin
    • Alexander Müller
    • Timm Oertel
    • Galina Orlinskaya
    • Florian Rösel
    • Hanno Schülldorf
    • Jonasz Staszek
    • Regine Stirnweiß
    • Sebastian Tschuppik
    • Friedrich Wagner
    • Dieter Weninger
    • Jorge Weston
  • Projects
    • Analytics
      • ADA Lovelace Center
      • Optimal Control of Electrical Distribution Networks with Uncertain Solar Feed-In
      • Optimization of medical care in rural environments
        • HealthFaCT Contents
      • EWave – Water Supply Energy Management System
      • LeOpIn
      • Robust Schedules for Air Traffic Management
      • RobustATM: Robust Optimization of ATM Planning Processes by Modelling of Uncertainty Impact
    • Energy
      • Robustification of Physical Parameters in Gas Networks
      • Adaptive MIP-Relaxations for MINLPs
      • Analysis of the German Electricity Market
      • MIP-based Alternating Direction Methods for High-Detail Stationary Gas Transport MINLPs
      • Decomposition methods for mixed-integer optimal control
      • Optimal allocation of gas network capacities
      • Energy System Analysis
      • Robust Power Load Balancing in Railway Networks
      • Smart Grid Optimization
    • Engineering and Physics
    • Logistics and Production
      • Driver Assistance Systems in Railway Traffic
      • Energy-Efficient Timetable Optimization
      • Joint Locomotive Scheduling and Driver Rostering in Rail Freight Traffic
      • Holistic optimization of trajectrories and runway scheduling
      • Optimized Production in the Tea Industry
      • OPs-TIMAL – Optimized processes for trajectory, maintenance and management of ressources and operations in aviation
      • Process optimization for hospital logistics
      • Expansion of the German Rail Freight Network
    • Mixed Integer Programming
      • Solver for Relaxations in General Mixed Integer Nonlinear Programming (SCIP/NL)
      • Development of new Linear and MIP Techniques for Supply Chain Management
      • Lamatto++
    • TRR 154 (Transregio)
  • Publications
  • PhD Theses
  • Teaching
  • Bachelor and Master Theses
  • Public Relations
  • News and Events
    • G’scheid schlau!
    • Friday@Noon
  • How to find us

Mixed Integer Programming

 

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, Katrin Halbig

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

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

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


Mixed Integer Programming Phased-Out

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

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

 

Friedrich-Alexander-Universität
Department of Mathematics

Cauerstraße 11
91058 Erlangen
  • Contact and Directions
  • Internal Pages
  • Staff Members A-Z
  • Imprint
  • Privacy
  • EN/DE
  • RSS Feed
Up