University of Cologne

Faculty of Mathematics and Natural Sciences
Computer Science Department - Prof. Dr. Michael Jünger

Navigation: PeopleStaff

Dr. Sven Mallach

Universität zu Köln
Institut für Informatik
Weyertal 121, D-50931 Köln
Postanschrift (Postal address):
Albertus-Magnus-Platz, D-50923 Köln
Fon: +49/221/470-89782
eMail: mallach(at)

6. Etage, Raum 6.10

Main Research Projects

The Multiprocessor Scheduling Problem with Communication Delays

Given a number P of processors, this problem asks for a minimum makespan schedule of tasks whose dependencies are given by a task graph G=(V,A). Each task has a processing time and each precedence relation between two tasks is associated with a communication delay that becomes effective whenever the two tasks are assigned to different processors. We study, develop and improve mixed-integer programming formulations for this problem in terms of their size, strength and modeling complexity.


The Vertex Separation Problem in Directed Graphs

The vertex separation number is a graph parameter with several applications in practice. Moreover, it is equivalent to the minimum width of a path decomposition of the graph. A mixed-integer programming formulation is developed that is very compact in comparison to existing ones such that it can hopefully be applied to compute the vertex separation number of larger digraphs.

Pre-PhD Projects

Optimal Basic-Block Instruction Scheduling for Single-Issue Processors

Instruction Scheduling is NP-hard in general. We successfully solve instances of relevant size for processors with arbitrary latencies using a branch-and-cut approach that is based on the linear ordering problem.

Other researchers involved: M. Jünger


Exact Offset Assignment - Optimal Address Code Generation for Special-Purpose Processors

Offset Assignment is a memory-addressing problem arising in special-purpose processors (DSPs, ASIPs, ...). The task is to compute (a) a memory layout for statically allocated variables and (b) an assignment of address registers to variable accesses. Solving this problem to optimality is NP-hard even for only one address register. We provide a branch-and-cut approach that delivers optimum solutions also for multiple registers.

Other researchers involved: R. Castañeda Lozano, M. Jünger

General Interests

  • Combinatorial optimization and integer programming
  • Applications of the above to problems arising in technical computer science, embedded systems
  • Smart modeling of complex optimization problems with emphasis on their practical solvability
  • Linearization Techniques for (naturally) quadratically constrained problems
  • Ordering and sequencing problems, scheduling, compaction, address code generation
  • Computational complexity of special cases of the above mentioned problems
  • Selected chapters of topological graph theory and graph drawing
  • Algorithm engineering, especially for numerics and graph algorithms
  • Hardware-oriented computing and optimization / shared-memory parallelization


  • Best Presentation Award for the talk on "Optimal general offset assignment" given at the SCOPES 2014 conference.
  • Best Presentation Award for the talk on "Solving the Simple Offset Assignment Problem as a Traveling Salesman" given at the M-SCOPES 2013 conference.

Teaching (in german)


  • Seminar Forschungsnahe Programmierprojekte in C++ (WS 16/17)
  • Übungen zur Vorlesung Automatisches Zeichnen von Graphen (WS 15/16)
  • Übungen zur Vorlesung Algorithmen zur linearen und diskreten Optimierung (SS 15)
  • Übungen zur Vorlesung Automatisches Zeichnen von Graphen (WS 12/13)
  • Übungen zur Vorlesung Algorithmen zur linearen und diskreten Optimierung (SS 12)
  • Vorlesung Programmierkurs (WS 09/10)
  • Übungen zur Vorlesung Automatisches Zeichnen von Graphen (SS 09)

Betreute Master- und Diplomarbeiten (Co-Betreuung zu Prof. Dr. M. Jünger):

  • C. Reifferscheid - Kommutativität im General Offset-Assignment (2016)
  • S. Houben - Flottenzuordnung mittels Minimalkostenflusstechniken (2014)
  • L. Tepaße - Untersuchung einer IP-Formulierung und Entwicklung eines Branch & Cut-Algorithmus zur Lösung des Single-Issue Instruction Scheduling Problems (2013)
  • K. Zimmer - Ein Branch-and-Cut-Algorithmus für Mehrschichten-Kreuzungsminimierung (2013)
  • D. Feld - Effiziente Vektorisierung durch semi-automatisierte Codeoptimierung im Polyedermodell (2011)

Betreute Bachelorarbeiten:

  • U. Schmidt-Kraepelin - Effiziente Separation und Experimentelle Analyse von 3-opt Ungleichungen (2016)
  • M. Frohn - Minimale s-(t,u)-Schnitte (2015)
  • C. Reifferscheid - Matroide - Ein Überblick über Dualität, Greedy-Algorithmen, Schnitte und Vereinigung (2013)
  • A. E. M. Lukner - Gomory-Hu-Bäume und die Rolle sich nicht kreuzender Schnitte (2012)
  • L. Schlenke - Simple Offset Assignment (2012)
  • S. Kuhnke - Kompaktierung einer orthogonalen Zeichnung (2011)
  • L. Dominguez Rodriguez - Ein exaktes Separationsverfahren für Dk-Ungleichungen (2011)