The Contest aims at letting the student gaining practical experience on the methods learned in class. The analysis of the results of the Competition is meant to provide important topics of discussion in class.

This year the Contest is focused on the well known Graph Coloring Problem.

Students can take part in the Competition in groups of at most 3, although individual participation is to be preferred.

The Contest is divided in Tasks that will be posed in class and reported in the Weekly Notes. Every Task will come with a Deadline (ca. two weeks after the launch).

Handing in Electronically

The program implementation must be handed in within the given deadline. This is done by sending to the lecturer an email with enclosed an archive thus organized:

main directory:

CPRN-TaskN/

where CPRN is the student's CPR number
and TaskN is the task number (eg, 030907-1) and content:

CPRN-TaskN/README

CPRN-TaskN/src/

The file README reports the name of the student and the manual for the compilation of the program. The directory src contains the sources which may be in C, C++ or Java language. If needed a Makefile can be included either in the root directory or in src. After compilation the executable must be placed in src. For java programs, a jar package can also be submitted.

Programs must work on IMADA's computers under Linux enviorment and with the compilers and other applications present on IMADA's computers. Students are free to develop their program at home, but it is their own responsibility to transfer the program to IMADA's system and make the necessary adjustments such that it works at IMADA. (past issues: the java compiler path is /usr/local/bin/javac; in C, any routine that uses subroutines from the math.c library should be compiled with the -lm flag -- eg, cc floor.c -lm)

Program Options and Output

The executable must be called gcp. It will be run by typing in the directory CPRN-TaskN/src/:   

gcp -i INSTANCE -t TIME -s SEED -o OUTPUT [task specific options]


• -i INSTANCE to load the data associated with the file INSTANCE.
• -t TIME to stop the program execution after TIME seconds. The test machine could not be totally dedicated at the moment of execution.
• -s SEED to initialize the random generator.
• -o OUTPUT the file name where the solution is written

For example: gcp -i le450_15a.col -o le450_15a -t 300 -s 1 will run the program on the instance le450_15a.col opportunely retrieved from the given path for 300 seconds with random seed 1 and write the solution in the file le450_15a.sol.

After termination the program must print in the standard output two numbers in two separated lines. The first number is the lowest number of colors for which a feasible coloring was found and the second line is the exiting computation time.

The syntax of the solution in the output file is a column of numbers corresponding to the colors assigned to nodes. After each entry the character \n (new line) has to be printed. Colors start from 1 and the first color in the column represents the color assigned to node 1.

It is advisable to have a log of algorithm activities during the run. This can be achieved by printing on the standard error or in a file (which maybe determined with a option -o filename) further information. A suggested format is to output a line whenever a new best solution is found containing at least the following pieces of information:

best 853 col 10 time 0.000000 iter 0 par_iter 0

The correctness of a solution will be checked.

Instances

The graphs are in the DIMACS file format. Each line of the file begins with a letter that defines the rest of the line. The legal lines are

• c Comment: remainder of line ignored.
• p Problem: is of form
  p edges n m
  where n is the number of nodes (to be numbered 1..n) and m the number of edges.
• e Edge: is of the form
  e n1 n2 d
  where n1 and n2 are the endpoints of the edge. The optional d value is used to enforce a requirement and n1 and n2 have colors that differ by at least d (if there is no d value, it is assumed d=1).

Assessment

An evaluation of the programs will occur after each task. In each task there will be two sets of instances available:

Set A:

is made public with the task and will serve to test and configure the programs.

Set B:

is undisclosed and will be used for the assessment.

Resources

This C++ code contains methods for reading the instances, generating random numbers and checking computation time. Moreover it is developed in a framework which should allow the implementation of all the methods of the course. [gcp++-1.0.tgz] The framework is a very simplified version of EasyLocal++ (see literature section).

An updated version of the framework with procedures for local search is available [gcp++-1.1..tgz].
Also available is the code of the two construction heuristics DSATUR and RLF.

The script in R for producing the output for the analysis of results as presented at the lectures: analysis.Task2.R.

There are 2 instances available for the Task 1: [Instances-Task-1.tgz]. For both graphs the chromatic number is 15.

There are 3 instances available for the Task 2: [Instances-Task-2.tgz]. The chromatic numbers are 50, 60 and 76.

There are 6 instances available for the Task 3: [Instances-Task-3.tgz]. The chromatic numbers are 50 and 60.