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
Germany
Fon: +49/221/470-89782
Fax: 
eMail: mallach(at)informatik.uni-koeln.de

6. Etage, Raum 6.10

Main Research Projects

Linearization Techniques for Binary Quadratic Programs

We elaborate advanced linearization techniques for (specially structured) 0/1 integer programs with quadratic terms in the objective function and / or constraints.

 

The Multiprocessor Scheduling Problem with Communication Delays

This problem asks for a minimum makespan multiprocessor schedule of a set 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 Pathwidth Problem

The vertex separation number and the pathwidth are graph parameters with several applications in practice. We develop mixed-integer programming formulations that are compact in size and yield comparably strong lower bounds.

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

  • Mixed-Integer Programming and Combinatorial Optimization
  • Smart modeling of complex optimization problems with emphasis on their practical solvability
  • Linearization Techniques for quadratically constrained problems
  • Ordering and sequencing problems, in particular scheduling, compaction, address code generation
  • Computational complexity of special cases of the above mentioned problems
  • Selected problems of topological graph theory and graph drawing
  • Algorithm engineering, especially for numerics and graph algorithms
  • Hardware-oriented computing and optimization / shared-memory parallelization

Awards

  • 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)

Lehrveranstaltungen:

  • 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)