Student projects

For students with a deep interest in optimization, and that have attended the appropriate courses, a project thesis in optimization is an excellent opportunity to acquire a deeper knowledge on the topic. This page gives an overview about:

The different project types, and the corresponding requirements
The project outcomes (written report and presentation)
The application procedure
The project topics

Also, please note that we often get more requests than what we can handle. Hence, we apologize in advance if we cannot supervise your student project.

Project types and requirements

In addition to the protected pagerequirements by D-MATH, the table below shows what courses we expect student to have successfully finished before writing a thesis in the group of Prof. Zenklusen.

Specialized Optimization courses include

Advanced Topics in Discrete Optimization
Network and Integer Optimization
Convex Optimization

In exceptional cases, other courses may qualify as specialized courses. Please discuss this with the study advisor.

Project outcomes

At the end of the project, students are required to hand in a written report and give a presentation. The presentation should last at most 30 minutes (make sure not to exceed this time) plus time for questions and answers.

Some hints and guidelines for composing the written report and the final presentation can be found in Downloadour tutorial (PDF, 3.4 MB) and on the D-MATH website.

Application procedure

Before you apply, please check the list of eligible supervisors for your respective thesis and degree program.

In order to apply for a Bachelor's thesis, a semester paper, or a Master's thesis, write an e-mail to the study advisor with the following information:

Your name
Your study program
Your current state of studies
What type of project you are interested in (Bachelor's thesis/semester paper/Master's thesis)
When you'd like to work on the project
The courses that you have attended at IFOR (and other relevant courses)
Whether you are more interested in a theoretically or practically inclined project

The study advisor should be contacted a few months before the desired start of the project.

Project topics

The topics we offer are typically aligned with current research thrusts/projects in the group, and thus change over time.

To give you an idea of some prior topics, hereafter we list some abstracts of theses completed in the Zenklusen Group in recent years.

Martin Nägele: Refuting a Conjecture of Goemans on Minimum Degree-Bounded Spanning Trees

In the degree-bounded spanning tree problem, we are given an undirected graph with edge costs and a degree bound for every vertex. The task is to find a spanning tree T whose degree at each vertex does not exceed the degree bound and T is of minimum cost among all such spanning trees. Even checking whether a feasible spanning tree exists is well known to be NP-hard. Thus, interest surged in understanding whether a small violation of the degree constraints may make it possible to efficiently obtain a spanning tree whose cost is not larger than the optimum spanning tree, which does not violate the degree constraints. In 2006, Goemans presented a nearly optimal algorithm, based on matroid intersection, which leads to a degree violation of at most 2 units. In 2007, Singh and Lau closed the gap by showing that iterative relaxation allows for obtaining the same result with degree violation of at most 1. Besides iterative relaxation, no other technique is known to lead to the same result. Interestingly, Goemans stated a conjecture which, if true, would imply that his matroid intersection approach would as well lead to a violation of at most 1 unit. In this work, we refute Goemans' conjecture, by refuting an even weaker version of it.

Simon Bruggmann: On the single-source unsplittable flow problem with costs

In the single-source unsplittable flow problem, we are given a directed graph whose arcs are assigned a capacity and a cost. There are a number of commodities with associated demands and terminals, and the task is to route all commodities simultaneously from a common source vertex to the given terminals such that the demand of each commodity is routed along a single path.

Dinitz, Garg, and Goemans (1999) showed that any flow f that is allowed to split the commodities can be transformed into an unsplittable flow f_unsp which has the property that for every arc a, f_unsp(a) exceeds f (a) by less than the maximum demand routed along a by the unsplittable flow f_unsp. Goemans conjectured that their result extends in the way that for each splittable flow f, there exists an unsplittable flow f_unsp which has the property above and which is at most as expensive as f.

We show that the conjecture holds for two special cases. For the first case, where we require the given graph to be 2-layered, we present an algorithm that is based on iterative relaxation and proves the conjecture in this context. The second case for which we prove the conjecture is the situation in which all demands are equal except for one which may be bigger. In particular, this yields an affirmative answer to the conjecture for the case where there are only two commodities.