Advertisement
Guest User

Untitled

a guest
Aug 21st, 2016
220
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* save this file as color.txt then run: ./glpsol --math -o solution.txt color.txt */
  2.  
  3. /* COLOR, Graph Coloring Problem */
  4.  
  5. /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
  6.  
  7. /* Given an undirected loopless graph G = (V, E), where V is a set of
  8. nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to
  9. find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set
  10. of colors whose cardinality is as small as possible, such that
  11. F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must
  12. be assigned different colors. */
  13.  
  14. param n, integer, >= 2;
  15. /* number of nodes */
  16.  
  17. set V := {1..n};
  18. /* set of nodes */
  19.  
  20. set E, within V cross V;
  21. /* set of arcs */
  22.  
  23. check{(i,j) in E}: i != j;
  24. /* there must be no loops */
  25.  
  26. /* We need to estimate an upper bound of the number of colors |C|.
  27. The number of nodes |V| can be used, however, for sparse graphs such
  28. bound is not very good. To obtain a more suitable estimation we use
  29. an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already
  30. assigned some colors. To assign a color to node i we see if there is
  31. an existing color not used for coloring nodes adjacent to node i. If
  32. so, we use this color, otherwise we introduce a new color. */
  33.  
  34. set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
  35. /* symmetrisized set of arcs */
  36.  
  37. param z{i in V, case in 0..1} :=
  38. /* z[i,0] = color index assigned to node i
  39. z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are
  40. adjacent to node i */
  41. ( if case = 0 then
  42. ( /* compute z[i,0] */
  43. min{c in 1..z[i,1]}
  44. ( if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then
  45. c
  46. else
  47. z[i,1] + 1
  48. )
  49. )
  50. else
  51. ( /* compute z[i,1] */
  52. if not exists{j in V: j < i} (i,j) in EE then
  53. 1
  54. else
  55. max{j in V: j < i and (i,j) in EE} z[j,0]
  56. )
  57. );
  58.  
  59. check{(i,j) in E}: z[i,0] != z[j,0];
  60. /* check that all adjacent nodes are assigned distinct colors */
  61.  
  62. param nc := max{i in V} z[i,0];
  63. /* number of colors used by the heuristic; obviously, it is an upper
  64. bound of the optimal solution */
  65.  
  66. display nc;
  67.  
  68. var x{i in V, c in 1..nc}, binary;
  69. /* x[i,c] = 1 means that node i is assigned color c */
  70.  
  71. var u{c in 1..nc}, binary;
  72. /* u[c] = 1 means that color c is used, i.e. assigned to some node */
  73.  
  74. var color{i in 1..n}, integer;
  75.  
  76. s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;
  77. /* each node must be assigned exactly one color */
  78.  
  79. s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c];
  80. /* adjacent nodes cannot be assigned the same color */
  81.  
  82. minimize obj: sum{c in 1..nc} u[c];
  83. /* objective is to minimize the number of colors used */
  84.  
  85. solve;
  86.  
  87. for{i in V,c in 1..nc:x[i,c]}printf"%d %d\n",i,c;
  88.  
  89. data;
  90.  
  91. param n := 19;
  92.  
  93. set E :=
  94. 1 3
  95. 1 8
  96. 1 11
  97. 1 12
  98. 1 16
  99. 1 19
  100. 2 3
  101. 2 4
  102. 2 6
  103. 2 8
  104. 2 10
  105. 2 11
  106. 2 12
  107. 2 15
  108. 2 16
  109. 3 11
  110. 3 12
  111. 3 14
  112. 3 16
  113. 4 5
  114. 4 9
  115. 4 12
  116. 4 14
  117. 4 15
  118. 4 16
  119. 5 12
  120. 6 14
  121. 6 19
  122. 7 18
  123. 7 19
  124. 8 16
  125. 8 18
  126. 10 14
  127. 10 19
  128. 11 19
  129. 12 13
  130. 12 15
  131. 12 17
  132. 12 18
  133. 13 19
  134. 14 18
  135. 14 19
  136. 16 19
  137. ;
  138.  
  139. end;
Advertisement
RAW Paste Data Copied
Advertisement