Next: Experimental results
Up: SWO for graph coloring
Previous: SWO for graph coloring
Subsections
The priority sequence for graph coloring consists of an ordered list
of nodes. The solver is always trying to produce a
coloring that uses colors from the target set, which has one
less color than was used to color the best solution so far.
Again, we
describe the implementation in terms of the three main components of
SWO:
The constructor assigns colors to nodes in
priority sequence order. If a node's color in the previous
solution is still available (i.e. no adjacent node is using it yet),
and is in the target set, then that color is assigned. If that fails,
it tries to assign a color in the current target set, picking the
color that is least constraining on adjacent uncolored nodes, i.e. the
color that reduces the adjacent nodes' remaining color
choices the least. If none of the target colors are available, the
constructor tries to ``grab'' a color in the target set from its
neighbors. A color can only be grabbed if all neighbor nodes with
that color have at least one other choice within the target set.
If multiple colors can be grabbed, then the least constraining one
is picked. If no color in the target set can be grabbed then
a color outside the target set is assigned.
Nodes that are early in the priority sequence are more likely to have
a wide range of colors to pick from. Nodes that come later may grab
colors from earlier nodes, but only if the earlier nodes have other
color options within the target set.
Blame is assigned to each node whose assigned
color is outside the target set, with the amount of blame increasing
for each additional color that must be added to the target set. We
ran experiments with several different variations of color-based
analysis. All of them performed reasonably.
The prioritizer modifies the previous
sequence of nodes by moving nodes with blame forward in the sequence
according to how much blame each received. This is done the same
way it is done for the scheduling problems. The initial sequence is
a list of nodes sorted in decreasing degree order, with some noise
added to slightly shuffle the sort.
Table 3:
Experimental results: graph coloring problems
| |
SWO |
IG |
Dist. IMPASSE |
Par. IMPASSE |
TABU |
| Problem |
colors |
time |
colors |
time |
colors |
time |
colors |
time |
colors |
time |
| DSJC125.5 |
18.3 |
1.6 |
18.9 |
2.5 |
17.0 |
6.3 |
17.0 |
4043.6 |
20.0 |
153.3 |
| DSJC250.5 |
31.9 |
8.3 |
32.8 |
6.9 |
28.0 |
268.5 |
29.2 |
4358.1 |
35.0 |
3442.2 |
| DSJC500.5 |
56.3 |
40.9 |
58.6 |
18.2 |
49.0 |
8109.1 |
53.0 |
4783.9 |
65.0 |
3442.2 |
| DSJC1000.5 |
101.5 |
208.6 |
104.2 |
67.6 |
89.0 |
41488.7 |
100.0 |
5333.8 |
117.0 |
3442.2 |
| C2000.5 |
185.7 |
1046.2 |
190.0 |
272.4 |
165.0 |
14097.9 |
-- |
-- |
-- |
-- |
| C4000.5 |
341.6 |
4950.8 |
346.9 |
1054.1 |
-- |
-- |
-- |
-- |
-- |
-- |
| R125.1 |
5.0 |
0.2 |
5.0 |
2.0 |
5.0 |
0.2 |
5.0 |
64.6 |
5.0 |
0.4 |
| R125.1c |
46.0 |
5.1 |
46.0 |
1.1 |
46.0 |
0.2 |
46.0 |
85.0 |
46.0 |
0.9 |
| R125.5 |
36.0 |
2.8 |
36.9 |
1.9 |
36.0 |
0.2 |
37.0 |
33.0 |
36.0 |
0.7 |
| R250.1 |
8.0 |
0.5 |
8.0 |
7.0 |
8.0 |
0.2 |
8.0 |
22.0 |
8.0 |
0.2 |
| R250.1c |
64.0 |
30.6 |
64.0 |
4.6 |
64.0 |
0.5 |
64.0 |
278.2 |
65.0 |
46.4 |
| R250.5 |
65.0 |
14.7 |
68.4 |
8.3 |
65.0 |
82.2 |
66.0 |
39.9 |
66.0 |
59.0 |
| DSJR500.1 |
12.0 |
2.0 |
12.0 |
21.1 |
12.0 |
0.2 |
12.0 |
26.6 |
12.0 |
0.5 |
| DSJR500.1c |
85.2 |
96.9 |
85.0 |
14.6 |
85.0 |
59.1 |
85.2 |
5767.7 |
87.0 |
3442.2 |
| DSJR500.5 |
124.1 |
68.7 |
129.6 |
26.1 |
123.0 |
175.3 |
128.0 |
90.5 |
126.0 |
395.1 |
| R1000.1 |
20.0 |
8.0 |
20.6 |
87.2 |
20.0 |
8.2 |
20.0 |
49.9 |
20.0 |
1.7 |
| R1000.1c |
101.7 |
433.2 |
98.8 |
49.1 |
98.0 |
563.3 |
102.6 |
3940.0 |
105.0 |
3442.2 |
| R1000.5 |
238.9 |
574.5 |
253.2 |
102.9 |
241.0 |
944.0 |
245.6 |
215.9 |
248.0 |
3442.2 |
| flat300_20_0 |
25.3 |
16.4 |
20.2 |
3.8 |
20.0 |
0.2 |
20.0 |
274.3 |
39.0 |
3442.2 |
| flat300_26_0 |
35.8 |
12.0 |
37.1 |
7.7 |
26.0 |
10.0 |
32.4 |
6637.1 |
41.0 |
3442.2 |
| flat300_28_0 |
35.7 |
11.9 |
37.0 |
9.6 |
31.0 |
1914.2 |
33.0 |
1913.5 |
41.0 |
3442.2 |
| flat1000_50_0 |
100.0 |
203.9 |
65.6 |
146.3 |
50.0 |
0.2 |
97.0 |
7792.7 |
-- |
-- |
| flat1000_60_0 |
100.7 |
198.0 |
102.5 |
87.3 |
60.0 |
0.2 |
97.8 |
6288.4 |
-- |
-- |
| flat1000_76_0 |
100.6 |
208.4 |
103.6 |
79.6 |
89.0 |
11034.0 |
99.0 |
6497.9 |
-- |
-- |
| latin_sqr_10 |
111.5 |
369.2 |
106.7 |
59.7 |
98.0 |
5098.0 |
109.2 |
6520.1 |
130.0 |
3442.2 |
| le450_15a |
15.0 |
5.5 |
17.9 |
17.0 |
15.0 |
0.2 |
15.0 |
162.6 |
16.0 |
17.8 |
| le450_15b |
15.0 |
6.1 |
17.9 |
16.2 |
15.0 |
0.2 |
15.0 |
178.4 |
15.0 |
28.4 |
| le450_15c |
21.1 |
8.0 |
25.6 |
14.5 |
15.0 |
57.2 |
16.6 |
2229.6 |
23.0 |
3442.2 |
| le450_15d |
21.2 |
7.8 |
25.8 |
13.5 |
15.0 |
36.3 |
16.8 |
2859.6 |
23.0 |
3442.2 |
| mulsol.i.1 |
49.0 |
5.9 |
49.0 |
4.2 |
49.0 |
0.2 |
49.0 |
27.2 |
49.0 |
0.3 |
| school1 |
14.0 |
8.4 |
14.0 |
10.5 |
14.0 |
0.2 |
14.0 |
46.3 |
29.0 |
90.7 |
| school1_nsh |
14.0 |
7.2 |
14.1 |
8.9 |
14.0 |
0.2 |
14.0 |
66.4 |
26.0 |
31.2 |
|
Next: Experimental results
Up: SWO for graph coloring
Previous: SWO for graph coloring
Dave Clements
1999-04-13