-
Notifications
You must be signed in to change notification settings - Fork 2
/
evaluate.c
139 lines (109 loc) · 3.93 KB
/
evaluate.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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include "admm.h"
extern Parameters params;
extern FILE *output;
extern int BabPbSize;
/*
* Evaluate a specific node.
* This function computes the upper and lower bounds of a specific node
* (calls SDP bound function) and returns the upper bound of the node
*/
double Evaluate(BabNode *node, Problem *SP, Problem *PP, int rank) {
// create subproblem PP
createSubproblem(node, SP, PP);
// compute the SDP upper bound and run heuristic
double bound = SDPbound(node, SP, PP, rank);
return bound;
}
/*
* Writes subproblem to PP.
*
* Computes the subproblem removing the rows and the columns of the
* fixed variables upper left corner of SP->L
*
* SP is the original problem
* PP is the subproblem (some variables are fixed)
*
* PP is made from SP
* Function prepares objective matrix L for model in -1,1 variables:
*
* max x'LX, s.t. x in {-1,1}^(PP->n)
*/
void createSubproblem(BabNode *node, Problem *SP, Problem *PP) {
// Subproblem size is the number of non-fixed variables in the node
PP->n = BabPbSize + 1 - countFixedVariables(node);
/* build objective:
* Laplacian;
* z'*L*z = sum_{i != fixed, j != fixed} L_ij*xi*xj (smaller matrix L_bar for subproblem)
+ sum_{i = fixed, j = fixed} L_ij*x_i*xj (getFixedValue)
+ sum_{rows of fixed vertices without fixed entries} (linear part, that is twice added to diagonal of L_bar)
*/
/* Laplacian is created by deleting appropriate rows and cols
* of upper left corner of SP->L
*/
int index = 0;
int N = SP->n;
double row_sum = 0.0;
// rows which are deleted due to fixed variable
// later add to diagonal
double fixedRow[PP->n - 1];
for (int i = 0; i < PP->n - 1; ++i)
fixedRow[i] = 0.0;
// counter for fixedRow
int fixed = 0;
// last element (lower right corner) is sum
double sum = 0.0;
for (int i = 0; i < BabPbSize; ++i) {
for (int j = 0; j < BabPbSize; ++j) {
if (!node->xfixed[i] && !node->xfixed[j]) { // delete rows and cols of SP->L
PP->L[index] = SP->L[j + i*N];
row_sum += PP->L[index];
++index;
}
else if ( (node->xfixed[i] && node->sol.X[i] == 1) && !node->xfixed[j]) { // save fixed rows to add to diagonal
fixedRow[fixed] += SP->L[j + i*N];
++fixed;
}
}
if (!node->xfixed[i]) {
PP->L[index] = row_sum; // vector part of PP->L (last column)
++index;
}
// row scaned, set to 0
row_sum = 0.0;
fixed = 0;
}
// add last row (copy from last column)
for (int i = 0; i < PP->n - 1; ++i)
PP->L[i + (PP->n - 1) * PP->n] = PP->L[PP->n - 1 + i * PP->n];
/* LINEAR PART OF PP->L: add 2x vector fixedRow to diagonal, last col and last row */
for (int i = 0; i < PP->n - 1; ++i) {
PP->L[i + i * PP->n] += 2*fixedRow[i];
PP->L[PP->n - 1 + i * PP->n] += 2*fixedRow[i];
PP->L[i + (PP->n - 1) * PP->n] += 2*fixedRow[i];
sum += PP->L[i + (PP->n - 1) * PP->n];
}
/* CONSTANT PART OF PP->L: element (PP->n - 1, PP->n - 1) */
PP->L[PP->n - 1 + (PP->n - 1) * PP->n] = sum;
/* multiple by 1/4 the whole matrix L */
double alpha = 0.25;
int inc = 1;
int nn = (PP->n) * (PP->n);
dscal_(&nn,&alpha,PP->L,&inc);
}
/*
* Return the fixed value of the node.
* The fixed value is contribution of the fixed variables to
* the objective value.
*/
double getFixedValue(BabNode *node, Problem *SP) {
int N = SP->n;
double fixedvalue = 0.0;
for (int i = 0; i < BabPbSize; ++i) {
for (int j = 0; j < BabPbSize; ++j) {
if (node->xfixed[i] && node->xfixed[j]) {
fixedvalue += SP->L[j + i*N] * node->sol.X[i] * node->sol.X[j];
}
}
}
return fixedvalue;
}