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 typical work mode during a project
- 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 page requirements 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
- Network and Integer Optimization
- Convex Optimization
- Mathematical Optimization Lab
- Seminar: Advanced Topics in Discrete Optimization
In exceptional cases, other courses may qualify as specialized courses. Please discuss this with the study advisor.
Work mode
For most projects, you will be assigned a primary supervisor from our group who proposes the concrete project topic. Throughout your work, you will have regular meetings with your supervisor to guide you and discuss the different phases of the project.
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 10 minutes (make sure not to exceed this time) plus time for questions and answers.
Some hints and guidelines for composing the written report can be found 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
- Type of project (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)
- Optional: Whether you have a preference for a theoretically or practically inclined project
- Optional: CV and/or transcript. We are primarily looking for relevant coursework, prior research or coding experience. This would help us match you with the right project from our diverse pool of topics. Feel free to also list relevant experiences directly in the application email.
The study advisor should be contacted a few months before the desired start of the project. Note that we do not operate on a first-come, first-served basis and usually gather applications for a period of time before making our decisions.
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.
Eva Bradbrook: Pulse Pattern Optimisation for Laser Ablation
In eye laser surgery, laser pulses are shot into the cornea to ablate tissue and change the shape of the cornea. We look at the problem of finding a distribution of equally strong laser pulses over the cornea that minimises the error between the desired ablation and the collective ablation caused by the laser pulses. This work was done in collaboration with Ziemer Ophthalmic Systems AG.
We work with a simplified, completely circular model of the cornea. The main approach is to work on a polar grid and reduce the problem to one dimension by only optimising over the number of laser pulses on some fixed set of radii. For each radius, the pulses can then be distributed around the circle at that radius to give a distribution of laser pulses over the cornea.
Take −5 diopters as an example; we show that the maximum error of around 4.5 · 10-7 m can be obtained with our model, which is about half the height of the ablation caused by a single laser pulse at the highest point. This is an improvement on results obtained with more natural approaches by a factor of 10.
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 funsp which has the property that for every arc a, funsp(a) exceeds f (a) by less than the maximum demand routed along a by the unsplittable flow funsp. Goemans conjectured that their result extends in the way that for each splittable flow f, there exists an unsplittable flow funsp 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.