-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfp_simanneal.py
67 lines (50 loc) · 1.64 KB
/
bfp_simanneal.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
import math
import sys
import numpy as np
import time
from Hypergraph import Hypergraph
from simanneal import Annealer
"""
Let ROTH(n) be the set of all arithmetic progressions in {1, 2, ...,
n}. It finds a coloring of small discprepancy for ROTH(n) by
simulated annealing.
Usage
-----
$ python3 vbp_simmanneal.py [n]
"""
class BeckFialaProblem(Annealer):
"""
Annealer for Beck-Fiala Problem
"""
def __init__(self, state, graph):
self.graph = graph
super(BeckFialaProblem, self).__init__(state)
def move(self):
"""Inverses a color"""
idx = np.random.randint(0, len(self.state)-1)
self.state[idx] = -self.state[idx]
def energy(self):
"""Calculates the discrepancy of the coloring."""
return self.graph.calc_discrepancy(self.state)
if __name__ == '__main__':
n = int(sys.argv[1])
graph = Hypergraph.roth(n)
init_coloring = np.asarray([np.random.randint(0, 2)*2-1 for i in range(n)])
print("init. coloring:", init_coloring)
bfp = BeckFialaProblem(init_coloring, graph)
bfp.Tmin = 0.2
bfp.steps = 50000
bfp.copy_strategy = "slice"
start_time = time.time()
state, disc = bfp.anneal()
elapsed_time = time.time() - start_time
print("n =", graph.n, ", m =", graph.m)
print("Incidence matrix:\n", graph.incidence)
print("degree=", graph.degree)
print()
print("coloring by simanneal:", state)
print("discrepancy by simanneal:", disc)
print('elapsed time:', elapsed_time)
opt_coloring, disc = graph.find_optimal_coloring()
print('optimal coloring:', opt_coloring)
print('optimal discrepancy: ', disc)