For the Fall 2020 offering of CS 170, we were tasked with solving and approximation solutions to an NP-complete problem. You can view the project spec here as well as in project_spec.pdf. We chose to formulate this problem as an integer linear program.
If you are using Gurobi, you will need to acquire an academic license.
parse.py: functions to read/write inputs and outputssolver.py: code to solve inputs using CDCsolverg.py: code to solve inputs using Gurobi (significantly faster runtime)utils.py: contains functions to compute cost and validate NetworkX graphs
- create a folder in the file tree where you want outputs to go
- change line 157 in
solverg.pyto the name of the created folder python3 solverg.py foldernamewill run the solver on a folder of inputs
We placed in the top 10% in our class of over 600 students. Our final team rank was 21/243. You can view the leaderboard here and our team's scores here.