Student Projects

For students with a deep interest in optimization and that have attended an appropriate number of optimization courses, it is an excellent opportunity to deepen their knowledge acquired in these courses by carrying out a thesis in optimization. On this page, we give an overview about:

• the types of projects offered by the Institute for Operations Research and the corresponding requirements;
• the research documents that you need to hand in and the presentation you are supposed to give at the end of such a project;
• the possible project topics we offer;
• the application procedure.

Project Types and Requirements

* A=independent project; D=diploma thesis. The credit points and working hours correspond to the respective quantities in the Mathematics studies. Mathematics Master students work full-time for 5 months at their Master Thesis. The Institute for Operations Research does not take any responsibility for the correctness of the information provided in this column. Relevant is the information given in the Mathematics programme regulations and in the ETH course catalogue. Students from other programmes are kindly asked to check their programme regulations for the corresponding rules.

Reports and Presentations

At the end of any project that is conducted by the Institute for Operations Research, students have to hand in a written report and to give a presentation about their work. Presentations of Bachelor and Semester Projects last 25 minutes (plus 5 minutes for questions at the end), whereas Master Thesis can be presented for 40 minutes (plus 5 minutes for questions at the end).

In the first half of every semester (provided that there is an appropriate number of interested students), the Institute for Operations Research organizes a tutorial with hints and guidelines for composing the written report and the final presentation. The slides of the last tutorial can be downloaded here.

Possible Topics

• Applications of Convex Optimization in Finance, Artificial Learning, or Data Analysis
  Since the development of powerful software for Convex Optimization problem (and more specifically, for Semidefinite Optimization), the number of applications of this field has increased dramatically, in numerous engineering disciplines. However, most powerful software for Convex Optimization use so-called Interior-Point Methods. These algorithms have remarkable convergence properties. However, they suffer for an important drawback: if the problem is very large, the cost of the very first iteration is high to be reasonably affordable. An other type of methods, namely Fast Gradient Methods and numerous variants, have been studied to deal with these large problems.
  These large-scale instances emerge in many applications, for instance in the problem of image deblurring, image segmentation, reconstruction of sparse correlation matrices between financial assets, boosting techniques in artificial learning, and so on. It some cases, Fast Gradient Methods cannot be applied directly to these problems, but rather specially tailored variants. The goal of the work is to study the applicability of Fast Gradient Methods to a selected application.
• Inventory Management
  Business operations rely increasingly on a well structured and smoothly operating supply chain. Ensuring that the right quantity of a certain product is present at the right place at the right time is crucial for keeping costs low and sales high. Several models have been used to describe various real situations, which lead to optimization problems with the objective to minimize the costs and maximize the revenue. The key point for the optimized decisions to work in practice is that they take into consideration uncertainty in either the demand or the business procedures and that they are adaptive in the information gradually been revealed as time evolves. That is why techniques from multistage stochastic and robust optimization have been extensively used. We are interested in analyzing these highly complex problems to develop algorithms with provable satisfactory performance both in theory and in practice. We are also interested in introducing new models that increase the flexibility of the decision maker in benefiting from the various trade-offs and in quantifying the effects of uncertainty in the incurred costs and revenues.
• Mixed-Integer Convex Optimization
  In Mixed-Integer Convex Optimization, one needs to minimize a convex function over a convex set, with the supplementary requirement that some variables must take an integral value. Many fascinating questions are still unanswered in this very new field.
  It is known that these optimization problems are extremely hard in general. Still, we have discovered recently some non-trivial instances that admit an efficient optimization algorithm. The exact boundary between these relatively easy instances and overwhelmingly hard ones is starting to uncover, and any result in this direction is of an importance that is difficult to overestimate.
  Provably efficient optimization algorithms for suitable subclasses of these problems must use at the same time techniques from Convex Programming and Mixed-Integer Programming. As of now, we are beginning to have an idea on how to orchestrate the interplay between the convex structure of the objective function and the discrete feasible set.
  A project in Mixed-Integer Convex Optimization would give you the opportunity of working in a pioneering scientific field in very close collaboration with keen researchers.
• Mixed-Integer Linear Optimization
  Such optimization problems, called MILP's, involve finitely many variables, some of which are required to be integers. The aim is to maximize or minimize a linear objective function over a set of finitely many linear equations and inequalities. The presence of both types of variables, discrete and continuous, makes it difficult to solve MILP's algorithmically. There is a great variety of solution techniques which can be subdivided into primal and dual methods.
  A standard (dual) approach to solve MILP's is to apply cutting plane methods. Here, the underlying MILP is used to construct a sequence of linear optimization problems whose formulations are improved by successively adding linear constraints, so-called cutting planes, until one of the linear optimization problems has an optimal solution which satisfies the integrality conditions on the integer constrained variables. For many combinatorial problems, it is possible to immediately deduce several families of cutting planes by exploiting the inherent combinatorial structure of the problem. However, for general MILP's, no structural properties can be used. The generation of cutting planes must rather be based on the objective function and the given, unstructured set of linear equations and inequalities.
  Since many industrial problems can be formulated as MILP's, there is an ongoing interest in novel solution techniques. Most of the currently available cutting plane algorithms are based on geometric concepts. In order to generate strong cutting planes, one needs to understand the interplay between algebra and geometry. One promising way to gain insight is to focus on so-called lattice-(point-)free polyhedra.
• Mixed-Integer Nonlinear Optimization with Applications in Chemical Engineering
  In chemical engineering, a major task is to determine a cost-optimal process design for a given production process. This task can be often modeled as a mixed-integer nonlinear optimization problem (MINLP) which needs to be solved globally. Although current state-of-the-art solvers could have been significantly improved in the past, global optimization of MINLPs is still extremely difficult. The goal of this research project is to develop new mathematical tools that allow to design improved global optimization algorithms. This will require an extensive investigation of the structure of the MINLPs. We, in particular, focus on MINLPs arising in the context of the Collaborative Research Centre SFB/TR 63 "InPROMPT - Integrated Chemical Processes in Liquid Multiphase Systems" funded by the German Research Foundation (DFG). See also here.
• Railway Networks
  For offline planning, we follow a two-level approach based on two different abstraction levels of the infrastructure and safety system. On the macroscopic level, given an intended commercial offer for the whole railway network, we abstract from the detailed track topology for creating a (flexible) timetable. On the microscopic level, starting with the flexible timetable from the macrosopic level, we construct detailed train schedules by considering the precise topology, the corresponding safety system as well as accurate train dynamics. In the macroscopic level big instances of the so-called periodic event scheduling problems have to be solved. The problems lead to mixed integer linear problems and we look for decomposition methods to accelerate the search for feasible and/or optimal solutions.
  The second branch of our current work is a collaboration framework with SBB for adaptive train disposition in complex station areas. A prototype for train disposition of the area Berne, Switzerland has been developed. We formulate train disposition as constrained assignment problems, which result in binary linear problems. To cope with the dynamically changing situation of a railway network, the problem is updated and solved iteratively every minute.
• Risk Management
  The construction of a plethora of complex financial products together with the frequent observation of deviations from the assumed financial models has recently boosted research in the area of quantitative risk management. In such an environment, banks, big financial institutions, investors and regulators cannot carry out decision making using only intuitive methods, but they increasingly depend on formally defined procedures that order financial positions according to their risk. Such procedures are mathematically described by risk measures, which are mappings of financial positions to numbers expressing their risk. In the core of these procedures, stochastic models for the financial positions summarize all the information gathered regarding the evolution of the market. However, the construction and validation of these models is an onerous task and the observation of extreme events and samples in the operation of the markets questions the confidence that the market participants can have in them. We are interested in estimating such models involving both continuous and discrete factors, as well as in optimizing portfolio decisions according to several risk measures. Our algorithms employ techniques from convex optimization, mixed integer optimization and robust optimization.

Application Procedure

In order to apply for a Bachelor Thesis, a Semester Paper, or a Master Thesis, please write an e-mail to the study advisers with the following information:

• your name;
• your programme;
• your current state of studies (number of semester);
• course units that you have attended at the Institute for Operations Research;
• type of project of you would like to do;
• your favourite project topics from the above list;
• a short motivation letter why you would like to carry out a project in optimization.