KCTLIB -- Software

As mentioned in the introduction pages, there have been heuristic as well as metaheuristic approaches proposed in the literature. The available software packages are listed below.

Software packages:

Software for the ACO, the EC, and the TS approach propsed by Blum and Blesa [1]
Basic data structures by Blum and Blesa [1]

Software for the ACO, the EC, and the TS approach propsed by Blum and Blesa

Blum and Blesa provide the software for their Ant Colony Optimization (ACO), their Evolutionary Compution (EC), and their Tabu Sarch (TS) approach. The software package is developed in C++ under Redhat 7.1 Linux and compilable with the GNU C++ compiler (no guarantees that it also works under Windows). To uncompress the package:

tar xvzf blum_blesa_algorithms.tgz

To compile the package:

make

After that, there should be four executables in the same directory: aco, ec, ts, and gg-ew-generator. The first three are the algorithms, whereas the last executable is a generator for random grid graph instances. All three algorithms have the same basic command line options:

-i: expects an input file (obligatory)
-t: expects a computation time (obligatory)
-cardb: a cardinality, or the beginning of a cardinality range (obligatory)
-carde: the end of a cardianlity range (optional)
-cardmod: makes the algorithm choose all the cardinalities between cardb and carde that are devidable by the number provided (optional; default = 1)
-n: the number of trials to be executed for every cardinality (optional; default = 1)

The grid graph generator provides the following command line options:

-rows number of rows of the grid graph (obligatory)
-cols number of columns of the grid graph (obligatory)
-max the maximum edge weight. Edge weights are chosen randomly from [1,max] (obligatory)
-o the name of the output file (obligatory)

For obtaining the software package as well as for questions and suggestions write to: cblum@ulb.ac.be

Basic data structures by Blum and Blesa

Blum and Blesa also provide in a seperate package the basic data structures that they used for all their algorithms. They invite other researchers to use these data structures for their algorithms in order to improve the comparability of approaches to tackle the KCT problem. This package consists of three C++ classes: UndirectedGraph, Edge and Vertex. A short description of every method can be found in the ".cpp" files.

Dowload: basic_data_structures.tgz

Bibliography

[ Home | Introduction | Problem instances | Software | Best known solutions]