Tabu Search method applied to Graph Coloring

Discussion:

(too old to reply)

David Bernier

2017-06-14 04:39:46 UTC

Tabu Search is a method that can be applied to find
good graph colorings efficiently.

My reference for Tabu Search applied to graph coloring is:
Porumbel, Hao and Kuntz,
"Informed Reactive Tabu Search for Graph Coloring",
on the Web at:

cedric.cnam.fr/~porumbed/papers/irts.pdf

I implemented in the C programming language the Tabu Search algorithm
from Section 2 with the parameters suggested in
5.1.2, so alpha = 0.6 and A = 10.

There are various collections of graphs for
bench-marking graph coloring algorithms.

I used the graph referred to as DSJC125.5.col
with 125 vertices and 3891 edges as shown here:

< http://mat.gsia.cmu.edu/COLOR04/INSTANCES/DSJC125.5.col > .

I adopted Michael Trick's representation , without comments:

The file DSJC125.5.mt looks like this:

125 3891
2 1
3 1
4 1
4 2
4 3
5 1
5 2
5 3
6 1
[ 3881 following lines skipped ]
125 122

------------------------------- test ---------------------------------

$ time ./test45a.out DSJC125.5.mt 17
num_colors = 17 // coloring with at most 17 colors wanted
num_vertex = 125
num_edges = 3891
sum_adj_mat = 7782

First select a random 17 coloring of the 125 vertices...
9 conflicts at 462 iterations
8 conflicts at 471 iterations
7 conflicts at 566 iterations
6 conflicts at 1745 iterations
5 conflicts at 2149 iterations
4 conflicts at 21839 iterations
3 conflicts at 23540 iterations
2 conflicts at 25051 iterations
1 conflicts at 30212 iterations
0 conflicts at 2854777 iterations // after 2.8 million iterations,
// all conditions are satisfied.

real 2m13.898s // time elapsed

---------------------- solution check ------------------------------

$ ./check55a.out DSJC125.5.mt 17
num_colors = 17
num_vertex = 125
num_edges = 3891
sum_adj_mat = 7782

First select a random 17 coloring of the 125 vertices... // input =
Solution...
0 conflicts at 1 iterations

--------------------------------------------------------------------
Solution in file solution17:

1 12
2 15
3 3
4 9
5 8
6 7
7 10
8 14
9 9
10 11
11 2
12 16
13 1
14 8
15 9
16 15
17 4
18 8
19 6
20 9
21 2
22 14
23 10
24 7
25 6
26 3
27 14
28 9
29 13
30 5
31 7
32 7
33 5
34 1
35 12
36 6
37 1
38 16
39 2
40 7
41 10
42 11
43 13
44 5
45 4
46 14
47 16
48 9
49 4
50 17
51 13
52 8
53 9
54 11
55 5
56 3
57 7
58 16
59 5
60 4
61 1
62 17
63 8
64 17
65 12
66 1
67 14
68 17
69 8
70 17
71 13
72 3
73 3
74 12
75 12
76 6
77 15
78 6
79 1
80 9
81 14
82 8
83 16
84 2
85 10
86 4
87 13
88 4
89 12
90 12
91 6
92 15
93 14
94 2
95 17
96 2
97 7
98 3
99 16
100 11
101 1
102 3
103 17
104 10
105 13
106 15
107 15
108 10
109 6
110 16
111 13
112 11
113 4
114 10
115 2
116 5
117 10
118 12
119 14
120 5
121 4
122 7
123 13
124 1
125 2
------------------------------------------------------------------------------------
Source code in test45a.c :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_VERTEX 1000
#define MAX_COLORS 200

int adj_mat[MAX_VERTEX][MAX_VERTEX];

int Gamma[MAX_VERTEX][MAX_COLORS];

int Fast_Gamma[MAX_VERTEX][MAX_COLORS];

int tabu_list[MAX_VERTEX][MAX_COLORS];

static unsigned long long Q[2097152], carry=0;

unsigned long long B64MWC(void)
{ unsigned long long t,x; static int jm=2097151;
jm=(jm+1)&2097151;
x=Q[jm]; t=(x<<28)+carry;
carry=(x>>36)-(t<x);
return (Q[jm]=t-x);
}

#define CNG ( cng=6906969069ULL*cng+13579 )
#define XS ( xs^=(xs<<13), xs^=(xs>>17), xs^=(xs<<43) )
#define KISS ( B64MWC()+CNG+XS )

int main(int argc, char *argv[] )
{
FILE *in;
unsigned long long im,cng=123456789987654321ULL,
xs=362436069362436069ULL;
unsigned long long mask = 2147483647ULL;
int num_colors;
int num_vertex;
int num_edges;
int num_conflicts;
int k;
int i;
int j;
int sum_adj_mat;
int ru;
int b;
int color;
int init_coloring[MAX_VERTEX];
int conflict_count;
int sum_Gamma;
int best_delta;
int delta;
int best_vertex;
int best_color;
int iter_counter;
int A;
float alpha;
int tl;
int b_tabu_rnd;
int tabu_rand;
int color_tabu;
int min_conflicts;
int job_done;
int differences;
FILE *out;

alpha = 0.6;
A = 10;
job_done = 0;

num_colors = atoi(argv[2]);
printf("num_colors = %d\n" , num_colors);

in = fopen(argv[1], "r");

fscanf(in, "%d %d", &num_vertex, &num_edges);

printf("num_vertex = %d\n", num_vertex);
printf("num_edges = %d\n", num_edges);

for(i = 0 ; i < MAX_VERTEX; i++)
{
for(j = 0 ; j < MAX_VERTEX; j++)
{
adj_mat[i][j] = 0;
}
}

for(k = 0; k < num_edges; k++)
{
fscanf(in, "%d %d", &j, &i);
if( i != j )
{
adj_mat[i-1][j-1] = 1;
adj_mat[j-1][i-1] = 1;
}

if(i == j)
{
printf("warning: edge %d is = %d %d\n", k+1, i, j);
}
}

fclose(in);

sum_adj_mat = 0;

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_vertex; j++)
{
if( (adj_mat[i][j] == 1) && (i!=j) )
{
sum_adj_mat++;
}
}
}

printf("sum_adj_mat = %d\n", sum_adj_mat);

printf("\n");

while( job_done == 0)
{

for(i = 0 ; i < num_vertex; i++)
{
for(j = 0 ; j < num_colors; j++)
{
tabu_list[i][j] = 0;
}
}

min_conflicts = 1000000;

b_tabu_rnd = ((int) mask)/A;
b_tabu_rnd = b_tabu_rnd + 1;

printf("\n");

printf("First select a random %d coloring of the %d vertices...\n",
num_colors, num_vertex);

b = ((int) mask)/num_colors;
b = b+1;

for(i = 0; i< num_vertex; i++)
{
ru = (int) (KISS&mask);
color = ru/b;
init_coloring[i] = color;
}

for(iter_counter = 1; iter_counter < 10000000; iter_counter++)
{

if( iter_counter == 1)
{
for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
conflict_count = 0;

for(k = 0; k< num_vertex; k++)
{
if( (i != k) && (adj_mat[i][k] == 1) && ( j == init_coloring[k]) )
{
conflict_count++;
}
}

Gamma[i][j] = conflict_count;
Fast_Gamma[i][j] = Gamma[i][j];
}
}
}

num_conflicts = 0;

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < i; j++)
{
if( (adj_mat[i][j] == 1) && ( init_coloring[i]== init_coloring[j]) )
{
num_conflicts++;
}
}
}

if( (num_conflicts < min_conflicts) && (num_conflicts < 10) )
{
min_conflicts = num_conflicts;
printf("%d conflicts at %d iterations\n", num_conflicts, iter_counter);
if(num_conflicts == 0)
{
job_done = 1;
break;
}
}

best_delta = 1000000;

tl = (int) (floor( alpha*((float) num_conflicts) + 0.5));
ru = (int) (KISS&mask);
tabu_rand = ru/b_tabu_rnd;
tabu_rand++;
tl = tl + tabu_rand;

for(i = 0; i < num_vertex; i++)
{
for(j = 0; j < num_colors; j++)
{
if(j != init_coloring[i])
{
delta = Fast_Gamma[i][j] - Fast_Gamma[i][init_coloring[i]];

if( delta < best_delta )
{
if( (tabu_list[i][j] < iter_counter) || ((tabu_list[i][j]

= iter_counter)&&(0 == delta + num_conflicts)))

{
best_vertex = i;
best_color = j;
best_delta = delta;
}
}
}
}
}

color_tabu = init_coloring[best_vertex];

tabu_list[best_vertex][color_tabu] = tl + iter_counter;

init_coloring[best_vertex] = best_color;

for(i = 0; i < num_vertex; i++)
{
if( adj_mat[i][best_vertex] == 1)
{
Fast_Gamma[i][color_tabu] = Fast_Gamma[i][color_tabu]-1;
Fast_Gamma[i][best_color] = Fast_Gamma[i][best_color]+1;
}
}

}

}

out = fopen("solution17", "w");

for(i = 0; i < num_vertex; i++ )
{
fprintf(out, "%d %d\n", i+1, init_coloring[i]+1);
}

fclose(out);

return 0;

}

---------------------------------------------------------------------

David Bernier

David Bernier

2017-06-16 05:15:57 UTC

Permalink

Post by David Bernier
Tabu Search is a method that can be applied to find
good graph colorings efficiently.
Porumbel, Hao and Kuntz,
"Informed Reactive Tabu Search for Graph Coloring",
cedric.cnam.fr/~porumbed/papers/irts.pdf
I implemented in the C programming language the Tabu Search algorithm
from Section 2 with the parameters suggested in
5.1.2, so alpha = 0.6 and A = 10.
There are various collections of graphs for
bench-marking graph coloring algorithms.
I used the graph referred to as DSJC125.5.col
< http://mat.gsia.cmu.edu/COLOR04/INSTANCES/DSJC125.5.col > .
125 3891
2 1
3 1
4 1
4 2
4 3
5 1
5 2
5 3
6 1
[ 3881 following lines skipped ]
125 122
------------------------------- test ---------------------------------
$ time ./test45a.out DSJC125.5.mt 17
num_colors = 17 // coloring with at most 17 colors wanted
num_vertex = 125
num_edges = 3891
sum_adj_mat = 7782
First select a random 17 coloring of the 125 vertices...
9 conflicts at 462 iterations
8 conflicts at 471 iterations
7 conflicts at 566 iterations
6 conflicts at 1745 iterations
5 conflicts at 2149 iterations
4 conflicts at 21839 iterations
3 conflicts at 23540 iterations
2 conflicts at 25051 iterations
1 conflicts at 30212 iterations
0 conflicts at 2854777 iterations // after 2.8 million iterations,
// all conditions are satisfied.
real 2m13.898s // time elapsed
---------------------- solution check ------------------------------
$ ./check55a.out DSJC125.5.mt 17
num_colors = 17
num_vertex = 125
num_edges = 3891
sum_adj_mat = 7782
First select a random 17 coloring of the 125 vertices... // input =
Solution...
0 conflicts at 1 iterations
--------------------------------------------------------------------
1 12
2 15
3 3
4 9
5 8
6 7
7 10
8 14
9 9
10 11

[...]

I tried to implement a Tabu search algorithm of Galinier and JK Hao,
from their 1999 paper:

"Hybrid Evolutionary Algorithms for Graph Coloring".

<
https://pdfs.semanticscholar.org/99fd/34c3b9172d9aa5f301fb8fe4fa54b80fc2b1.pdf

Post by David Bernier
.

In Table 4 on page 389, they give the average number of iterations
needed to solve, for example, a k-coloring of a standard reference
random graph on 500 vertices known as graph: DSJC500.5 (sometimes
DSJC500.5.col ) for k = 50, 51, 52 colors (the larger k is, the easier
it is to solve).

For 52 colors, they need 43,000 iterations on average to solve it with
Tabu search.
For 51 colors, they need 160,000 iterations on average.
For 50 colors, they need 1,495,000 iterations on average.

They also give results of the same kind for their superior performing
algorithm HCA (Hybrid Coloring Algorithm, which is an evolutionary
algorithm with a population of fittest colorings and rules for
"genetic combination").

For DSJC500.5 , the best coloring as of 2012 was 47 colors ( Olawale
Titiloye and Alan Crispin, using simulated quantum annealing ...)

ref..:
"Parameter Tuning Patterns for Random Graph Coloring with Quantum
Annealing" ,
link:
<
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0050060 > .

===

Even after several hours work, I couldn't duplicate Galinier and Hao's
iterations count for Tabu search on the 500-vertex graph, with 52 colors...

Anyway, I have a "home-brew" Tabu search program working on the
random 500-vertex graph, using many more iterations, but I think it
gives correct colorings :

[***@localhost TABU_E_homebrew]$ time ./newtabub99a.out DSJC500.5.mt 56
num_colors = 56
num_vertex = 500
num_edges = 62624
sum_adj_mat = 125248

First select a random 56 coloring of the 500 vertices...
9 conflicts at 1182 iterations
8 conflicts at 1265 iterations
7 conflicts at 1945 iterations
6 conflicts at 1961 iterations
5 conflicts at 2830 iterations
4 conflicts at 6028 iterations
3 conflicts at 7820 iterations
2 conflicts at 8917 iterations
1 conflicts at 25856 iterations
0 conflicts at 27855 iterations *********************** 56 done !

First select a random 55 coloring of the 500 vertices...
9 conflicts at 23 iterations
8 conflicts at 69 iterations
7 conflicts at 174 iterations
6 conflicts at 176 iterations
5 conflicts at 191 iterations
4 conflicts at 311 iterations
3 conflicts at 1014 iterations
2 conflicts at 25199 iterations
1 conflicts at 25758 iterations
0 conflicts at 29483 iterations ********************** 55 done !

First select a random 54 coloring of the 500 vertices...
9 conflicts at 136 iterations
8 conflicts at 222 iterations
7 conflicts at 346 iterations
6 conflicts at 987 iterations
5 conflicts at 1805 iterations
4 conflicts at 4411 iterations
3 conflicts at 6220 iterations
2 conflicts at 14534 iterations
1 conflicts at 76492 iterations

First select a random 54 coloring of the 500 vertices...
9 conflicts at 105 iterations
8 conflicts at 1964 iterations
7 conflicts at 2633 iterations
6 conflicts at 3267 iterations
5 conflicts at 4188 iterations
4 conflicts at 4516 iterations
3 conflicts at 7723 iterations
2 conflicts at 9802 iterations
1 conflicts at 89563 iterations
0 conflicts at 377553 iterations ***************** 54 done !

First select a random 53 coloring of the 500 vertices...
9 conflicts at 249 iterations
8 conflicts at 497 iterations
7 conflicts at 531 iterations
6 conflicts at 567 iterations
5 conflicts at 3314 iterations
4 conflicts at 206785 iterations
3 conflicts at 235843 iterations
2 conflicts at 396294 iterations
1 conflicts at 567372 iterations
0 conflicts at 677284 iterations ********************* 53 done !

First select a random 52 coloring of the 500 vertices...
9 conflicts at 3391 iterations
8 conflicts at 30975 iterations
7 conflicts at 31780 iterations
6 conflicts at 47393 iterations
5 conflicts at 47558 iterations
4 conflicts at 47816 iterations
[snip, as unfinished for 52]

David Bernier

David Bernier

2017-06-17 14:54:03 UTC

Permalink

On 06/16/2017 01:15 AM, David Bernier wrote:

[...]

Post by David Bernier
I tried to implement a Tabu search algorithm of Galinier and JK Hao,
"Hybrid Evolutionary Algorithms for Graph Coloring".
<
https://pdfs.semanticscholar.org/99fd/34c3b9172d9aa5f301fb8fe4fa54b80fc2b1.pdf

===
Even after several hours work, I couldn't duplicate Galinier and Hao's
iterations count for Tabu search on the 500-vertex graph, with 52 colors...
Anyway, I have a "home-brew" Tabu search program working on the
random 500-vertex graph, using many more iterations, but I think it
num_colors = 56
num_vertex = 500
num_edges = 62624
sum_adj_mat = 125248
First select a random 56 coloring of the 500 vertices...
9 conflicts at 1182 iterations
8 conflicts at 1265 iterations
7 conflicts at 1945 iterations
6 conflicts at 1961 iterations
5 conflicts at 2830 iterations
4 conflicts at 6028 iterations
3 conflicts at 7820 iterations
2 conflicts at 8917 iterations
1 conflicts at 25856 iterations
0 conflicts at 27855 iterations *********************** 56 done !

[snip]

I may have a 50-coloring for the DSJC500.5.col 500-vertex, 62624-edge
random graph... But it took tens of millions of iterations in
a program based on tabu search....

According to Titiloye and Crispin, authors of the article on graph
coloring using QA (quantum annealing) (please see above),
a 48-coloring of the DSJC500.5.col had already been found in 1996
and reported on by C. Morgenstern in reference [22] of the PLOS online
article:
"Parameter Tuning Patterns for Random Graph Coloring with Quantum
Annealing" , <
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0050060 > .

David Bernier

---------------------------
addendum:

The presumptive solution ( 50-coloring) to DIMACS DSJC500.5.col graph
for 50 colors found by my program implementing Tabu Search :

Vertex number: 1-500 ; Color class: 1-50
1 1
2 20
3 17
4 12
5 12
6 41
7 17
8 34
9 3
10 42
11 3
12 22
13 11
14 42
15 8
16 50
17 31
18 1
19 13
20 47
21 6
22 36
23 27
24 30
25 29
26 20
27 48
28 12
29 33
30 43
31 19
32 4
33 28
34 9
35 21
36 34
37 44
38 45
39 14
40 48
41 18
42 8
43 15
44 47
45 42
46 11
47 6
48 8
49 42
50 20
51 10
52 47
53 41
54 35
55 2
56 19
57 11
58 4
59 46
60 49
61 18
62 38
63 40
64 38
65 50
66 46
67 30
68 34
69 48
70 20
71 9
72 32
73 24
74 2
75 33
76 44
77 15
78 2
79 40
80 47
81 31
82 15
83 35
84 28
85 9
86 9
87 17
88 1
89 23
90 32
91 44
92 12
93 49
94 36
95 2
96 35
97 34
98 19
99 40
100 24
101 35
102 25
103 34
104 20
105 30
106 7
107 11
108 29
109 17
110 3
111 4
112 25
113 21
114 6
115 29
116 50
117 4
118 31
119 41
120 32
121 27
122 6
123 31
124 42
125 37
126 35
127 27
128 5
129 21
130 24
131 28
132 1
133 29
134 25
135 25
136 3
137 48
138 40
139 18
140 8
141 28
142 27
143 24
144 32
145 1
146 9
147 22
148 37
149 7
150 17
151 24
152 11
153 3
154 49
155 45
156 27
157 13
158 26
159 17
160 42
161 5
162 7
163 8
164 5
165 26
166 15
167 49
168 20
169 16
170 3
171 30
172 27
173 33
174 12
175 23
176 44
177 42
178 1
179 16
180 34
181 7
182 28
183 25
184 36
185 41
186 40
187 13
188 37
189 10
190 15
191 15
192 45
193 33
194 44
195 16
196 7
197 32
198 20
199 43
200 18
201 1
202 7
203 20
204 32
205 27
206 45
207 8
208 3
209 3
210 29
211 1
212 31
213 47
214 6
215 41
216 50
217 6
218 14
219 36
220 37
221 13
222 22
223 14
224 19
225 41
226 17
227 10
228 40
229 28
230 25
231 39
232 21
233 31
234 36
235 6
236 16
237 28
238 25
239 42
240 2
241 13
242 39
243 10
244 36
245 10
246 48
247 10
248 44
249 22
250 21
251 37
252 29
253 9
254 39
255 9
256 19
257 4
258 29
259 1
260 13
261 46
262 12
263 12
264 50
265 49
266 36
267 37
268 44
269 23
270 45
271 13
272 32
273 7
274 30
275 6
276 40
277 12
278 21
279 36
280 11
281 21
282 49
283 46
284 10
285 22
286 5
287 38
288 13
289 26
290 32
291 2
292 16
293 22
294 46
295 14
296 10
297 4
298 40
299 7
300 23
301 39
302 47
303 14
304 3
305 4
306 43
307 39
308 45
309 39
310 10
311 45
312 22
313 43
314 47
315 21
316 31
317 47
318 2
319 17
320 7
321 26
322 50
323 7
324 3
325 16
326 37
327 23
328 23
329 11
330 37
331 6
332 43
333 44
334 49
335 23
336 45
337 16
338 43
339 33
340 48
341 16
342 28
343 26
344 46
345 48
346 6
347 18
348 36
349 9
350 20
351 21
352 26
353 31
354 49
355 20
356 48
357 34
358 14
359 4
360 39
361 40
362 50
363 4
364 18
365 10
366 38
367 18
368 1
369 48
370 24
371 18
372 6
373 27
374 45
375 5
376 46
377 44
378 15
379 5
380 19
381 17
382 49
383 14
384 43
385 48
386 46
387 36
388 24
389 47
390 26
391 30
392 26
393 24
394 23
395 31
396 30
397 25
398 5
399 14
400 8
401 23
402 24
403 47
404 39
405 17
406 41
407 43
408 35
409 19
410 26
411 26
412 7
413 21
414 32
415 48
416 13
417 37
418 41
419 40
420 45
421 27
422 33
423 33
424 7
425 38
426 29
427 38
428 47
429 39
430 11
431 15
432 2
433 8
434 8
435 16
436 43
437 34
438 5
439 21
440 46
441 5
442 14
443 35
444 36
445 5
446 40
447 6
448 19
449 9
450 23
451 35
452 9
453 13
454 40
455 50
456 48
457 29
458 2
459 33
460 19
461 17
462 30
463 31
464 28
465 44
466 12
467 46
468 47
469 25
470 11
471 33
472 43
473 35
474 50
475 18
476 39
477 42
478 18
479 38
480 17
481 37
482 8
483 41
484 28
485 19
486 22
487 16
488 5
489 50
490 24
491 42
492 38
493 27
494 19
495 23
496 8
497 11
498 24
499 49
500 13

David Bernier

2017-07-14 14:37:02 UTC

Permalink

Post by David Bernier
[...]

Post by David Bernier
.

DSJC500.5 is a graph with 500 vertices and about 62,500 edges: the
average degree of a vertex is close to 251. It was constructed
as a random graph ~= 1990 by theoretical computer scientist David
Johnson. It's one of dozens of benchmark graphs used in testing old and
new algorithms, particularly in graph coloring.

Laurent Moalic and Alexandre Gondran, in a preprint at arxiv,
report using a variation of Galinier and Hao's Hybrid Coloring Algorithm
which they call HEA in Duet (versions HEAD' and improved HEAD) to find a
47-coloring of DSJC500.5, and other good colorings for some benchmark
graphs.

For most benchmark graphs with 1000 and fewer vertices, the improved
algorithm HEAD matches the best colorings found using Quantum Annealing
coloring (I can't explain it).

At arxiv:

< https://arxiv.org/abs/1401.2184 > .

"Variations on Memetic Algorithms for Graph Coloring Problems".

I eventually succeeded in implementing the simpler algorithm HEAD',
specifically for the 500-vertex benchmark graph DSJC500.5.col .

The program found 3 48-colorings and failed for 4 cases, using
each time a pair of 2 improper/illegal 48-colorings.

Cf.:

<
https://meditationatae.wordpress.com/2017/07/14/hea-in-duet-and-graph-coloring-continuation/

Post by David Bernier
.

I independently checked the 3 purported 48-colorings this morning, and
they passed this test.

David Bernier