User Tools

Site Tools


Lab Computational Analytics

Solving the Vertex Coloring Problem with a Branch and Price Algorithm

Lecturer Lukas Schürmann, Prof. Dr. Petra Mutzel
Module MA-INF 0402
BASIS Link2Basis
Type of Lecture LAB
CP 9


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.


Date When Where
Deadline application 10.09.2023
Introductory workshop 04.10.2023 - 06.10.2023 Pool U.1.042


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.

teaching/ws2023/lab-ca.txt · Last modified: 2023/10/02 09:46 by lukas.schuermann

Page Tools