This repo contains our team's (discordggTYsy64VcWT) work for the Fall 2022 CS170 Project. We placed 1st out of 260 teams. The project is an NP-Hard optimization problem that involves finding an optimal partition of a graph based on an objective function seeking to minimize the number of groups, equalize the distribution of nodes across groups, and minimize the sum of intra-group edge weights. The full project spec can be found in project.pdf
.
We primarily used a simulated annealing approach framed inside a genetic algorithm heuristic to compute our results. The relevant code is in main.cpp
and header.cpp
. In addition, to focus our compute power on the most pressing inputs where we were lowest ranked on, we run a BeautifulSoup script in python/scraper.ipynb
that writes relevant information about each input into queue.txt
, sorted so the lowest ranking inputs with the largest delta scores (best score - local best score) appear first. Our other minor algorithms and attempts can be found in extras.cpp
, /python/jax_pop_sim.py
, /python/knapsack.py
, and /python/main.ipynb
. Our complete set of inputs and outputs can be found in /tests
, which is intuitively organized. Our inputs for phase 1 can be found in /phase_1
. Our final submission file for phase 2 is submission.tar
, which contains our best outputs which were compiled to /phase_2
.
To see our program in action, you can run /python/scraper.ipynb
to populate queue.txt
. Then run main.cpp
and optimal results will be written to the respective folder in /tests
(the file name is the score rounded to the nearest integer as well as a tag used for identification purposes, if you run into issues compiling, you can manually set comp_name
on lines 477 and 520 and comment out the preceding related lines of code). To see all the best solutions in one place, run submit.py
to copy all results to /phase_2
and tar them into submission.tar
. Optionally, once you have good results for all inputs, you can call final_solve()
instead of basic_solve()
in main.cpp
on line 655 to drastically improve existing results. Note that an x64 environment with 1GB of RAM is recommended to run this program (initializing all 1024 agents takes quite a bit of memory, once the program is running, only 60MB is required). Moreover, remember to use the -O2
or -O3
flags to compile main.cpp
for optimal performance. You can download a lightweight ZIP file minus all .out
files here.