| 1 |
/*===========================================================================*/ |
| 2 |
/* */ |
| 3 |
/* This file is part of a demonstration application for use with the */ |
| 4 |
/* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ |
| 5 |
/* the Set Partitioning Problem. */ |
| 6 |
/* */ |
| 7 |
/* (c) Copyright 2005-2007 Marta Eso and Ted Ralphs. All Rights Reserved. */ |
| 8 |
/* */ |
| 9 |
/* This application was originally developed by Marta Eso and was modified */ |
| 10 |
/* Ted Ralphs ([email protected]) */ |
| 11 |
/* */ |
| 12 |
/* This software is licensed under the Eclipse Public License. Please see */ |
| 13 |
/* accompanying file for terms. */ |
| 14 |
/* */ |
| 15 |
/*===========================================================================*/ |
| 16 |
|
| 17 |
/* system include files */ |
| 18 |
#include <stdlib.h> |
| 19 |
#include <string.h> |
| 20 |
#include <math.h> |
| 21 |
|
| 22 |
/* SYMPHONY include files */ |
| 23 |
#include "sym_constants.h" |
| 24 |
#include "sym_macros.h" |
| 25 |
#include "sym_pack_cut.h" |
| 26 |
#include "sym_qsort.h" |
| 27 |
#include "sym_cg.h" |
| 28 |
|
| 29 |
/* SPP include files */ |
| 30 |
#include "spp_constants.h" |
| 31 |
#include "spp_types.h" |
| 32 |
#include "spp_common.h" |
| 33 |
#include "spp_cg.h" |
| 34 |
#include "spp_cg_functions.h" |
| 35 |
|
| 36 |
/*****************************************************************************/ |
| 37 |
/*****************************************************************************/ |
| 38 |
/* ODD HOLES */ |
| 39 |
/*****************************************************************************/ |
| 40 |
/*****************************************************************************/ |
| 41 |
/*===========================================================================* |
| 42 |
* tmp arrays used |
| 43 |
* find_violated_odd_holes: |
| 44 |
* roots : itmp_8nodenum |
| 45 |
* oh : ... + nodenum |
| 46 |
* hubs : ... + 2 nodenum |
| 47 |
* hub_coef : ... + 3 nodenum |
| 48 |
* itmp : ... + 5 nodenum |
| 49 |
* new_cut : cuttmp |
| 50 |
* -> find_chordless_oh: |
| 51 |
* path_u : itmp_8nodenum + 2 nodenum |
| 52 |
* path_w : ... + 3 nodenum |
| 53 |
* -> min_path_to_root: |
| 54 |
* pred : itmp_8nodenum + 4 nodenum |
| 55 |
* reached : ... + 5 nodenum |
| 56 |
* dist : dtmp_2nodenum |
| 57 |
* -> rotate_odd_hole: no tmp |
| 58 |
* -> register_and_send_cut: |
| 59 |
* indices: itmp_8nodenum + 5 nodenum |
| 60 |
* coefs : dtmp_2nodenum |
| 61 |
*===========================================================================*/ |
| 62 |
|
| 63 |
int find_violated_odd_holes(spp_cg_problem *spp, double etol) |
| 64 |
{ |
| 65 |
int nodenum = spp->fgraph->nodenum; |
| 66 |
fnode *nodes = spp->fgraph->nodes; |
| 67 |
char *node_node = spp->fgraph->node_node; |
| 68 |
int *lnodes = spp->lgraph->lnodes; |
| 69 |
int *lbeg = spp->lgraph->lbeg; |
| 70 |
int *roots = spp->tmp->itmp_8nodenum; |
| 71 |
int *oh = spp->tmp->itmp_8nodenum + nodenum; |
| 72 |
int *hubs = spp->tmp->itmp_8nodenum + 2 * nodenum; |
| 73 |
int *hub_coef = spp->tmp->itmp_8nodenum + 3 * nodenum; |
| 74 |
int *itmp = spp->tmp->itmp_8nodenum + 7 * nodenum; |
| 75 |
double *dtmp = spp->tmp->dtmp_2nodenum; |
| 76 |
cut_data *new_cut = spp->tmp->cuttmp; |
| 77 |
int begl, endl, levelnum, *coef; |
| 78 |
int i, j, l, cnt, oh_len, hub_len, num_roots, numcuts = 0; |
| 79 |
int u, v, w; |
| 80 |
double prob, choose, lhs_oh, violation, *dcoef; |
| 81 |
|
| 82 |
/* Choose a set of nodes randomly to be the roots (one by one) |
| 83 |
of the bfs tree. Choose 20 to 50 percent of all nodes, depending |
| 84 |
on the density of the graph (the denser the graph, the more nodes we |
| 85 |
choose right now). Should be made a parameter. */ |
| 86 |
prob = .2 + .3 * spp->fgraph->density; |
| 87 |
for (i = 0, num_roots = 0; i < nodenum; i++){ |
| 88 |
/* choose each node with probability prob */ |
| 89 |
choose = (double)RANDOM()/MAXINT; |
| 90 |
if (choose < prob) |
| 91 |
roots[num_roots++] = i; |
| 92 |
} |
| 93 |
|
| 94 |
for (i = 0; i < num_roots; i++) { |
| 95 |
v = roots[i]; |
| 96 |
/* construct level graph with root v and display it */ |
| 97 |
construct_level_graph(spp->fgraph, v, spp->lgraph); |
| 98 |
/* display_level_graph(spp, spp->fgraph); */ |
| 99 |
|
| 100 |
/* for each level >= 2 */ |
| 101 |
levelnum = spp->lgraph->levelnum; |
| 102 |
for (l = 2; l < levelnum; l++) { |
| 103 |
begl = lbeg[l]; endl = lbeg[l+1]; |
| 104 |
/* if there is at most one node on this level: continue */ |
| 105 |
if (endl - begl <= 1) |
| 106 |
continue; |
| 107 |
oh_len = 2 * l + 1; |
| 108 |
|
| 109 |
/* examine each pair of adjacent nodes on this level. |
| 110 |
note: u and w are indices wrt lgraph here, so lnodes[u] and |
| 111 |
lnodes[w] are the indices wrt fgraph! */ |
| 112 |
for (u = begl; u < endl - 1; u++) { |
| 113 |
for (w = u + 1; w < endl; w++) { |
| 114 |
/* if the nodes are adjacent try to find paths from u and w |
| 115 |
to the root (v) */ |
| 116 |
if (node_node[lnodes[u] * nodenum + lnodes[w]]) { |
| 117 |
lhs_oh = find_chordless_oh(spp, spp->fgraph, |
| 118 |
lnodes[u], lnodes[w], oh); |
| 119 |
if (lhs_oh > -1) { |
| 120 |
if (lhs_oh > l + etol) { |
| 121 |
/* odd hole is violated: send back cut */ |
| 122 |
coef = (int *)(dtmp); |
| 123 |
for (j = 0; j < oh_len; j++) |
| 124 |
coef[j] = nodes[oh[j]].ind; |
| 125 |
rotate_odd_hole(oh_len, coef, itmp); |
| 126 |
memcpy(new_cut->coef, coef, oh_len * ISIZE); |
| 127 |
new_cut->type = ODD_HOLE; |
| 128 |
new_cut->size = oh_len * ISIZE; |
| 129 |
new_cut->rhs = l; |
| 130 |
new_cut->range = 0; |
| 131 |
new_cut->sense = 'L'; |
| 132 |
violation = lhs_oh - l; |
| 133 |
numcuts += |
| 134 |
register_and_send_cut(spp, new_cut, violation, etol); |
| 135 |
} else { |
| 136 |
/* odd hole is not violated: try to lift */ |
| 137 |
/* display_level_graph(spp, spp->fgraph); */ |
| 138 |
lhs_oh = |
| 139 |
lift_nonviolated_odd_hole(spp, oh_len, oh, lhs_oh, |
| 140 |
&hub_len, hubs, hub_coef); |
| 141 |
if (lhs_oh > l + etol) { |
| 142 |
/* lifted odd hole is violated: send back cut */ |
| 143 |
coef = (int *)(dtmp); |
| 144 |
coef[0] = oh_len; |
| 145 |
coef[1] = hub_len; |
| 146 |
for (j = 0, cnt = 2; j < oh_len; j++) |
| 147 |
coef[cnt++] = nodes[oh[j]].ind; |
| 148 |
rotate_odd_hole(oh_len, coef + 2, itmp); |
| 149 |
for (j = 0; j < hub_len; j++) |
| 150 |
coef[cnt++] = nodes[hubs[j]].ind; |
| 151 |
memcpy(new_cut->coef, coef, cnt * ISIZE); |
| 152 |
dcoef = dtmp; |
| 153 |
for (j = 0; j < hub_len; j++) |
| 154 |
dcoef[j] = (double) hub_coef[j]; |
| 155 |
memcpy(new_cut->coef + cnt * ISIZE, dcoef, |
| 156 |
hub_len * DSIZE); |
| 157 |
new_cut->type = ODD_HOLE_LIFTED; |
| 158 |
new_cut->size = cnt * ISIZE + hub_len * DSIZE; |
| 159 |
new_cut->rhs = l; |
| 160 |
new_cut->range = 0; |
| 161 |
new_cut->sense = 'L'; |
| 162 |
violation = lhs_oh - l; |
| 163 |
numcuts += |
| 164 |
register_and_send_cut(spp, new_cut, violation,etol); |
| 165 |
} |
| 166 |
/* undisplay_level_graph(spp); */ |
| 167 |
} |
| 168 |
} |
| 169 |
} /* endif u, w adjacent */ |
| 170 |
} /* endfor w */ |
| 171 |
} /* endfor u */ |
| 172 |
|
| 173 |
} /* endfor l */ |
| 174 |
|
| 175 |
/* undisplay_level_graph(spp); */ |
| 176 |
} /* endfor i */ |
| 177 |
return(numcuts); |
| 178 |
} |
| 179 |
|
| 180 |
/*===========================================================================*/ |
| 181 |
|
| 182 |
/*===========================================================================* |
| 183 |
* Find a chordless odd hole of minimum cost (weights of edges added up |
| 184 |
* along the cycle) that contains u, w, and the root of the level-graph. |
| 185 |
* Returns the value of the lhs for the odd hole, -1 if no odd hole is found. |
| 186 |
* |
| 187 |
* u, w (IN) indices of nodes (wrt fgraph) thru which an odd hole is |
| 188 |
* sought. |
| 189 |
* oh (OUT) contains indices of nodes (wrt fgraph) in the odd hole |
| 190 |
* if one is found (u ... root ... w), garbage ow. |
| 191 |
*===========================================================================*/ |
| 192 |
|
| 193 |
double find_chordless_oh(spp_cg_problem *spp, frac_graph *fgraph, int u, |
| 194 |
int w, int *oh) |
| 195 |
{ |
| 196 |
int nodenum = fgraph->nodenum; |
| 197 |
fnode *nodes = fgraph->nodes; |
| 198 |
char *node_node = fgraph->node_node; |
| 199 |
int *level_of_node = spp->lgraph->level_of_node; |
| 200 |
int *path_u = spp->tmp->itmp_8nodenum + 2 * nodenum; |
| 201 |
int *path_w = spp->tmp->itmp_8nodenum + 3 * nodenum; |
| 202 |
int *saved_levels = oh; /* we use oh to temp store the levels of nodes */ |
| 203 |
int root = spp->lgraph->root; |
| 204 |
double cost_oh, lhs_oh = -1, cost_path_u = -1, cost_path_w = -1; |
| 205 |
int z; /* a node index */ |
| 206 |
int i, j, l, deg; |
| 207 |
|
| 208 |
l = level_of_node[u]; |
| 209 |
/* find min cost path to the root from u in the level graph */ |
| 210 |
min_path_to_root(spp, fgraph, u, path_u, &cost_path_u); |
| 211 |
/* save the levels */ |
| 212 |
memcpy(saved_levels, level_of_node, nodenum * ISIZE); |
| 213 |
/* block the nodes on the path from u to the root and their neighbors |
| 214 |
(except for the root) by setting the levels of these nodes to -1 */ |
| 215 |
for (i = 0; i < l; i++) { |
| 216 |
z = path_u[i]; |
| 217 |
deg = nodes[z].degree; |
| 218 |
level_of_node[z] = -1; |
| 219 |
for (j = 0; j < deg; j++) |
| 220 |
level_of_node[nodes[z].nbrs[j]] = -1; |
| 221 |
} |
| 222 |
level_of_node[root] = 0; |
| 223 |
/* now the level of w is -1 since it is adjacent to u. w can also be |
| 224 |
adjacent to the second node on the path (the one above u) but not |
| 225 |
to nodes on higher levels b/c of the BFS ordering of the level graph. |
| 226 |
If w is adjacent to the second node, there is a chord, so return. */ |
| 227 |
if (node_node[w * nodenum + path_u[1]]) { |
| 228 |
/* restore levels */ |
| 229 |
memcpy(level_of_node, saved_levels, nodenum * ISIZE); |
| 230 |
return(lhs_oh); |
| 231 |
} |
| 232 |
/* restore level of w */ |
| 233 |
level_of_node[w] = l; |
| 234 |
/* find min cost path to the root from w in the level graph */ |
| 235 |
min_path_to_root(spp, fgraph, w, path_w, &cost_path_w); |
| 236 |
/* restore levels */ |
| 237 |
memcpy(level_of_node, saved_levels, nodenum * ISIZE); |
| 238 |
|
| 239 |
/* if there is a path from w to the root, put together the odd hole |
| 240 |
and compute its cost */ |
| 241 |
if (cost_path_w > -1) { |
| 242 |
memcpy(oh, path_u, (l+1) * ISIZE); |
| 243 |
for (i = 1; i <= l; i++) |
| 244 |
oh[l+i] = path_w[l-i]; |
| 245 |
cost_oh = cost_path_u + cost_path_w + 1 - nodes[u].val - nodes[w].val; |
| 246 |
lhs_oh = l + (1 - cost_oh) / 2; |
| 247 |
} |
| 248 |
return(lhs_oh); |
| 249 |
} |
| 250 |
|
| 251 |
/*===========================================================================*/ |
| 252 |
|
| 253 |
/*===========================================================================* |
| 254 |
* Find a shortest path of length level_of_node[u] from u to the root of |
| 255 |
* the level-graph. Nodes on levels higher than that of u are enumerated |
| 256 |
* in a BFS fashion. If no path exists from u to the root, *pcost is -1. |
| 257 |
* |
| 258 |
* u (IN) is the index of the node (wrt fgraph) from where shortest |
| 259 |
* path to the root is sought, |
| 260 |
* path_u (OUT) contains indices of nodes (wrt fgraph) on the shortest path |
| 261 |
* from u to the root if one exists, garbage ow. |
| 262 |
* pcost (OUT) pointer to the cost of the shortest path (to -1 if none found) |
| 263 |
*===========================================================================*/ |
| 264 |
|
| 265 |
void min_path_to_root(spp_cg_problem *spp, frac_graph *fgraph, int u, |
| 266 |
int *path_u, double *pcost) |
| 267 |
{ |
| 268 |
int nodenum = fgraph->nodenum; |
| 269 |
int root = spp->lgraph->root; |
| 270 |
int *level_of_node = spp->lgraph->level_of_node; |
| 271 |
fnode *nodes = fgraph->nodes; |
| 272 |
int i, pos, nextpos, x, y, level_x; |
| 273 |
/* pred[w] is the predecessor of node w in the level-by-level shortest |
| 274 |
path tree built from u; |
| 275 |
dist[w] is the shortest path distance of w from u in the above tree, |
| 276 |
reached[] contains the indices of nodes already reached, in the order |
| 277 |
they have been reached. */ |
| 278 |
int *pred = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 279 |
double *dist = spp->tmp->dtmp_2nodenum; |
| 280 |
int *reached = spp->tmp->itmp_8nodenum + 5 * nodenum; |
| 281 |
|
| 282 |
/* initialize */ |
| 283 |
for (i = 0; i < nodenum; i++) { |
| 284 |
pred[i] = nodenum; /* this is a dummy node */ |
| 285 |
dist[i] = spp->lgraph->levelnum + 2; /* obvious ub on dist */ |
| 286 |
} |
| 287 |
|
| 288 |
pred[u] = u; |
| 289 |
dist[u] = 0; |
| 290 |
reached[0] = u; |
| 291 |
pos = 0; |
| 292 |
nextpos = 1; |
| 293 |
|
| 294 |
while (pos < nextpos) { |
| 295 |
x = reached[pos++]; |
| 296 |
level_x = level_of_node[x]; |
| 297 |
for (i = 0; i < nodes[x].degree; i++) { |
| 298 |
y = nodes[x].nbrs[i]; |
| 299 |
if (level_of_node[y] == level_x - 1) { |
| 300 |
if (pred[y] == nodenum) |
| 301 |
reached[nextpos++] = y; |
| 302 |
if (dist[y] > dist[x] + nodes[x].edgecosts[i]) { |
| 303 |
dist[y] = dist[x] + nodes[x].edgecosts[i]; |
| 304 |
pred[y] = x; |
| 305 |
} |
| 306 |
} |
| 307 |
} |
| 308 |
} |
| 309 |
|
| 310 |
/* if the root has been reached... */ |
| 311 |
if (pred[root] < nodenum){ |
| 312 |
pos = level_of_node[u]; |
| 313 |
path_u[pos--] = root; |
| 314 |
x = pred[root]; |
| 315 |
while (x != u){ |
| 316 |
path_u[pos--] = x; |
| 317 |
x = pred[x]; |
| 318 |
} |
| 319 |
path_u[pos] = u; |
| 320 |
*pcost = dist[root]; |
| 321 |
}else{ |
| 322 |
*pcost = -1; |
| 323 |
} |
| 324 |
|
| 325 |
} |
| 326 |
|
| 327 |
|
| 328 |
/*===========================================================================*/ |
| 329 |
|
| 330 |
/* this version is closer to that of HP (each hub candidate is lifted in |
| 331 |
and the best (the one which improves the lhs the most) is chosen. */ |
| 332 |
|
| 333 |
double lift_nonviolated_odd_hole(spp_cg_problem *spp, int oh_len, int *oh, |
| 334 |
double lhs_oh, int *phub_len, int *hubs, |
| 335 |
int *hub_coef) |
| 336 |
{ |
| 337 |
int nodenum = spp->fgraph->nodenum; |
| 338 |
fnode *nodes = spp->fgraph->nodes; |
| 339 |
char *node_node = spp->fgraph->node_node; |
| 340 |
int rhs = (oh_len - 1)/2; |
| 341 |
int hub_len = 0; |
| 342 |
int *num_nbrs = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 343 |
char *label = spp->tmp->ctmp_2nodenum; |
| 344 |
int *tmp_hubs = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 345 |
int *tmp_hub_coef = spp->tmp->itmp_8nodenum + 5 * nodenum; |
| 346 |
int i, j, k, start, hub, max_lhs, cnt, max_hub, tmp; |
| 347 |
double lhs_loh, max_val; |
| 348 |
|
| 349 |
lhs_loh = lhs_oh; |
| 350 |
/* pick out all the nodes that are adjacent to at least one node on the |
| 351 |
odd hole (these will be the hub candidates). |
| 352 |
add up rows of node-node corresponding to the nodes in oh, this |
| 353 |
will tell how many adjacent oh nodes each node in fgraph has. */ |
| 354 |
for (k = 0; k < nodenum; k++) |
| 355 |
num_nbrs[k] = 0; |
| 356 |
for (i = 0; i < oh_len; i++) { |
| 357 |
start = oh[i] * nodenum; |
| 358 |
for (k = 0; k < nodenum; k++) |
| 359 |
num_nbrs[k] += (int) node_node[start + k]; |
| 360 |
} |
| 361 |
for (i = 0; i < oh_len; i++) |
| 362 |
num_nbrs[oh[i]] = 0; /* oh nodes can't be hubs */ |
| 363 |
|
| 364 |
/* hub candidates are those with >= 1 num_nbrs value */ |
| 365 |
for (k = 0, hub_len = 0; k < nodenum; k++) |
| 366 |
if (num_nbrs[k]) |
| 367 |
hubs[hub_len++] = k; |
| 368 |
if (hub_len == 0) |
| 369 |
return(lhs_loh); |
| 370 |
/* order the hubs randomly, this will make sure that ties are broken |
| 371 |
more or less randomly when comparing which hubs improves the most */ |
| 372 |
for (i = hub_len-1; i > 0; i--) { |
| 373 |
j = (int) (floor((double)RANDOM()/MAXINT * (i+1))); |
| 374 |
tmp = hubs[i]; |
| 375 |
hubs[i] = hubs[j]; |
| 376 |
hubs[j] = tmp; |
| 377 |
} |
| 378 |
|
| 379 |
for (i = 0; i < spp->par->max_hub_num && i < hub_len; i++) { |
| 380 |
/* compute the lifting coefficient for each hub candidate. |
| 381 |
the first i-1 hubs are assumed to be already lifted */ |
| 382 |
for (j = i; j < hub_len; j++) { |
| 383 |
hub = hubs[j]; |
| 384 |
/* tmp_hubs and tmp_hub_coef will contain the indices and coefs |
| 385 |
of hubs (from 0 to i-1) not adjacent to the hub currently |
| 386 |
being lifted */ |
| 387 |
start = hub * nodenum; |
| 388 |
for (k = 0, cnt = 0; k < i; k++) |
| 389 |
if (!node_node[start + hubs[k]]) { |
| 390 |
tmp_hubs[cnt] = hubs[k]; |
| 391 |
tmp_hub_coef[cnt++] = hub_coef[k]; |
| 392 |
} |
| 393 |
/* compute max of lhs of the lifted oh assuming that hub is chosen */ |
| 394 |
for (k = 0; k < cnt; k++) |
| 395 |
label[k] = FALSE; |
| 396 |
max_lhs = |
| 397 |
max_lhs_of_lifted_odd_hole(spp, oh_len, oh, hub, cnt, tmp_hubs, |
| 398 |
tmp_hub_coef, label, 0); |
| 399 |
hub_coef[j] = rhs - max_lhs; |
| 400 |
} |
| 401 |
/* compute which hub candidate increases the lhs the most */ |
| 402 |
for (j = i, max_hub = -1, max_val = 0; j < hub_len; j++) { |
| 403 |
if (hub_coef[j] * nodes[hubs[j]].val > max_val) { |
| 404 |
max_hub = j; |
| 405 |
max_val = hub_coef[j] * nodes[hubs[j]].val; |
| 406 |
} |
| 407 |
} |
| 408 |
/* if max_val is 0 (all the hubs have coef 0), break out of loop */ |
| 409 |
if (max_val == 0) |
| 410 |
break; |
| 411 |
/* swap the best hub with the ith (also set hub_coef) */ |
| 412 |
tmp = hubs[i]; |
| 413 |
hubs[i] = hubs[max_hub]; |
| 414 |
hubs[max_hub] = tmp; |
| 415 |
hub_coef[i] = hub_coef[max_hub]; |
| 416 |
|
| 417 |
lhs_loh += max_val; |
| 418 |
} |
| 419 |
*phub_len = i; |
| 420 |
return(lhs_loh); |
| 421 |
} |
| 422 |
|
| 423 |
#if 0 |
| 424 |
/*===========================================================================*/ |
| 425 |
|
| 426 |
/* phub_len, hubs and hub_coef are OUT, *pcost_oh contains the cost of the |
| 427 |
oh as an input and the cost of the lifted oh as an output. |
| 428 |
cost of oh (lifted oh) is the value of the lhs in the current soln */ |
| 429 |
/* if lifted oh is not violated *pcost_oh is unchanged, and the OUT |
| 430 |
arguments contain junk */ |
| 431 |
|
| 432 |
double lift_nonviolated_odd_hole(spp_cg_problem *spp, int oh_len, int *oh, |
| 433 |
double lhs_oh, int *phub_len, int *hubs, |
| 434 |
int *hub_coef, double etol) |
| 435 |
{ |
| 436 |
int nodenum = spp->fgraph->nodenum; |
| 437 |
fnode *nodes = spp->fgraph->nodes; |
| 438 |
char *node_node = spp->fgraph->node_node; |
| 439 |
int rhs = (oh_len - 1)/2; |
| 440 |
int hub_len = 0; |
| 441 |
int *num_nbrs = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 442 |
char *label = spp->tmp->ctmp_2nodenum; |
| 443 |
int *tmp_hubs = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 444 |
int *tmp_hub_coef = spp->tmp->itmp_8nodenum + 5 * nodenum; |
| 445 |
int i, j, k, start, hub, max_lhs, cnt; |
| 446 |
double lhs_loh; |
| 447 |
|
| 448 |
/* choose a set of at most max_hub_num hub candidates (each must be |
| 449 |
adjacent to at least one node in the oh, so we add up rows of |
| 450 |
node-node corresponding to the nodes in oh to see how many adjacent |
| 451 |
oh nodes each node in fgraph has) */ |
| 452 |
for (k = 0; k < nodenum; k++) |
| 453 |
num_nbrs[k] = 0; |
| 454 |
for (i = 0; i < oh_len; i++) { |
| 455 |
start = oh[i] * nodenum; |
| 456 |
for (k = 0; k < nodenum; k++) |
| 457 |
num_nbrs[k] += (int) node_node[start + k]; |
| 458 |
} |
| 459 |
for (i = 0; i < oh_len; i++) |
| 460 |
num_nbrs[oh[i]] = 0; /* oh nodes can't be hubs */ |
| 461 |
|
| 462 |
/* hub candidates are those with >= 1 num_nbrs value, so order all the nodes |
| 463 |
in decr order of their num_nbrs values */ |
| 464 |
for (k = 0; k < nodenum; k++) |
| 465 |
hubs[k] = k; |
| 466 |
qsort_ii(num_nbrs, hubs, nodenum); |
| 467 |
spp_reverse_int_string(nodenum, num_nbrs); /* qsort orders into incr */ |
| 468 |
spp_reverse_int_string(nodenum, hubs); |
| 469 |
for (k = 0; k < nodenum && num_nbrs[k]; k++); /* k is pos of first 0 */ |
| 470 |
hub_len = MIN(spp->par->max_hub_num, k); |
| 471 |
|
| 472 |
/* alternative way of ordering the hubs: into decreasing order of their |
| 473 |
x values */ |
| 474 |
/* |
| 475 |
for (k = 0; k < nodenum; k++) { |
| 476 |
hubs[k] = k; |
| 477 |
if (num_nbrs[k]) { |
| 478 |
dtmp[k] = nodes[k].val; |
| 479 |
} else { |
| 480 |
dtmp[k] = -1; |
| 481 |
} |
| 482 |
} |
| 483 |
qsort_di(dtmp, hubs, nodenum); |
| 484 |
spp_reverse_double_string(nodenum, dtmp); |
| 485 |
spp_reverse_int_string(nodenum, hubs); |
| 486 |
for (k = 0; k < nodenum && dtmp[k] >= 0; k++); |
| 487 |
hub_len = MIN(spp->par->max_hub_num, k); |
| 488 |
*/ |
| 489 |
|
| 490 |
/* lift the hubs one by one */ |
| 491 |
for (i = 0; i < hub_len; i++) { |
| 492 |
|
| 493 |
hub = hubs[i]; |
| 494 |
/* tmp_hubs and tmp_hub_coef will contain the indices and coefs of |
| 495 |
hubs not adjacent to the hub currently being lifted */ |
| 496 |
start = hub * nodenum; |
| 497 |
for (j = 0, cnt = 0; j < i; j++) |
| 498 |
if (!node_node[start + hubs[j]]) { |
| 499 |
tmp_hubs[cnt] = hubs[j]; |
| 500 |
tmp_hub_coef[cnt++] = hub_coef[j]; |
| 501 |
} |
| 502 |
/* compute max of lhs of the lifted oh assuming that hub is chosen */ |
| 503 |
for (j = 0; j < cnt; j++) |
| 504 |
label[j] = FALSE; |
| 505 |
max_lhs = |
| 506 |
max_lhs_of_lifted_odd_hole(spp, oh_len, oh, hub, cnt, tmp_hubs, |
| 507 |
tmp_hub_coef, label, 0); |
| 508 |
if (max_lhs == rhs) { |
| 509 |
/* coef would be 0, delete this hub from the list */ |
| 510 |
for (j = i+1; j < hub_len; j++) |
| 511 |
hubs[j-1] = hubs[j]; |
| 512 |
hub_len--; |
| 513 |
i--; |
| 514 |
continue; |
| 515 |
} else { |
| 516 |
hub_coef[i] = rhs - max_lhs; |
| 517 |
} |
| 518 |
|
| 519 |
/* evaluate lhs and return if lifted oh is violated by the |
| 520 |
current solution (do this only if parameter is set) */ |
| 521 |
if (spp->par->eval_oh_during_lifting) { |
| 522 |
lhs_loh = lhs_oh; |
| 523 |
for (j = 0; j <= i; j++) |
| 524 |
lhs_loh += hub_coef[j] * nodes[hubs[j]].val; |
| 525 |
if (lhs_loh > rhs + etol) { |
| 526 |
*phub_len = i+1; |
| 527 |
return(lhs_loh); |
| 528 |
} |
| 529 |
} |
| 530 |
} |
| 531 |
|
| 532 |
/* evaluate lhs */ |
| 533 |
lhs_loh = lhs_oh; |
| 534 |
for (j = 0; j < hub_len; j++) |
| 535 |
lhs_loh += hub_coef[j] * nodes[hubs[j]].val; |
| 536 |
if (lhs_loh > rhs + spp->soln->lpetol) { |
| 537 |
*phub_len = hub_len; |
| 538 |
return(lhs_loh); |
| 539 |
} |
| 540 |
return(lhs_oh); |
| 541 |
} |
| 542 |
#endif |
| 543 |
|
| 544 |
/*===========================================================================*/ |
| 545 |
|
| 546 |
/* returns the max value of the lhs of the lifted odd hole provided that |
| 547 |
the hubs labeled by TRUE are set to 1. |
| 548 |
oh and hubs contain indices wrt fgraph |
| 549 |
label (T/F) indicates which hubs are at value 1 in the current solution |
| 550 |
pos position within hubs (and label), hubs up to position pos are |
| 551 |
permanently labeled. |
| 552 |
hub is the hub to be lifted, needs to be passed on since its neighbors |
| 553 |
on the odd hole need to be marked as well */ |
| 554 |
|
| 555 |
int max_lhs_of_lifted_odd_hole(spp_cg_problem *spp, int oh_len, int *oh, |
| 556 |
int hub, int hub_len, int *hubs, int *hub_coef, |
| 557 |
char *label, int pos) |
| 558 |
{ |
| 559 |
int nodenum = spp->fgraph->nodenum; |
| 560 |
fnode *nodes = spp->fgraph->nodes; |
| 561 |
char *node_node = spp->fgraph->node_node; |
| 562 |
int i, j, k, start, max_lhs, ret, *nbrs; |
| 563 |
int *oh_clone = spp->tmp->itmp_8nodenum + 6 * nodenum; |
| 564 |
int *perm = spp->tmp->itmp_8nodenum + 7 * nodenum; |
| 565 |
char *oh_label = spp->tmp->ctmp_2nodenum + nodenum; |
| 566 |
|
| 567 |
/* pos will contain the position of the first hub that is nonadjacent to |
| 568 |
all hubs already labeled TRUE */ |
| 569 |
for ( ; pos < hub_len; pos++) { |
| 570 |
start = hubs[pos] * nodenum; |
| 571 |
for (j = 0; j < pos; j++) |
| 572 |
if (label[j] && node_node[start + hubs[j]]) |
| 573 |
break; /* neighbor to an earlier... */ |
| 574 |
if (j == pos) |
| 575 |
break; /* no neighbor from 0 to pos-1 */ |
| 576 |
label[pos] = FALSE; |
| 577 |
} |
| 578 |
|
| 579 |
/* max_lhs is the largest possible lhs value provided that the hubs |
| 580 |
up to position pos are permanently labeled */ |
| 581 |
max_lhs = 0; |
| 582 |
|
| 583 |
/* if not all nodes are labeled, recurse by setting the last node labeled |
| 584 |
TRUE once to TRUE and once to FALSE; ow compute the maximal lhs value */ |
| 585 |
if (pos < hub_len) { |
| 586 |
label[pos] = TRUE; |
| 587 |
ret = max_lhs_of_lifted_odd_hole(spp, oh_len, oh, hub, hub_len, hubs, |
| 588 |
hub_coef, label, pos+1); |
| 589 |
max_lhs = MAX(max_lhs, ret); |
| 590 |
label[pos] = FALSE; |
| 591 |
ret = max_lhs_of_lifted_odd_hole(spp, oh_len, oh, hub, hub_len, hubs, |
| 592 |
hub_coef, label, pos+1); |
| 593 |
max_lhs = MAX(max_lhs, ret); |
| 594 |
|
| 595 |
} else { |
| 596 |
/* we introduce a labeling (oh_label) on oh that indicates which nodes |
| 597 |
are not neighbors to any of the hubs currently set to 1. |
| 598 |
first order the nodes in oh into increasing order of their indices |
| 599 |
so that scanning thru the neighbors of hubs will be easy. |
| 600 |
perm is an array that will contain the permutation (will need |
| 601 |
to permute back oh and oh_label) */ |
| 602 |
memcpy(oh_clone, oh, oh_len * ISIZE); |
| 603 |
for (i = 0; i < oh_len; i++) { |
| 604 |
oh_label[i] = TRUE; |
| 605 |
perm[i] = i; |
| 606 |
} |
| 607 |
qsort_ii(oh_clone, perm, oh_len); |
| 608 |
for (j = 0; j < hub_len; j++) |
| 609 |
if (label[j]) { |
| 610 |
/* need to set oh_label to FALSE for every index common in oh |
| 611 |
and the adjacency list of the jth hub */ |
| 612 |
nbrs = nodes[hubs[j]].nbrs; |
| 613 |
for (i = oh_len-1, k = nodes[hubs[j]].degree-1; i >= 0 && k >= 0; ) |
| 614 |
if (oh_clone[i] == nbrs[k]) { |
| 615 |
oh_label[i] = FALSE; |
| 616 |
i--; k--; |
| 617 |
} else if (oh_clone[i] < nbrs[k]) { |
| 618 |
k--; |
| 619 |
} else { |
| 620 |
i--; |
| 621 |
} |
| 622 |
} |
| 623 |
/* do the same for hub */ |
| 624 |
nbrs = nodes[hub].nbrs; |
| 625 |
for (i = oh_len-1, k = nodes[hub].degree-1; i >= 0 && k >= 0; ) |
| 626 |
if (oh_clone[i] == nbrs[k]) { |
| 627 |
oh_label[i] = FALSE; |
| 628 |
i--; k--; |
| 629 |
} else if (oh_clone[i] < nbrs[k]) { |
| 630 |
k--; |
| 631 |
} else { |
| 632 |
i--; |
| 633 |
} |
| 634 |
/* permute back oh_label */ |
| 635 |
qsort_ic(perm, oh_label, oh_len); |
| 636 |
|
| 637 |
/* now compute the max value of the lhs: coeffs of hubs at 1 + |
| 638 |
ceil(|S|/2) for each segment of the oh (segments: cont sequence |
| 639 |
of nodes that are not neigbors of any of the hubs at 1 (nodes |
| 640 |
marked TRUE in oh_label) */ |
| 641 |
for (j = 0; j < hub_len; j++) |
| 642 |
if (label[j]) |
| 643 |
max_lhs += hub_coef[j]; |
| 644 |
/* find first false (there must be at least one since all hubs are |
| 645 |
adjacent to some nodes in oh) */ |
| 646 |
for (i = 0; i < oh_len && oh_label[i]; i++); |
| 647 |
ret = i; /* save position of first FALSE */ |
| 648 |
while (i < oh_len) { |
| 649 |
/* find next FALSE */ |
| 650 |
for (k = i + 1; k < oh_len && oh_label[k]; k++); |
| 651 |
if (k == oh_len) { |
| 652 |
/* last segment is between last and first FALSE */ |
| 653 |
max_lhs += (ret + k - i) >> 1; |
| 654 |
break; |
| 655 |
} |
| 656 |
max_lhs += (k - i) >> 1; |
| 657 |
i = k; |
| 658 |
} |
| 659 |
} |
| 660 |
return(max_lhs); |
| 661 |
} |
| 662 |
|
| 663 |
|
| 664 |
/*****************************************************************************/ |
| 665 |
/*****************************************************************************/ |
| 666 |
/* ODD ANTIHOLES */ |
| 667 |
/*****************************************************************************/ |
| 668 |
/*****************************************************************************/ |
| 669 |
|
| 670 |
int find_violated_odd_antiholes(spp_cg_problem *spp, double etol) |
| 671 |
{ |
| 672 |
int nodenum = spp->cfgraph->nodenum; |
| 673 |
fnode *nodes = spp->cfgraph->nodes; |
| 674 |
char *node_node = spp->cfgraph->node_node; |
| 675 |
int *lnodes = spp->lgraph->lnodes; |
| 676 |
int *lbeg = spp->lgraph->lbeg; |
| 677 |
int *roots = spp->tmp->itmp_8nodenum; |
| 678 |
int *oah = spp->tmp->itmp_8nodenum + nodenum; |
| 679 |
int *hubs = spp->tmp->itmp_8nodenum + 2 * nodenum; |
| 680 |
int *hub_coef = spp->tmp->itmp_8nodenum + 3 * nodenum; |
| 681 |
int *itmp = spp->tmp->itmp_8nodenum + 7 * nodenum; |
| 682 |
double *dtmp = spp->tmp->dtmp_2nodenum; |
| 683 |
cut_data *new_cut = spp->tmp->cuttmp; |
| 684 |
int begl, endl, levelnum, *coef; |
| 685 |
int cnt, num_roots, random_num, tmp, oah_len, hub_len, numcuts = 0; |
| 686 |
int i, j, l, u, v, w; |
| 687 |
double lhs_oah, violation, *dcoef; |
| 688 |
|
| 689 |
/* collect the non-isolated nodes of cfgraph into roots */ |
| 690 |
for (i = 0, num_roots = 0; i < nodenum; i++) { |
| 691 |
if (nodes[i].degree) |
| 692 |
roots[num_roots++] = i; |
| 693 |
} |
| 694 |
if (num_roots == 0) |
| 695 |
return(numcuts); /* all nodes isolated */ |
| 696 |
/* order roots randomly: swap ith with one randomly chosen bw 0 and i */ |
| 697 |
for (i = num_roots-1; i > 0; i--) { |
| 698 |
random_num = (int) (floor((double)RANDOM()/MAXINT * (i+1))); |
| 699 |
tmp = roots[i]; |
| 700 |
roots[i] = roots[random_num]; |
| 701 |
roots[random_num] = tmp; |
| 702 |
} |
| 703 |
/* we will process only 20 to 50 percent of the possible roots, depending |
| 704 |
on the density of the graph. make this a parameter! */ |
| 705 |
num_roots = (int) (ceil((double)(.2 + .3 * spp->cfgraph->density)*num_roots)); |
| 706 |
|
| 707 |
for (i = 0; i < num_roots; i++) { |
| 708 |
v = roots[i]; |
| 709 |
/* construct level graph with root v and display it */ |
| 710 |
construct_level_graph(spp->cfgraph, v, spp->lgraph); |
| 711 |
/* display_level_graph(spp, spp->cfgraph); */ |
| 712 |
|
| 713 |
/* for each level >= 2 */ |
| 714 |
levelnum = spp->lgraph->levelnum; |
| 715 |
for (l = 2; l < levelnum; l++) { |
| 716 |
begl = lbeg[l]; endl = lbeg[l+1]; |
| 717 |
/* if there is at most one node on this level: continue */ |
| 718 |
if (endl - begl <= 1) |
| 719 |
continue; |
| 720 |
oah_len = 2 * l + 1; |
| 721 |
|
| 722 |
/* examine each pair of adjacent nodes on this level. |
| 723 |
note: u and w are indices wrt lgraph here, so lnodes[u] and |
| 724 |
lnodes[w] are the indices wrt fgraph! */ |
| 725 |
for (u = begl; u < endl - 1; u++) { |
| 726 |
for (w = u + 1; w < endl; w++) { |
| 727 |
/* if the nodes are adjacent try to find paths from u and w |
| 728 |
to the root (v) */ |
| 729 |
if (node_node[lnodes[u] * nodenum + lnodes[w]]) { |
| 730 |
lhs_oah = find_chordless_oh(spp, spp->cfgraph, |
| 731 |
lnodes[u], lnodes[w],oah); |
| 732 |
if (lhs_oah > -1) { |
| 733 |
/* display_level_graph(spp, spp->cfgraph); */ |
| 734 |
if (lhs_oah > 2 + etol) { |
| 735 |
/* odd antihole is violated: send back cut */ |
| 736 |
coef = (int *)(dtmp); |
| 737 |
for (j = 0; j < oah_len; j++) |
| 738 |
coef[j] = nodes[oah[j]].ind; |
| 739 |
rotate_odd_hole(oah_len, coef, itmp); |
| 740 |
memcpy(new_cut->coef, coef, oah_len * ISIZE); |
| 741 |
new_cut->type = ODD_ANTIHOLE; |
| 742 |
new_cut->size = oah_len * ISIZE; |
| 743 |
new_cut->rhs = 2; |
| 744 |
new_cut->range = 0; |
| 745 |
new_cut->sense = 'L'; |
| 746 |
violation = lhs_oah - 2; |
| 747 |
numcuts += |
| 748 |
register_and_send_cut(spp, new_cut, violation, etol); |
| 749 |
} else { |
| 750 |
/* odd antihole is not violated: try to lift */ |
| 751 |
/* display_level_graph(spp, spp->cfgraph); */ |
| 752 |
lhs_oah = |
| 753 |
lift_nonviolated_odd_antihole(spp, oah_len, oah, |
| 754 |
lhs_oah, &hub_len, |
| 755 |
hubs, hub_coef, etol); |
| 756 |
if (lhs_oah > 2 + etol) { |
| 757 |
/* lifted odd antihole is violated: send back cut */ |
| 758 |
coef = (int *)(dtmp); |
| 759 |
coef[0] = oah_len; |
| 760 |
coef[1] = hub_len; |
| 761 |
for (j = 0, cnt = 2; j < oah_len; j++) |
| 762 |
coef[cnt++] = nodes[oah[j]].ind; |
| 763 |
rotate_odd_hole(oah_len, coef + 2, itmp); |
| 764 |
for (j = 0; j < hub_len; j++) |
| 765 |
coef[cnt++] = nodes[hubs[j]].ind; |
| 766 |
memcpy(new_cut->coef, coef, cnt * ISIZE); |
| 767 |
dcoef = dtmp; |
| 768 |
for (j = 0; j < hub_len; j++) |
| 769 |
dcoef[j] = (double) hub_coef[j]; |
| 770 |
memcpy(new_cut->coef + cnt * ISIZE, dcoef, |
| 771 |
hub_len * DSIZE); |
| 772 |
new_cut->type = ODD_ANTIHOLE_LIFTED; |
| 773 |
new_cut->size = cnt * ISIZE + hub_len * DSIZE; |
| 774 |
new_cut->rhs = 2; |
| 775 |
new_cut->range = 0; |
| 776 |
new_cut->sense = 'L'; |
| 777 |
violation = lhs_oah - l; |
| 778 |
numcuts += |
| 779 |
register_and_send_cut(spp, new_cut, violation,etol); |
| 780 |
} |
| 781 |
/* undisplay_level_graph(spp); */ |
| 782 |
} |
| 783 |
/* undisplay_level_graph(spp); */ |
| 784 |
} |
| 785 |
} /* endif u, w adjacent */ |
| 786 |
} /* endfor w */ |
| 787 |
} /* endfor u */ |
| 788 |
} /* endfor l */ |
| 789 |
/* undisplay_level_graph(spp); */ |
| 790 |
} /* endfor i */ |
| 791 |
return(numcuts); |
| 792 |
} |
| 793 |
|
| 794 |
/*===========================================================================*/ |
| 795 |
|
| 796 |
double lift_nonviolated_odd_antihole(spp_cg_problem *spp, int oah_len, |
| 797 |
int *oah, double lhs_oah, int *phub_len, |
| 798 |
int *hubs, int *hub_coef, double etol) |
| 799 |
{ |
| 800 |
int nodenum = spp->fgraph->nodenum; |
| 801 |
fnode *nodes = spp->fgraph->nodes; |
| 802 |
char *node_node = spp->fgraph->node_node; |
| 803 |
int hub_len = 0; |
| 804 |
int *num_nbrs = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 805 |
int *tmp_nbrs = spp->tmp->itmp_8nodenum + 4 * nodenum; |
| 806 |
int i, j, k, l, tmp, max_hub, start, hub, cnt; |
| 807 |
double lhs_loah, max_val; |
| 808 |
|
| 809 |
lhs_loah = lhs_oah; |
| 810 |
/* pick out all the nodes that are adjacent to at least one node on the |
| 811 |
odd antihole (these will be the hub candidates). |
| 812 |
add up rows of node-node corresponding to the nodes in oah, this |
| 813 |
will tell how many adjacent oah nodes each node in fgraph has. */ |
| 814 |
for (k = 0; k < nodenum; k++) |
| 815 |
num_nbrs[k] = 0; |
| 816 |
for (i = 0; i < oah_len; i++) { |
| 817 |
start = oah[i] * nodenum; |
| 818 |
for (k = 0; k < nodenum; k++) |
| 819 |
num_nbrs[k] += (int) node_node[start + k]; |
| 820 |
} |
| 821 |
for (i = 0; i < oah_len; i++) |
| 822 |
num_nbrs[oah[i]] = 0; /* oah nodes can't be hubs */ |
| 823 |
|
| 824 |
/* hub candidates are those with >= (oah_len+1)/2 num_nbrs value */ |
| 825 |
tmp = (oah_len + 1) / 2; |
| 826 |
for (k = 0, hub_len = 0; k < nodenum; k++) |
| 827 |
if (num_nbrs[k] >= tmp) |
| 828 |
hubs[hub_len++] = k; |
| 829 |
if (hub_len == 0) |
| 830 |
return(lhs_loah); |
| 831 |
/* order the hubs randomly, this will make sure that ties are broken |
| 832 |
more or less randomly when comparing which hubs improves the most */ |
| 833 |
for (i = hub_len-1; i > 0; i--) { |
| 834 |
j = (int) (floor((double)RANDOM()/MAXINT * (i+1))); |
| 835 |
tmp = hubs[i]; |
| 836 |
hubs[i] = hubs[j]; |
| 837 |
hubs[j] = tmp; |
| 838 |
} |
| 839 |
|
| 840 |
for (i = 0; i < spp->par->max_hub_num && i < hub_len; i++) { |
| 841 |
/* compute the lifting coefficient for each hub candidate, the first |
| 842 |
i-1 hubs are assumed to be already lifted. */ |
| 843 |
for (j = i; j < hub_len; j++) { |
| 844 |
hub = hubs[j]; |
| 845 |
/* tmp_nbrs will contain the indices of oah nodes and already lifted |
| 846 |
hubs (from 0 to i-1) not adjacent to hub */ |
| 847 |
start = hub * nodenum; |
| 848 |
for (k = 0, cnt = 0; k < oah_len; k++) |
| 849 |
if (!node_node[start + oah[k]]) |
| 850 |
tmp_nbrs[cnt++] = oah[k]; |
| 851 |
for (k = 0; k < i; k++) |
| 852 |
if (!node_node[start + hubs[k]]) |
| 853 |
tmp_nbrs[cnt++] = hubs[k]; |
| 854 |
/* if there are no such indices: the coeff of the currently lifted |
| 855 |
hub is 2 (since the max of the lhs is 0) */ |
| 856 |
if (cnt == 0) { |
| 857 |
hub_coef[j] = 2; |
| 858 |
continue; |
| 859 |
} |
| 860 |
/* hub cannot be adjacent to an already lifted hub with coeff 2 */ |
| 861 |
/* if any two nodes in the list are not adjacent, they can be |
| 862 |
both chosen, so hub's coeff is 0; ow hub's coeff is 1 */ |
| 863 |
hub_coef[j] = 1; |
| 864 |
for (k = cnt - 1; k >= 1; k--) { |
| 865 |
start = tmp_nbrs[k] * nodenum; |
| 866 |
for (l = k - 1; l >= 0; l--) |
| 867 |
if (!node_node[start + tmp_nbrs[l]]) { |
| 868 |
hub_coef[j] = 0; |
| 869 |
break; |
| 870 |
} |
| 871 |
if (l >= 0) |
| 872 |
break; |
| 873 |
} |
| 874 |
} /* endfor j */ |
| 875 |
|
| 876 |
/* compute which hub candidate increases the lhs the most */ |
| 877 |
for (j = i, max_hub = -1, max_val = 0; j < hub_len; j++) { |
| 878 |
if (hub_coef[j] * nodes[hubs[j]].val > max_val) { |
| 879 |
max_hub = j; |
| 880 |
max_val = hub_coef[j] * nodes[hubs[j]].val; |
| 881 |
} |
| 882 |
} |
| 883 |
/* if max_val is 0 (all the hubs have coef 0), break out of loop */ |
| 884 |
if (max_val == 0) |
| 885 |
break; |
| 886 |
/* swap the best hub with the ith */ |
| 887 |
tmp = hubs[i]; |
| 888 |
hubs[i] = hubs[max_hub]; |
| 889 |
hubs[max_hub] = tmp; |
| 890 |
tmp = hub_coef[i]; |
| 891 |
hub_coef[i] = hub_coef[max_hub]; |
| 892 |
hub_coef[max_hub] = tmp; |
| 893 |
|
| 894 |
lhs_loah += max_val; |
| 895 |
|
| 896 |
/* if coef of chosen hub is 2, set the coefs of its neighbors to 0 */ |
| 897 |
if (hub_coef[i] == 2) { |
| 898 |
start = hubs[i] * nodenum; |
| 899 |
for (j = i+1; j < hub_len; j++) |
| 900 |
if (node_node[start + hubs[j]]) |
| 901 |
hub_coef[j] = 0; |
| 902 |
} |
| 903 |
/* hub candidates with hub_coef 0 will never have a positive coef, |
| 904 |
so shuffle them into the end of the sequence and decrease hub_len |
| 905 |
accordingly (k is where the next non0 can be written) */ |
| 906 |
for (j = k = i+1; j < hub_len; j++) |
| 907 |
if (hub_coef[j] != 0) |
| 908 |
hubs[k++] = hubs[j]; |
| 909 |
hub_len = k; |
| 910 |
} /* endfor i */ |
| 911 |
*phub_len = i; |
| 912 |
return(lhs_loah); |
| 913 |
} |
| 914 |
|