DM811 - Heuristics for Combinatorial Optimization
Assignment Sheet 3, Autumn 2011 [pdf format]

1  Local Search for Graph Coloring

This task asks you to design and implement a local search algorithm for the optimization version of the graph coloring problem. Your aim should be finding the best approximation of the chromatic number.

1. The following are possible alternatives to consider in the design of a local search for GCP. They lead to the definition of the solution representation (and hence to the candidate solutions), the neighborhood structure and the evaluation function.

   ---

   k in	assignment	type of
   local search	of colors to V	coloring
   k-fixed	complete	proper
   k-fixed	partial	proper
   k-fixed	complete	unproper
   k-fixed	partial	unproper
   k-variable	complete	proper
   k-variable	partial	proper
   k-variable	complete	unproper
   k-variable	partial	unproper

   ---

   Determine which combination read in the rows of this table leads to a promising local search approach and implement it.

2. Describe your local search providing a definition of the seven components and an algorithmic sketch (pseudo-code). Put your response in .pdf format in the directory doc/ of your archive. For the sketch, you may consider using the LaTex style algorithm2e.sty. (Just google with the file name.)
3. Collect computational results on the following instances published in Assignment 2:

   queen11_11, queen12_12, queen13_13, queen14_14, queen15_15, queen16_16,
   DSJC1000.1, DSJC1000.5, DSJC1000.9, DSJC500.1, DSJC500.5, DSJC500.9 
   

   Run your algorithm 10 tens on each instance and report the results in a file called results.txt in res/ using the following format:

   CPRN instance_name solution seconds