-
Notifications
You must be signed in to change notification settings - Fork 1
/
FAQ
31 lines (27 loc) · 1.62 KB
/
FAQ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1. Question: How can I start with a given coloring and write out the optimum coloring found?
Answer: 'color' provides functions to write out and read in stable set covers/partitions.
The file format is similar to DIMACS-format:
Lines starting with
c are comments and can be ignored
p followed by the problem name and number of vertices. These values are used
to verify that only files corresponding to the same problem data are read.
s are followed by a list of integers that constitute a stable set.
Example:
c Stable sets from exactcolors on instance myciel3:
c Syntax:
c p <problem name> <node count>
c s <list of integers ( = nodes of a stable set)>
p myciel3 11
s 1 3 6 8
s 0 4 5 9
s 2 10
s 7
The optimum coloring can be written to a file using the option '-o filename'.
The stable set cover consisting of the columns of the root LP can be written using the
option '-w filename'.
Vice versa, any covering by stable sets (including colorings) can read in using
the option '-r <filename>'. The stable sets are then used as the starting columns
for the coloring LP.
Furthermore, an initial coloring (i.e. partition into stable sets) is
generated by a greedy algorithm using the initial covering and used to initialize the upper bound.
That is, if the covering is already a minimum coloring the upper bound is chosen best possible.