Debian Codegraph @

SYMPHONY/Applications/SPP+CUTS/src/CutGen/spp_cg_functions.c

raw
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