Practical applications of combinatorial optimization and efficient algorithms

The group, overlapping with the algorithms group, is dealing with practical applications of combinatorial optimization and efficient algorithms. The primary goal is to find effective means to achieve good solutions to very complex discrete optimization problems, either resulting directly from, or closely related to real-life problems. Examples are scheduling of production plants, staff scheduling, route scheduling and timetabling problems.

The group is dealing with both exact algorithms and (meta-)heuristics. Most often the above mentioned problems are NP-hard, even in very simplified forms. Moreover, in many practical applications these problems must be solved quickly. Therefore, an important focus of the group is to find fast algorithms to solve the problems to optimality. Where this turns out impossible in practice, heuristics to find close optimal solutions are designed.

Subjects of research are among other things: algorithms for variants of the vehicle routing problem, (job-shop) scheduling problems and variants of timetabling problems. Both single and multi-objective issues are considered. We use statistical tools to configure algorithm parameters and to assess which algorithms are best suited for solving a given practical problem.

On a more theoretical level the group is working with different graph theoretical problems of great relevance to practical applications. Examples are increasing the connectivity in networks, problems concerning disjoint spanning trees and the problem of finding a tree whose edge removal would ruin the connectivity of the remaining graph as much as possible.

The group has collaborated with several Danish companies and public institutions, among others B&O, Cabinplant, DSB S-tog, FKI Logistex, Odense kommune, OUH, Rambøll Informatik, Simcon A/S, Air Support and OE3i.


Jørgen Bang-Jensen
Daniel Merkle
Marco Chiarandini

To give you the best possible experience, this site uses cookies Read more about cookies

Accept cookies