Exploration of a solution to the Assignment Problem (Graph Theory)
https://en.wikipedia.org/wiki/Assignment_problem
This is a variation of the classic Graph Coloring Problem. In this variation:
Let C be a finite set of colors, C = { 0, 1, .. , k }
We begin with an empty graph, G. Then, we repeat the following N times:
- After a random period of time, a node is added to the graph adjacent to each other node in the graph.
- Nodes added to the graph must be assigned a color as they are added.
- A weight is assigned to the edge between each node in the (complete) graph, according to the colors of the incident nodes.
w(u,v) = f(c(u), c(v)) - Each node will be removed from the graph after some time TTL (time-to-live)
The goal is to choose colors to assign the nodes such that the sum of edge weights in the graph across time is minimised.
The goal is to train a variety of machine learning models to choose color asisgnments, and compare their performance.
git clone https://github.com/khornlund/aspr.git
cd aspr
python setup.py develop
- Generate a set of spawn-times (times for nodes to be added to the graph):
aspr_spt --help
Usage: aspr_spt [OPTIONS]
- Options:
-i, --identifier TEXT Name of new spawntime set [required] -n, --n-nodes INTEGER Number of nodes to spawn -t, --time-window INTEGER Time window over which nodes will spawn. -s, --seed INTEGER Random seed to use --help Show this message and exit.
- Perform some simulation runs. Try 'greedy' or 'random' to start.
aspr_run --help
Usage: aspr_run [OPTIONS]
- Options:
-s, --spawn-times TEXT Folder containing spawn times. Generate this using aspr_spt. [required] -c, --n-colors INTEGER Number of node colors available. -r, --n-runs INTEGER Number of runs to perform. -dm, --decision-model TEXT greedy, random, rrobin, linreg -da, --decision-model-args TEXT Additional arguments for decision model. -im, --interference-model TEXT binary -ia, --interference-model-args TEXT Additional arguments for interference model. -b, --base-seed INTEGER Random seed to use -v, --verbose Log level. Options: -v -vv --help Show this message and exit.
- Train some machine-learning models based on the results of others!
aspr_train --help
Usage: aspr_train [OPTIONS]
- Options:
-m, --model-name TEXT Model to train [required] -f, --folder TEXT Folder to use for training [required] -c, --n-colors INTEGER Number of colors in scenario [required] -v, --verbose Log level. Options: -v -vv --help Show this message and exit.
- Generate 20 random spawn times in a 50s window. Output will be in
/outputs/test01
aspr_spt -i test01 -n 20 -t 50
- Run 5000 simulations with a Random decision model. 5 colors available.
aspr_run -s test01 -c 5 -r 5000 -dm random -v
- Train a Linear Regressor model using the data generated by the Random decision model.
aspr_train -m linreg -f outputs\\test01\\nc5\\data\\random-binary -c 5 -v
- Test the Linear Regressor on the same spawn times (note the -da argument to say which trained model to use):
aspr_run -s test01 -c 5 -dm linreg -da test01 -v
- Generate some new spawn times, and test the Linear Regressor on those:
aspr_spt -i test02 -n 20 -t 50 --seed 42
aspr_run -s test02 -c 5 -dm linreg -da test01 -v
Tests can be run using python setup.py test