-
Notifications
You must be signed in to change notification settings - Fork 5
/
section3.2.py
86 lines (75 loc) · 2.44 KB
/
section3.2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
"""
Section 3.2 The Max Cut Problem
Given an undirected graph G(V,E) with a vertex set V and an edge set E, the Max Cut problem seeks to partition V into two sets such that the number of edges between the two sets (considered to be severed by the cut), is a large as possible.
"""
import dimod
from dwave.system.samplers import DWaveSampler
from dwave.system.composites import EmbeddingComposite
linear = {1: -2, 2: -2, 3: -3, 4: -3, 5: -2}
quadratic = {
(1, 2): 1,
(1, 3): 1,
(2, 1): 1,
(2, 4): 1,
(3, 1): 1,
(3, 4): 1,
(3, 5): 1,
(4, 2): 1,
(4, 5): 1,
(5, 3): 1,
(5, 4): 1,
}
offset = 0.0
vartype = dimod.BINARY
# Expected Solution
#
# x = (0, 1, 1, 0, 0)
# Hence vertices 2 and 3 are in one set and vertices 1, 4, and 5 are in the other, with a maximum cut value of 5
bqm = dimod.BinaryQuadraticModel(linear, quadratic, offset, vartype)
sampler = dimod.ExactSolver()
sample_set = sampler.sample(bqm)
print("Using ExactSolver()")
print(sample_set)
# Using ExactSolver()
# 1 2 3 4 5 energy num_oc.
# 4 0 1 1 0 0 -5.0 1
# 8 0 0 1 1 0 -5.0 1
# 9 1 0 1 1 0 -5.0 1
# 11 0 1 1 1 0 -5.0 1
# 14 1 0 0 1 0 -5.0 1
# ...
# 0 0 0 0 0 0 0.0 1
# ['BINARY', 32 rows, 32 samples, 5 variables]
print("#" * 80)
sampler = dimod.SimulatedAnnealingSampler()
sample_set = sampler.sample(bqm)
print("Using SimulatedAnnlearingSampler()")
print(sample_set)
# Using SimulatedAnnlearingSampler()
# 1 2 3 4 5 energy num_oc.
# 0 1 0 1 1 0 -5.0 1
# 1 1 0 0 1 0 -5.0 1
# 2 0 0 1 1 0 -5.0 1
# 3 1 0 0 1 1 -5.0 1
# 4 0 1 1 1 0 -5.0 1
# 5 1 0 0 1 1 -5.0 1
# 6 1 0 1 1 0 -5.0 1
# 7 0 1 1 0 1 -5.0 1
# 8 1 0 0 1 1 -5.0 1
# 9 1 0 0 1 1 -5.0 1
# ['BINARY', 10 rows, 10 samples, 5 variables]
print("#" * 80)
sampler = EmbeddingComposite(DWaveSampler())
sample_set = sampler.sample(bqm, num_reads=50)
print("Using DWaveSampler()")
print(sample_set)
# Using DWaveSampler()
# 1 2 3 4 5 energy num_oc. chain_.
# 0 0 1 1 0 0 -5.0 8 0.0
# 1 1 0 1 1 0 -5.0 2 0.0
# 2 0 1 1 0 1 -5.0 11 0.0
# 3 1 0 0 1 1 -5.0 13 0.0
# 4 0 0 1 1 0 -5.0 4 0.0
# 5 0 1 1 1 0 -5.0 9 0.0
# 6 1 0 0 1 0 -5.0 3 0.0
# ['BINARY', 7 rows, 50 samples, 5 variables]