Computational Integer Programming

Integer programming has a fascinating theory. On top of that, when it comes to actually solving large scale integer programs to optimality, usually a lot of engineering has to be done. This may include sophisticated relaxation techniques, cutting plane algorithms, problem decomposition, the use of problem adequate heuristics, and many more. more ...

Cycle Bases

We investigate classes of cycle bases of directed graphs. The most popular ones are those, which project onto a cycle basis for the underlying undirected graph, and those, which are induced by the non-tree arcs of some spanning tree (strictly fundamental cycle bases). But there is more to explore. Although generalized fundamental cycle bases were introduced already by Whitney (1935), the complexity status of finding a minimum generalized fundamental cycle basis is still open. The latter holds for integral cycle bases, too. These are important for periodic railway timetable optimization. more ...

Frequency Assignment

In the frequency assignment problem in cellular telephone networks the task is to allocate carrier frequencies to base stations in such a way that a possibly large amount of telephone traffic is supported and simultaneously a good quality of connections is guaranteed. This practical problem is closely related to the graph coloring problem. It includes the characteristic features of T-coloring, list coloring, and set coloring, and belongs thereby to NP-hard combinatorial problems. more ...

Network flows

Network flows are a corner stone of combinatorial optimization. They have numerous obvious and unreckoned applications in various areas, such as traffic, telecommunication, logistics, evacuation problems, computer science, medicine etc., as well as a lot of theoretical impact, e.g., for matchings, mesh generation and reductions. Striving for models closer to real world problems has motivated our group to pursue research in two directions: Dynamic flows and k-splittable flows. The former reflects the idea that a flow should indeed traverse the network in time. The latter accounts for the significant requirement of applications that a flow may not be decomposed in an arbitrary number of paths. more ...

Online optimization

In classic optimization one assumes complete knowledge of all input data that define a problem instance. However, it is unlikely that in practice those information are available in advance. Decisions have to be made based on incomplete knowledge, instead. This problem setting has motivated (among other directions) the research on online optimization. more ...

Routing problems

Routing problems concern the design of routes in a metric space or network. There exist a huge variety of routing problems. The probably most classic one is the Traveling Salesman Problem (TSP) which consists of determining a shortest Hamiltonian circuit or cycle in a graph. Applications of the TSP and routing in general arise in distribution management, in scheduling and in manufacturing. more ...

Scheduling

Sequencing and scheduling is motivated by questions that arise in production planning, in computer control, and generally in all situations in which scarce resources have to be allocated to activities over time. Currently, we investigate deterministic machine scheduling, project scheduling with varying processing times, and a generalized model for scheduling under uncertainty. more ...

VLSI Design

Very large scale integrated circuit layout (VLSI) is one of the amazingly growing areas in discrete mathematics and computing science of the last years, due to both its practical relevance and its importance as a trove of combinatorial problems. Usually, in VLSI design one distinguishes between the phase of placing physical components and the subsequent routing phase realizing the conducting connections between them. more ...