Projects at DISOPT (Spring 2025):
- Submodular maximization subject to matroid and linear constraints
- In this project, we will investigate submodular maximization subject to matroid and linear constraints. Maximizing a monotone submodular function under a single general matroid constraint is NP-hard but can be approximated up to a (1-1/e)-approximation guarantee (https://epubs.siam.org/doi/10.1137/080733991). In this project, we will investigate whether the LP-rounding procedure can be extended to get better approximations for submodular maximization under several matroid and knapsack constraints. In particular, we will look into both LP-based and combinatorial methods for submodular maximization over various polytopes.
- Prerequisites: Student should have previous coursework in Discrete Optimization and in Algorithms. Student should have familiarity with LP and ILP algorithms.
- If you are interested, please contact: Neta Singer ([email protected]).
- Characterization of adjacency for the stable matching polytope
- In this project, we will study the adjacency of stable matching polytope. For perfect matching polytope, two perfect matchings are adjacent if and only if their symmetric difference is a circuit. We would like to give a similar characterization of adjacency in stable matching polytope. This will probably be related with the lattice structure of stable matchings, in which we can transform one stable matching into another by a special permutation called rotation. A follow-up of this question is to investigate other computational properties of stable matching polytope and stable matching lattice.
- Prerequisites: Student should have taken a bachelor-level Discrete Optimization course. A bachelor-level course on Algorithms and a master-level course on Discrete Optimization would be helpful but not required. Student should have some programming skills for doing numerical experiments.
- If you are interested, please contact: Jiaye Wei ([email protected]).
- Cutting planes: are large cuts necessary?
- Check the descriptions here.
- Prerequisites: Student should have taken a bachelor-level Discrete Optimization course and a master-level Integer Optimization course.
- If you are interested, please contact: Friedrich Eisenbrand ([email protected]).
Rules of the game
- Available projects are displayed on this webpage. Students interested in taking a project with DISOPT are invited to contact us. Projects are allotted first-come first-serve.
- Please note that for third year Bachelor students, a successful completion of the course Optimisation discrète is required (grade 4.5 or better) to do a project.
- Each project is supervised by an advisor within DISOPT. The student and the advisor meet within 3 days after the project assignation for the kick-off meeting, where the goals and first milestones are discussed on the basis of the project description.
- There is a seminar dedicated to project talks. Each student has to deliver two 30 min presentations. Each project student is expected to participate at the presentation of the other students. The quality of the presentation and, in particular, the improvement from first to second presentation, is a grading criterion.
- There are weekly meetings with the advisor. In these meetings the achievement of previously set goals is assesed and after discussion, new tasks are assigned for the following week and, if necessary, the milestones are updated.
- Typically, the identified tasks are reading and understanding an article from the literature or implementing algorithms or methods used for the project
- We expect the students to be on time and well prepared for these meetings. If two meetings are missed by the student without an excuse, or if the student is two times unprepared, the student will not pass the project.
- There is a mutual evaluation form to be filled out by the student and the advisor at midterm that serves as a base to improve the performance of the project.
- At the end of the semester the students will hand in their report and, after that, present their project and results in a 30-minutes final presentation.
- The final presentation shall be exposed in 10 slides, plus a single bonus slide listing the contribution of the student. The contribution might be of the following kinds: understanding and learning state-of-the art methods, modelling real-life scenarios, algorithm implementations, new proofs of existing results, or (restricted) new results.
Grading:
- DISOPT uses the full grading spectrum 1-6 to assess projects
Grading criteria:
- Ability to perform independent mathematical research: literature research (branching out), formulation of alternative and related goals
- Mastery of the mathematical theory around the project
- Usability and efficiency of the code and comparison by exhaustive tests with existing methods (applied projects)
- Achievement of theoretical goals (new theorems proved, old theorems proved in a creative alternative way)
- Quality of midterm and final project presentation and the report
Requirements:
High motivation, discrete optimization, linear algebra, programming skills