- Python: We used version 3.6.2, but any version of python3 <= 3.7 should work for Gurobi purposes. Please visit https://www.python.org/downloads/ if you do not currently have python installed in your machine.
- Python package manager: We used pip3, but any python package manager should do the trick. With help installing pip3, please consult https://pip.pypa.io/en/stable/
- Networkx (https://networkx.github.io/)
- Gurobi Optimizer
Our solution uses Gurobi Optimizer 9.0 under an academic license to formulate and solve ILPs for each graph. For the following steps, please ensure that you are connected to an academic network.
- Register for a free Gurobi academic license at https://www.gurobi.com/downloads/end-user-license-agreement-academic/
- Download Gurobi optimizer from https://www.gurobi.com/downloads/
- Once installed, run ‘grbgetkey’ using the argument provided (ex: grbgetkey ae36ac20-16e6-acd2-f242-4da6e765fa0a) to store the license on your local machine
- Navigate into the gurobi installation path
- For mac, this defaults to /Library/gurobi_server811/mac64
- For windows, this defaults to c:/gurobi_server811/win64
- Run
python3 setup.pyto add gurobi to your python libraries
If you are facing any other problems, please refer to https://www.gurobi.com/documentation/8.1/remoteservices/installation.html
To install networkx, simply run the following command:
pip3 install networkx
- Navigate to the location of this project
- Run python3 solver.py --all ./inputs ./outputs/
- solve(): Computes the cost of a path using both backtracking and ilp, and returns the minimum of both.
- solve_backtracking(): Creates a path using a reverse all-pairs shortest path from homes to the start index.
- solve_ilp(): Creates a path using an integer linear programming formulation.
- printCircuit(): Conducts Hierholzer's algorithm for directed graphs to find a eulerian circuit given edges in the graph and a start vertex. Code from https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/