1""" Basic problems for Orca """
2import numpy as np
3from pyqubo import Array
4from qlauncher.problems.problem_formulations.jssp.pyqubo_scheduler import get_jss_bqm
5import qlauncher.problems.problem_initialization as problem
6
7from qlauncher.base import formatter, adapter
8
9
[docs]
10@adapter('qubo', 'qubo_fn')
11def qubo_to_fn(qubo):
12 # TODO check
13 def qubo_fn(bin_vec):
14 return np.dot(bin_vec, np.dot(qubo, bin_vec))
15 return qubo_fn
16
17
[docs]
18@formatter(problem.MaxCut, 'qubo')
19def get_maxcut_qubo(problem: problem.MaxCut):
20 """ Returns Qubo function """
21 n = len(problem.instance)
22 Q = np.zeros((n, n))
23 for (i, j) in problem.instance.edges:
24 Q[i, i] += -1
25 Q[j, j] += -1
26 Q[i, j] += 1
27 Q[j, i] += 1
28
29 return Q, 0
30
31
32@formatter(problem.EC, 'qubo')
33class ECOrca:
34 gamma = 1
35 delta = 0.05
36
37 def Jrr(self, route1, route2):
38 s = len(set(route1).intersection(set(route2)))
39 return s / 2
40
41 def hr(self, route1, routes):
42 i_sum = 0
43 for r in routes:
44 i_sum += len(set(r).intersection(set(route1)))
45 s = i_sum - len(route1) * 2
46 return s / 2
47
48 def calculate_jrr_hr(self, problem: problem.EC):
49 Jrr_dict = dict()
50 indices = np.triu_indices(len(problem.instance), 1)
51 for i1, i2 in zip(indices[0], indices[1]):
52 Jrr_dict[(i1, i2)] = self.Jrr(
53 problem.instance[i1], problem.instance[i2])
54
55 hr_dict = dict()
56 for i in range(len(problem.instance)):
57 hr_dict[i] = self.hr(problem.instance[i], problem.instance)
58
59 return Jrr_dict, hr_dict
60
61 def calculate_lengths_tab(self, problem: problem.EC):
62 tab = []
63 for route in problem.instance:
64 tab.append(len(route))
65 return tab
66
67 def calculate_num_elements(self, problem: problem.EC):
68 d = dict()
69 for route in problem.instance:
70 for el in route:
71 d[el] = 1
72 return len(d)
73
74 def calculate_instance_size(self, problem: problem.EC):
75 # Calculate instance size for training
76 return len(problem.instance)
77
78 def __call__(self, problem: problem.EC):
79 self.num_elements = self.calculate_num_elements(problem)
80 self.len_routes = self.calculate_lengths_tab(problem)
81 Q = np.zeros((len(problem.instance), len(problem.instance)))
82 self.Jrr_dict, self.hr_dict = self.calculate_jrr_hr(problem)
83 for i in self.Jrr_dict:
84 Q[i[0]][i[1]] = self.Jrr_dict[i]
85 Q[i[1]][i[0]] = Q[i[0]][i[1]]
86
87 for i in self.hr_dict:
88 Q[i][i] = -self.hr_dict[i]
89
90 return Q, 0
91
92
93@formatter(problem.JSSP, 'qubo')
94class JSSPOrca:
95 gamma = 1
96 lagrange_one_hot = 1
97 lagrange_precedence = 2
98 lagrange_share = 5
99
100 def _fix_get_jss_bqm(self, instance, max_time, config,
101 lagrange_one_hot=0,
102 lagrange_precedence=0,
103 lagrange_share=0) -> tuple[dict, list, None]:
104 pre_result = get_jss_bqm(instance, max_time, config,
105 lagrange_one_hot=lagrange_one_hot,
106 lagrange_precedence=lagrange_precedence,
107 lagrange_share=lagrange_share)
108 result = (pre_result.spin.linear, pre_result.spin.quadratic,
109 pre_result.spin.offset) # I need to change it into dict somehow
110 return result, list(result[0].keys()), None
111
112 def calculate_instance_size(self, problem: problem.JSSP):
113 # Calculate instance size for training
114 _, variables, _ = self._fix_get_jss_bqm(problem.instance, problem.max_time, self.config,
115 lagrange_one_hot=self.lagrange_one_hot,
116 lagrange_precedence=self.lagrange_precedence,
117 lagrange_share=self.lagrange_share)
118 return len(variables)
119
120 def get_len_all_jobs(self, problem: problem.JSSP):
121 result = 0
122 for job in problem.instance.values():
123 result += len(job)
124 return result
125
126 def one_hot_to_jobs(self, binary_vector, problem: problem.JSSP):
127 actually_its_qubo, variables, model = self._fix_get_jss_bqm(problem.instance, problem.max_time, self.config,
128 lagrange_one_hot=self.lagrange_one_hot,
129 lagrange_precedence=self.lagrange_precedence,
130 lagrange_share=self.lagrange_share)
131 result = [variables[i]
132 for i in range(len(variables)) if binary_vector[i] == 1]
133 return result
134
135 def _set_config(self):
136 self.config = {}
137 self.config['parameters'] = {}
138 self.config['parameters']['job_shop_scheduler'] = {}
139 self.config['parameters']['job_shop_scheduler']['problem_version'] = "optimization"
140
141 def __call__(self, problem: problem.JSSP):
142 # Define the matrix Q used for QUBO
143 self.config = {}
144 self.instance_size = self.calculate_instance_size(problem)
145 self._set_config()
146 actually_its_qubo, variables, model = self._fix_get_jss_bqm(problem.instance, problem.max_time, self.config,
147 lagrange_one_hot=self.lagrange_one_hot,
148 lagrange_precedence=self.lagrange_precedence,
149 lagrange_share=self.lagrange_share)
150 reverse_dict_map = {v: i for i, v in enumerate(variables)}
151
152 Q = np.zeros((self.instance_size, self.instance_size))
153
154 for (label_i, label_j), value in actually_its_qubo[1].items():
155 i = reverse_dict_map[label_i]
156 j = reverse_dict_map[label_j]
157 Q[i, j] += value
158 Q[j, i] = Q[i, j]
159
160 for label_i, value in actually_its_qubo[0].items():
161 i = reverse_dict_map[label_i]
162 Q[i, i] += value
163 return Q / max(np.max(Q), -np.min(Q)), 0
164
165
[docs]
166@formatter(problem.Raw, 'qubo')
167def get_raw_qubo(problem: problem.Raw):
168 return problem.instance
169
170
[docs]
171@formatter(problem.GraphColoring, 'qubo')
172def get_graph_coloring_qubo(problem: problem.GraphColoring):
173 """ Returns Qubo function """
174 num_qubits = problem.instance.number_of_nodes() * problem.num_colors
175 x = Array.create('x', shape=(problem.instance.number_of_nodes(), problem.num_colors), vartype='BINARY')
176 qubo = 0
177 for node in problem.instance.nodes:
178 qubo += (1 - sum(x[node, i] for i in range(problem.num_colors))) ** 2
179 for n1, n2 in problem.instance.edges:
180 for c in range(problem.num_colors):
181 qubo += (x[n1, c] * x[n2, c])
182 model = qubo.compile()
183 qubo_dict, offset = model.to_qubo()
184 Q_matrix = np.zeros((num_qubits, num_qubits))
185 for i in range(num_qubits):
186 for j in range(num_qubits):
187 n1, c1 = i//problem.num_colors, i % problem.num_colors
188 n2, c2 = j//problem.num_colors, j % problem.num_colors
189 key = ("x["+str(n1)+"]["+str(c1)+"]", "x["+str(n2)+"]["+str(c2)+"]")
190 if key in qubo_dict:
191 Q_matrix[i, j] = qubo_dict[key]
192 return Q_matrix, offset
