If you consider participating in this lab, please write an informal application e-mail to Lukas Schürmann. This lab has an upper limit on the number of participants; please mention your experiences with Integer Linear Programming and Graph Algorithms and a list of the algorithmic-related courses you attended. Notice that we expect you to have some knowledge about linear programming and duality.

The Vertex Coloring Problem is a classical graph problem with applications in scheduling, register allocation, map coloring, and many more. For general graphs, it is an NP-hard problem. There exist multiple integer linear programming formulations to solve it.
In this lab, we will investigate and implement the set cover formulation, where we have to make use of the so-called column generation technique. On our way to implementing a complete Branch and Price algorithm, we will encounter different graph-manipulating techniques and other graph problems, such as the vertex cover problem or the independent set problem.
The goal is to get an insight into the Algorithm Engineering for integer linear programming.

Some related literature:

• Graph Theory
• Column Generation
• Column Generation Slides
• A Column Generation Approach for Graph Coloring
• Maximum-weight stable sets and safe lower bounds for graph coloring
• Vertex Packings: Structural Properties and Algorithms

_{DozentInnen: Mutzel, Schürmann}