Selected Research Projects

Exact Maximum Cut and Binary Quadratic Programming

I am currently acting as a principal investigator in a research project that -- seen as a whole -- is joint work with Jonas Charfreitag, Michael Jünger, Petra Mutzel, and Angelika Wiegele.

In different branches of this project, we are integrating solution techniques from polyhedral combinatorics, integer linear programming, and semidefinite programming as well as effective preprocessing and modeling techniques in order to obtain a fast exact solver for general Maximum Cut and Binary Quadratic Optimization instances.

An early yet visible outcome of this project is the web-based solver service McSparse for sparse problem instances, as well as an accompanying publication.

Previous research constituting one of the many pillars of this project is about facet-only separation algorithms for the odd cycle inequalities associated to the cut polypope, i.e., the convex hull of (edge) incidence vectors corresponding to a bi-partitioning of a graph.

Inductive Linearization for Binary Quadratic Programs with Linear Constraints

As a particular example of entirely independent research, in this project I propose a linearization technique for binary optimization problems having linear constraints and, in addition, either a quadratic objective function, or quadratic constraints, or both. It can be applied to the general case, and is well-suited especially for a rather sparse set of product terms and if the coeffcients of the (normalized) left and right hand sides of the linear constraints are rather small. In this case, an inductive linearization of the original problem that is compact, and whose continuous relaxation is strong, is likely to exist.

The key concept of the technique is to link the product terms present in the problem to their factors by thoroughly multiplying some of the present linear constraints by original variables, and to then replace the resulting products by linearization variables. Doing this in a prescribed way, these linearization variables are then guaranteed to retain the correct solution values without any further effort. For several well-known combinatorial optimization problems such as the quadratic assignment problem, the quadratic traveling salesman problem, or the quadratic knapsack problem, the continutions relaxations resulting from this technique are provably at least as strong as the so-called standard linearization.

A recent and large-scale computational study demonstrates some of the potentials of this method in practice.

Sophisticated Mixed-Integer Programming and Algorithms for Combinatorial Optimization

It is my passion to design and improve mathematical models, especially mixed-integer programming formulations, of Combinatorial Optimization and Operations Research problems with emphasis on their better practical solution. Moreover, I design and implement sophisticated solution techniques like Branch-and-Cut Algorithms that go far beyond “plugging a model into a solver”. Naturally, this goes hand in hand with Algorithm Engineering as well as the design and application of Approximation (or heuristic) Algorithms and efficient Data Structures. In order to solve the separation problems associated with the constraints that arise in the respective integer programs, I also frequently employ Graph Theory, Max-Flow / Min-Cut algorithms, Shortest Path algorithms, or Dynamic Programming.

Problems tackled in this line of research include e.g.:

  • Sequential (Instruction) Scheduling
  • Multiprocessor Scheduling with Communication Delays
  • Memory Layout and Access Optimization
  • The Linear Ordering Problem
  • The Traveling Salesman Problem
  • The (Quadratic) Assignment Problem
  • The Graph Layering Problem
  • The Pathwidth or Vertex Separation Problem