Applying some metaheuristic, improve the quality of the solutions returned by the construction heuristic you devised in Assignment 1.
Compare the results against:
Use for your experimental comparison the problem instances available from the course web page:
queen11_11 queen12_12 queen13_13 queen14_14 queen15_15 queen16_16 DSJC1000.1, DSJC1000.5, DSJC1000.9, DSJC500.1, DSJC500.5, DSJC500.9
Limit the total computation time to 1 minute (on IMADA terminal room machines).
For the analysis of results use the methods saw in class, that is, graphical visualisation and appropriate data aggregation.
Iterate the process until you are able to show significant improvements. If you lack of inspiration, recall the property mentioned at the lecture: For any graph, there is a permutation of vertices from which the greedy assignment of colors (i.e., always assign the smallest feasible color) will produce a coloring with chromatic number of colors. Playing with these permutations one can design a large number of heuristics and metaheuristics for GCP.
Submit as in the previous Assignment your full working directory with
the best results in res\.
If you finish early, start working on the next assignment: design and
implement local search algorithms for graph coloring.