Skip to content

f4t4nt/cs170-project

Folders and files

NameName
Last commit message
Last commit date

Latest commit

256ad4a · Dec 5, 2022
Nov 17, 2022
Nov 17, 2022
Dec 5, 2022
Dec 5, 2022
Dec 5, 2022
Dec 1, 2022
Dec 5, 2022
Nov 30, 2022
Dec 4, 2022
Nov 10, 2022
Dec 5, 2022
Dec 5, 2022
Dec 5, 2022
Dec 5, 2022
Dec 5, 2022

Repository files navigation

Fall 2022 CS170 Project, 1st Place Team

Screenshot 2022-12-05 095045

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.