Benchmark problems for Minimum Weighted Dominating Set Problem

On this page test instances for the Minimum Dominating Set Problem can be downloaded. The problems have been used in the article:

1. Ant Colony Optimization Applied to Minimum Weight Dominating Set Problem, Raka Jovanovic, Milan Tuba, Dana Simian, New Aspects of Automatic,  Proceedings of the 12th WSEAS International Conference Control, Modeling and Simulation on Automatic Control, Modelling & Simulation, Catania, Italy, May 29-31, pp. 322-326(2010)

In the case of using these test problems I request that you cite this article.

Problem instance description

We have generated two types of random problem instances for our tests. In the first one weights for nodes where randomly selected for vertexes from the interval [20, 70]. In the second group the weights where dependent of the number of connections vertex v had and it would be randomly selected from the [1, e(v)^2]. e gives the number of connections for v. We used graphs from 50 to 1000 nodes with different number of randomly created edges but always making the graph connected. For each problem size and density we have created 10 instances with random seeds having the values from 0-9. The values of solutions for this problem can be found in the mentioned article.

File Structure

The test problem instances can be downloaded here.

The problems are stored in a ProblemInstances.zip. The file has the following directory structure:

\problemtype\V{NumberOfvertexes}E{NumberOfEdges}\{ProblemInstanceIndex}\Test\

For an example:

Problem of Type 1, with 1000 vertexes with 1000 edges, and with random seed 0 would be stored in the following directory:

\T1\ V 1000E1000\0\Test

___________________________________________________________________In this folder (\T1\ V 1000E1000\0\Test) we have the following files:

Problem.dat stores the graph structure:

First line “NumberOfNodes”, second line <NumberOfNodes>. Then a line “Positions”. Next NumberOfNodes lines hold positions for vertexes given with two coordinates “A <space>B”. This information is not necessary for calculating the dominant set but is stored anyways. After this one line with “******************WEIGHTS*****************************”. Next NumberOfNodes lines weight for vertexes. Next a line with “*****************CONNECTIONS****************”. Connections are given one line for each vertex. 1 at position i means that vertex is connected with vertex “i”. Every vertex is considered to be connected with its self.

Rezultati.txt gives info about calculation using our ACO implementation :

There is some extra text in this file which should be disregarded, the only important line is : nocorrection Best: 10682 Index:0 Iteration:9050. Which gives information on the solution found using ACO, and the iteration on which it has been found.

Test0.text gives the intermediate solutions found using ACO. Each line has first the iteration number and value of the solution found at that iteration. Often there are two lines that have zero. This is due to the fact that we write the initial solution found using the greedy algorithm, and in some cases ACO finds a better solution at the first step.

In the folder T1 or T2 the average results for each of test instances are stored in the following way:

For each problem size 3 files exist (we give names for the V 1000E1000 problem):

testV1000E1000Edge.txt : gives grouped results for appropriate problem size when greedy1 algorithm from mentioned article was used

testV1000E1000Sum.txt : gives grouped results for appropriate problem size when greedy2 algorithm from mentioned article was used

testV1000E1000ACO.txt: gives grouped results for appropriate problem size when ACO implementation from mentioned article was used

All the average results are grouped in the following files using the same naming system.

T1\testAverageACO.txt, T1\testAverageEDGE.txt, T1\testAverageSUM.txt

The results are ordered first by vertex and then by edge number. There is a small mistake the 800 vertex problems are put last, or in other word the last two vertex sizes (1000, 800) have changed places.