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