-
Notifications
You must be signed in to change notification settings - Fork 0
/
test.c
68 lines (66 loc) · 1.97 KB
/
test.c
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
#include <assert.h>
#include <stdio.h>
#include "tsqubo.h"
int main() {
size_t n, nonzeros;
assert(scanf("%zu%zu", &n, &nonzeros) == 2);
assert(n > 0);
assert(nonzeros > 0);
double* Q = calloc(n * n, sizeof(double));
struct tsqubo_instance inst;
tsqubo_instance_init(&inst, 3);
double* diag = calloc(n, sizeof(double));
for (size_t k = 0; k < nonzeros; k++) {
size_t i, j;
double q;
assert(scanf("%zu%zu%lf", &i, &j, &q) == 3);
i--;
j--;
Q[n * i + i] -= q;
Q[n * j + j] -= q;
Q[n * i + j] += 2 * q;
Q[n * j + i] += 2 * q;
diag[i] -= q;
diag[j] -= q;
tsqubo_instance_add_component(&inst, i, j, q);
}
for (size_t i = 0; i < n; i++) tsqubo_instance_add_component(&inst, i, i, diag[i]);
free(diag);
struct tsqubo* ts = tsqubo_new(&inst);
tsqubo_instance_free(&inst);
for (size_t i = 0; i < 10; i++) {
tsqubo_reset_solutions(ts);
tsqubo_reset_tabu(ts);
for (size_t j = 0; j < n; j++)
if (rand() % 2) {
tsqubo_flip_current(ts, j);
double fy = 0;
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j <= i; j++) fy += ts->cur.x[i] * ts->cur.x[j] * Q[n * i + j];
assert(fy == ts->cur.fx);
}
tsqubo_commit_incumbent(ts);
double fx = 0;
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j <= i; j++) fx += ts->inc.x[i] * ts->inc.x[j] * Q[n * i + j];
assert(fx == ts->inc.fx);
for (size_t l = 0; l < 100; l++) {
if (tsqubo_iterate(ts, n / 10)) {
tsqubo_local_search(ts);
tsqubo_commit_incumbent(ts);
}
double fx = 0;
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j <= i; j++) fx += ts->inc.x[i] * ts->inc.x[j] * Q[n * i + j];
assert(fx == ts->inc.fx);
double fy = 0;
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j <= i; j++) fy += ts->cur.x[i] * ts->cur.x[j] * Q[n * i + j];
assert(fy == ts->cur.fx);
}
}
tsqubo_free(ts);
free(ts);
free(Q);
return 0;
}