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 submit a written report and give a presentation. Presentations should last approximately 7–8 minutes (strictly capped at 10 minutes), followed by a Q&A session.

Some hints and guidelines for composing the written report can be found on the D-MATH website.

Project topics

Below you will find a list of categories and descriptions into which most of our offered and recently supervised projects fall. The topics we offer are typically aligned with our current research thrusts and projects, so they change over time. In particular, not all project categories may be available every semester.

In a typical theory project, students collaborate with their supervisor on an ongoing research project. Students start by working through a recent paper in detail to get up to speed with the state-of-the-art in a particular area. This is similar to what students do in the seminar 'Topics in Discrete Optimization'. From there, projects involve some or all of the following different approaches: we may dive deeper into the literature, we may try to improve the state-of-the-art for a specific problem, and we may implement algorithms to study empirical aspects of theoretical results. By their nature, the course and the outcome of these projects is hard to predict. It is not unusual to pivot and try different approaches as we understand a particular problem more deeply.

We have successfully introduced a new type of project that we call a generator project. In these projects, students use the Rust programming language to develop fully automated systems that generate interesting instances of a given problem, along with a verified solution and the corresponding solution path. These projects combine software engineering skills with a solid theoretical understanding of the problem structure in order to design effective generators. Furthermore, didactic aspects also play a key role when designing problems and determining the best ways to evaluate them. Typically, students build a small codebase from scratch: implementing data structures to represent problem instances and solutions, coding algorithms covered in the lectures, and extending them with their own ideas. In previous projects, students have also applied techniques such as integer programming or linear programming to address subproblems that arose.

Our group has a long-standing collaboration with Swiss Post, focusing on algorithms that optimize truck routing for parcel delivery. In the literature, this problem is referred to as the Vehicle Routing Problem (VRP) and is defined as follows: given a hub location, a set of customers, and a fleet of vehicles, the goal is to determine a set of hub-based tours that visit all customers. These tours may be subject to side constraints such as vehicle capacity or time windows, and the objective is to minimize the total distance of the routes. Within this framework, we encounter a variety of interesting subproblems that we aim to investigate. All projects in this context also involve coding in Rust.

These projects focus on applied scheduling problems, such as university course and exam timetabling. The overarching goal is to design algorithms that can produce feasible, high-quality timetables under diverse constraints, ranging from time constraints (e.g., avoiding unwanted weekend slots) and room constraints (e.g., capacity limits) to student-oriented constraints. The problem can be stated as assigning a set of courses or exams to specific time slots while ensuring that required conditions are met and desired properties are considered as much as possible. Because university-scale problem instances are large, exact optimal solutions are computationally infeasible in most cases. This gives rise to interesting projects around the development and analysis of targeted optimization techniques. As for most other applied projects, these projects involve coding in Rust.

We frequently collaborate with industry partners to solve complex combinatorial optimization problems arising in their daily operations. To address these challenges, we build custom software prototypes tailored to each partner's specific requirements. For example, in our work with Ziemer Ophthalmic Systems AG, we optimized laser pulse distributions over the cornea to minimize tissue ablation errors during eye surgery. In a project with Lyreco, we developed 3D bin packing heuristics with proven optimality bounds to improve parcel packaging efficiency.

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.
Project Type: Bachelor's thesis, semester paper, or Master's thesis.
Start Date: Projects typically begin at the start of the semester, though exceptions are possible under special circumstances.
The courses that you have attended at IFOR (and other relevant courses).
Project preferences: To indicate your project preferences, please select and rank only the categories described above that you are interested in working on, choosing from Theory (T), Generator (G), Vehicle Routing (V), Scheduling (S), and Industry Collaboration (I), allowing ties where desired. For example, '1: G, V, S, I; 2: T' indicates a preference for any applied project over Theory, whereas '1: T' indicates interest in Theory alone. Please note that you will not be considered for any category you do not rank.
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.

Example projects

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.

Enlarged view: Example plot of absolute errors obtained by our method at -5 diopters with 200 radii — Example: absolute errors obtained by our method at -5 diopters with 200 radii

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 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.