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

Metaheuristics for Graph Coloring

The task of this last obligatory assignment is to implement an effective stochastic local search heuristic or a local search based metaheuristic for the optimization version of the graph coloring problem.

This time your program will be re-run in class during one of the exercise sessions using one of the IMADA machines. It is therefore chiefly important that you follow the submission requirements described below.

The program will be tested in solving uniform random graphs of size 500 and edge density 0.5. A set of 10 instances of this type has been made available at the course web page. Those are the training instances. The instances on which your program will be tested in class will be different although their characteristics will resemble those of the training instances.

The time limit will be set to 30 seconds.

You may implement different metaheuristics and/or different settings for their parameters, but you must submit only the instantiation that you deem the best (i.e., the value of metaheuristic parameters, if any, must be defined in your code).

Submission requirements

• Submit your files in a tgz archive organized as mentioned in Assignment 1.
• This time it is the executable of your program that will be checked.
• Pre-compile the executable on IMADA machines or make sure that you have a makefile in your CPRN/ directory for compiling.
• Your program must run by typing in the directory CPRN/:

      gcp -i INSTANCE -t TIME -s SEED
  

  and return on the standard output a single number representing the number of colors for which a feasible coloring has been found during the execution of the program.

  If you are writing your program in Java you may need to include a bash wrapper called gcp

  #!/bin/bash
  java -jar your_java_program.jar $@
  

  to ensure that nothing is needed in the command line before the call to the executable. Also, you may need the java command line parser commons.apache.org/cli.

• It is important that your program halts sharp on the time passed through the flag -t. If you are unable to achieve this in Java you may use the following bash wrapper gcp that externally stops your application and retrieves the result from the certificate solution printed in a file. In this case you must ensure that your java program writes in the file passed with option -o a solution in the format required by the verifier used in the previous assignments every time a new best solution is found (you may however restrict to only proper coloring since improper coloring are useless).

  [download]

  #!/bin/bash HARDTIMELIMIT=30 HARDMEMLIMIT=2000000 INSTANCE="" while getopts "i:t:s:" OPTION; do case $OPTION in i) INSTANCE="$OPTARG";; \?) echo "usage: -i INSTANCE -t TIME -s SEED"; exit;; esac done if [[ -z $INSTANCE ]] then echo "instance parameter missing" exit 1 fi TEMPFILE=temp.$$ TMPDIR=/tmp/$USER rm -f $TMPDIR/$TEMPFILE* &> /dev/null mkdir -p $TMPDIR exec 2> $TMPDIR/$TEMPFILE.stderr bash -c " ulimit -t $HARDTIMELIMIT s; ulimit -f $HARDMEMLIMIT; \ java -jar your_java_program.jar $@ -o $TMPDIR/$TEMPFILE.sol " 1> $TMPDIR/$TEMPFILE.stdout bash -c " test_sol -i $INSTANCE -s $TMPDIR/$TEMPFILE.sol -p 1 | awk -F\" \" '/uses/{print \$7}'" RET=$? echo "OK" >& 2 mv $TMPDIR/* ./ rmdir -p $TMPDIR &> /dev/null exit $RET EOF