Project

In the project, you will work together in teams of 2 on a board game inspired problem. The possible settings can be found here. Each team will be given a different setting based on preferences they submit (details to follow). Your tasks are:

1. Formally define your problem and possibly variants (including parameterizations) of it and write an ILP model for it. See here for details.
2. Develop an initial algorithm based on Branch-and-Bound. It should be a correct and sensible algorithm, but formal guarantees on running time, etc. are not required. See here for details.
3. Deeper investigation of problem into a direction of your choice. See here for details.

Remarks:

• some of the problems are more complicated than others. You are free to make simplifying assumptions, for example, removing some constraints from the problem.
• start with the easiest, not the most complicated techniques from the course. Similarly, start by simplifying the problem as much as you can, to obtain initial ideas that might transfer to more general variants.
• Goals: nice ideas, efficiency, generality of the algorithm (priority in this order)
• These are difficult projects. I do not know the outcome of them. It is expected that you run into obstacles or get stuck at some point. Do not give up easily!

Links

• Project settings
• Task 1
• Task 2
• Task 3