PySCIPOpt  5.1.1
Python Interface for the SCIP Optimization Suite
gcp_fixed_k.py
Go to the documentation of this file.
1 
3 """
4 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
5 """
6 
7 from pyscipopt import Model, quicksum
8 
9 
10 def gcp_fixed_k(V, E, K):
11  """gcp_fixed_k -- model for minimizing number of bad edges in coloring a graph
12  Parameters:
13  - V: set/list of nodes in the graph
14  - E: set/list of edges in the graph
15  - K: number of colors to be used
16  Returns a model, ready to be solved.
17  """
18  model = Model("gcp - fixed k")
19 
20  x, z = {}, {}
21  for i in V:
22  for k in range(K):
23  x[i, k] = model.addVar(vtype="B", name="x(%s,%s)" % (i, k))
24  for (i, j) in E:
25  z[i, j] = model.addVar(vtype="B", name="z(%s,%s)" % (i, j))
26 
27  for i in V:
28  model.addCons(quicksum(x[i, k] for k in range(K)) == 1, "AssignColor(%s)" % i)
29 
30  for (i, j) in E:
31  for k in range(K):
32  model.addCons(x[i, k] + x[j, k] <= 1 + z[i, j], "BadEdge(%s,%s,%s)" % (i, j, k))
33 
34  model.setObjective(quicksum(z[i, j] for (i, j) in E), "minimize")
35 
36  model.data = x, z
37  return model
38 
39 
40 def solve_gcp(V, E):
41  """solve_gcp -- solve the graph coloring problem with bisection and fixed-k model
42  Parameters:
43  - V: set/list of nodes in the graph
44  - E: set/list of edges in the graph
45  Returns tuple with number of colors used, and dictionary mapping colors to vertices
46  """
47  LB = 0
48  UB = len(V)
49  color = {}
50  while UB - LB > 1:
51  K = int((UB + LB) / 2)
52  gcp = gcp_fixed_k(V, E, K)
53  # gcp.Params.OutputFlag = 0 # silent mode
54  # gcp.Params.Cutoff = .1
55  gcp.setObjlimit(0.1)
56  gcp.optimize()
57  status = gcp.getStatus()
58  if status == "optimal":
59  x, z = gcp.data
60  for i in V:
61  for k in range(K):
62  if gcp.getVal(x[i, k]) > 0.5:
63  color[i] = k
64  break
65  # else:
66  # raise "undefined color for", i
67  UB = K
68  else:
69  LB = K
70 
71  return UB, color
72 
73 
74 import random
75 
76 
77 def make_data(n, prob):
78  """make_data: prepare data for a random graph
79  Parameters:
80  - n: number of vertices
81  - prob: probability of existence of an edge, for each pair of vertices
82  Returns a tuple with a list of vertices and a list edges.
83  """
84  V = range(1, n + 1)
85  E = [(i, j) for i in V for j in V if i < j and random.random() < prob]
86  return V, E
87 
88 
89 if __name__ == "__main__":
90  random.seed(1)
91  V, E = make_data(75, .25)
92 
93  K, color = solve_gcp(V, E)
94  print("minimum number of colors:", K)
95  print("solution:", color)
gcp_fixed_k.make_data
def make_data(n, prob)
Definition: gcp_fixed_k.py:77
pyscipopt.expr.quicksum
def quicksum(termlist)
Definition: expr.pxi:357
gcp_fixed_k.gcp_fixed_k
def gcp_fixed_k(V, E, K)
Definition: gcp_fixed_k.py:10
gcp_fixed_k.solve_gcp
def solve_gcp(V, E)
Definition: gcp_fixed_k.py:40
gcp_fixed_k
Definition: gcp_fixed_k.py:1