47-779 / 47-785 course syllabus - Fall 2021

The final group project accounts for 50% of the total grade. This project should reflect the understanding of the material covered in the course.

The components of this project are the following:

- Identify a problem that can be posed as an Integer Program. Discuss the importance of this problem.
- Solve instances of the identified problem using classical tools. Identify which are the sources of complexity while solving this problem.
- Model the problem as a Quadratic Unconstrained Binary Optimization (QUBO). Verify that the reformulation of the problem is valid, in the sense that it represents the original problem.
- Solve the resulting QUBO using non-conventional methods, e.g. Quantum Annealing, QAOA, simulated annealing in GPUs/TPUs, etc. Compare at least two different methods.
- Implement the Graver Augmented Multiseed Algorithm (GAMA) to solve your problem. Evaluate the validity of your formulation for this algorithm and apply other decomposition algorithms if possible.
- Write a report outlining the different approaches used and highlighting the knowledge obtained while developing the project.
- Make a final presentation to the class reporting the findings of the project.