SHARE
TWEET

Untitled

a guest Aug 21st, 2016 110 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;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top