Debian Codegraph @

SYMPHONY/Applications/SPP+CUTS/src/CutGen/spp_cg_clique.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_macros.h"
24 #include "sym_constants.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_clique.h"
35
36 /*****************************************************************************/
37 /* global variables */
38 /* (defined so that the recursive fn has few arguments => faster) */
39 /*****************************************************************************/
40
41 static cut_data *new_cut; /* tmp, stores a cut to be sent to the lp */
42 static int perm_length; /* see desc at enumerate_maximal_cliques */
43 static int *perm_indices;
44 static int length;
45 static int *indices;
46 static char *label;
47
48 static int del_length; /* already deleted nodes in star cl method */
49 static int *del_indices;
50
51 /*****************************************************************************/
52 /*****************************************************************************/
53 /* STAR CLIQUES */
54 /*****************************************************************************/
55 /*****************************************************************************/
56 /*===========================================================================*
57 * tmp arrays used
58 * find_violated_star_cliques:
59 * current_indices: itmp_8nodenum
60 * current_props : dtmp_2nodenum + nodenum
61 * star : ... + 2 * nodenum
62 * star_deg : ... + 3 * nodenum
63 * del_indices : ... + 4 * nodenum
64 * label : ctmp_2nodenum
65 * new_cut : cuttmp
66 * -> spp_delete_node: no tmp
67 * -> enumerate_maximal_cliques:
68 * coef : itmp_8nodenum + 7 * nodenum
69 * -> register_and_send_cut:
70 * indices: itmp_8nodenum + 7 * nodenum
71 * coefs : dtmp_2nodenum
72 * -> extend_clique_on_fgraph:
73 * indices: itmp_8nodenum + 7 * nodenum
74 * -> greedy_maximal_clique: no tmp
75 * -> register_and_send_cut
76 *===========================================================================*/
77
78 /*===========================================================================*
79 * Find violated star cliques, a la Hoffman-Padberg.
80 *
81 * Algorithm: Take min degree node. Check for violated cuts in the subgraph
82 * consisting of this node and its neighbors (the "star" of this node).
83 * Violated cuts are sent back to the LP and are lifted there. Then delete
84 * the node and continue with the now min degree node.
85 *
86 * Implementation: Two arrays are defined, one contains the indices the other
87 * the degrees of all the nodes still in the graph. If the min degree is 0
88 * or 1 then the min degree node can be deleted at once.
89 * All cliques are enumerated in v U star(v) if the min degree is smaller
90 * than the threshold par->starcl_degree_threshold, otherwise attemp to
91 * find maximal clique greedily.
92 *
93 * Note: Indices in current_indices are always kept in increasing order.
94 *===========================================================================*/
95
96 int find_violated_star_cliques(spp_cg_problem *spp, double etol)
97 {
98 int nodenum = spp->fgraph->nodenum;
99 fnode *nodes = spp->fgraph->nodes;
100 char *node_node = spp->fgraph->node_node;
101
102 int current_nodenum, v_deg, start;
103 int *current_indices = spp->tmp->itmp_8nodenum;
104 int *current_degrees = spp->tmp->itmp_8nodenum + nodenum;
105 double *current_values = spp->tmp->dtmp_2nodenum + nodenum;
106 int v, best_ind, other_node;
107 double v_val, star_val;
108
109 int star_length;
110 int *star = spp->tmp->itmp_8nodenum + 2 * nodenum;
111 int *star_deg = spp->tmp->itmp_8nodenum + 3 * nodenum;
112
113 int i, tmp, cnt1 = 0, cnt2 = 0, cnt3 = 0;
114 int clique_cnt_e = 0, clique_cnt_g = 0, clique_cnt;
115 int largest_star_size = 0;
116
117 /* initialize global variables */
118 new_cut = spp->tmp->cuttmp;
119 perm_length = 1; /* always the node whose star we're evaluating */
120 del_length = 0;
121 del_indices = spp->tmp->itmp_8nodenum + 4 * nodenum;
122 label = spp->tmp->ctmp_2nodenum;
123
124 /* initialize current_nodes, current_degrees and current_values */
125 current_nodenum = nodenum;
126 for (i = 0; i < nodenum; i++) {
127 current_indices[i] = i;
128 current_degrees[i] = nodes[i].degree;
129 current_values[i] = nodes[i].val;
130 }
131
132 /* find first node to be checked */
133 best_ind = choose_next_node(spp, current_nodenum, current_indices,
134 current_degrees, current_values);
135 v = current_indices[best_ind];
136 v_deg = current_degrees[best_ind];
137 v_val = current_values[best_ind];
138
139 /* while there are nodes left in the graph ... (more precisely, while
140 there are at least 3 nodes in the graph) */
141 while (current_nodenum > 2) {
142
143 /* if the best node is of degree < 2 then it can be deleted */
144 if (v_deg < 2) {
145 del_indices[del_length++] = v;
146 spp_delete_node(spp, best_ind, &current_nodenum, current_indices,
147 current_degrees, current_values);
148 best_ind = choose_next_node(spp, current_nodenum, current_indices,
149 current_degrees, current_values);
150 v = current_indices[best_ind];
151 v_deg = current_degrees[best_ind];
152 v_val = current_values[best_ind];
153 largest_star_size = MAX(largest_star_size, v_deg);
154 continue;
155 }
156
157 /* star will contain the indices of v's neighbors (but not v's index) */
158 start = nodenum * v;
159 star++;
160 star_deg++;
161 star_val = v_val;
162 for (i = 0, star_length = 0; i < current_nodenum; i++) {
163 other_node = current_indices[i];
164 if (node_node[start + other_node]) {
165 star[star_length] = other_node;
166 star_deg[star_length++] = current_degrees[i];
167 star_val += current_values[i];
168 }
169 }
170
171 /* quick check: if sum of values for the star does not exceed 1 then
172 there won't be a violated clique in the star */
173 if (star_val >= 1 + etol) {
174 /* find maximal violated cliques in star. cliques found here might not
175 be maximal wrt to entire fractional graph, only for the current
176 subset of it (some nodes might be already deleted...) */
177 if (v_deg < spp->par->starcl_degree_threshold) {
178 /* enumerate if v_deg is small enough */
179 for (i = 0; i < star_length; i++)
180 label[i] = FALSE;
181 length = star_length; /* set global vars */
182 indices = star;
183 perm_indices = &v;
184 clique_cnt_e += enumerate_maximal_cliques(spp, 0, etol);
185 star--;
186 star_deg--;
187 cnt1++;
188 } else {
189 /* greedily find if v_deg is too big */
190 /* order nodes in *decreasing* order of their degrees in star */
191 qsort_ii(star_deg, star, star_length);
192 for (i = star_length / 2 - 1; i >= 0; i--) {
193 tmp = star[i];
194 star[i] = star[star_length - i - 1];
195 star[star_length - i - 1] = tmp;
196 }
197 /* put v to the beginning of star */
198 star--;
199 star_deg--;
200 star[0] = v;
201 star_deg[0] = v_deg;
202 star_length++;
203 /* find maxl clique greedily, including v */
204 clique_cnt_g += greedy_maximal_clique(spp, new_cut, star_length,
205 star, 1, etol);
206 cnt2++;
207 }
208 } else {
209 cnt3++;
210 }
211 /* delete v from current_indices */
212 del_indices[del_length++] = v;
213 spp_delete_node(spp, best_ind, &current_nodenum, current_indices,
214 current_degrees, current_values);
215 best_ind = choose_next_node(spp, current_nodenum, current_indices,
216 current_degrees, current_values);
217 v = current_indices[best_ind];
218 v_deg = current_degrees[best_ind];
219 v_val = current_values[best_ind];
220 largest_star_size = MAX(largest_star_size, v_deg);
221 }
222
223 clique_cnt = clique_cnt_e + clique_cnt_g;
224 printf("\nFound %i new violated cliques with the star-clique method\n",
225 clique_cnt);
226 printf("The largest star size was %i (threshold %i)\n",
227 largest_star_size, spp->par->starcl_degree_threshold);
228 printf("Enumeration %i times, found %i maxl cliques\n", cnt1, clique_cnt_e);
229 printf("Greedy %i times, found %i maxl cliques\n", cnt2, clique_cnt_g);
230 printf("Skipped a star b/c of small solution value %i times\n", cnt3);
231
232 if (cnt2 == 0)
233 printf(" all cliques have been enumerated\n");
234 else
235 printf(" not all cliques have been eliminated\n");
236
237 return(clique_cnt);
238 }
239
240 /*===========================================================================*/
241
242 /*===========================================================================*
243 * Delete the node of index del_ind (this index is wrt current_indices) from
244 * the list current_indices (current_degrees and current_values) and based on
245 * the graph stored in spp->fgraph decrease the degrees of its neighbors.
246 *
247 * There are at least 3 nodes in the graph when this function is invoked.
248 *
249 * Note that the node indices in current_indices are in increasing order,
250 * and that thins ordering is maintained here.
251 *
252 * spp: IN, general data structure, contains fgraph.
253 * del_ind: IN, the index of the node to be deleted (wrt to current_indices)
254 * pcurrent_nodenum: INOUT, pointer to the current number of nodes
255 * current_indices: INOUT, array of current node indices
256 * current_degrees: INOUT, array of current node degrees, in the dame order
257 * as in current_indices
258 * current_values: INOUT, array of solution values
259 *===========================================================================*/
260
261 void spp_delete_node(spp_cg_problem *spp, int del_ind, int *pcurrent_nodenum,
262 int *current_indices, int *current_degrees,
263 double *current_values)
264 {
265 char *node_node = spp->fgraph->node_node;
266 int current_nodenum = *pcurrent_nodenum;
267
268 int i, start, v;
269 v = current_indices[del_ind];
270
271 /* delete the entry corresponding to del_ind from current_indices,
272 current_degrees and current_values */
273 i = del_ind;
274 memmove((char *)(current_indices+i), (char *)(current_indices+i+1),
275 (current_nodenum-i-1) * ISIZE);
276 memmove((char *)(current_degrees+i), (char *)(current_degrees+i+1),
277 (current_nodenum-i-1) * ISIZE);
278 memmove((char *)(current_values+i), (char *)(current_values+i+1),
279 (current_nodenum-i-1) * ISIZE);
280 current_nodenum--;
281
282 /* decrease the degrees of v's neighbors by 1 */
283 start = spp->fgraph->nodenum * v;
284 for (i = 0; i < current_nodenum; i++)
285 if (node_node[start + current_indices[i]])
286 current_degrees[i]--;
287
288 *pcurrent_nodenum = current_nodenum;
289 }
290
291 /* returns the index of the "best" node wrt current_indices, etc. */
292 int choose_next_node(spp_cg_problem *spp, int current_nodenum,
293 int *current_indices, int *current_degrees,
294 double *current_values)
295 {
296 int best, i, best_deg;
297 double best_val;
298
299 best = 0;
300 best_deg = current_degrees[0];
301 best_val = current_values[0];
302
303 switch (spp->par->starcl_which_node) {
304
305 case MIN_DEGREE:
306 for (i = 0; i < current_nodenum; i++)
307 if (current_degrees[i] < best_deg) {
308 best = i;
309 best_deg = current_degrees[i];
310 }
311 break;
312
313 case MAX_DEGREE:
314 for (i = 0; i < current_nodenum; i++)
315 if (current_degrees[i] > best_deg) {
316 best = i;
317 best_deg = current_degrees[i];
318 }
319 break;
320
321 case MAX_XJ_MAX_DEG:
322 for (i = 0; i < current_nodenum; i++) {
323 if (current_values[i] > best_val) {
324 best = i;
325 best_val = current_values[i];
326 best_deg = current_degrees[i];
327 } else if (current_values[i] == best_val &&
328 current_degrees[i] > best_deg) {
329 best = i;
330 best_deg = current_degrees[i];
331 }
332 }
333 break;
334
335 default:
336 printf("ERROR: bad starcl_which_node (in choose_next_node\n");
337 break;
338 }
339
340 return(best);
341
342 }
343
344
345 /*****************************************************************************/
346 /*****************************************************************************/
347 /* ROW CLIQUES */
348 /*****************************************************************************/
349 /*****************************************************************************/
350 /*===========================================================================*
351 * tmp arrays used
352 * find_violated_row_cliques:
353 * indices : itmp_8nodenum
354 * degrees : ... + nodenum
355 * itmp : ... + 2 * nodenum
356 * ctmp : ctmp_2nodenum
357 * new_cut : cuttmp
358 * -> enumerate_maximal_cliques:
359 * coef : itmp_8nodenum + 7 * nodenum
360 * -> register_and_send_cut:
361 * indices: itmp_8nodenum + 7 * nodenum
362 * coefs : dtmp_2nodenum
363 * -> extend_clique_on_fgraph:
364 * indices: itmp_8nodenum + 7 * nodenum
365 * -> greedy_maximal_clique: no tmp
366 * -> register_and_send_cut
367 *===========================================================================*/
368
369 int find_violated_row_cliques(spp_cg_problem *spp, double etol)
370 {
371 char *node_node = spp->fgraph->node_node;
372 fnode *nodes = spp->fgraph->nodes;
373 int nodenum = spp->fgraph->nodenum;
374 int *rmatbeg = spp->rm_frac->rmatbeg;
375 int *rmatind = spp->rm_frac->rmatind;
376 int rownum = spp->rm_frac->rownum;
377 int *itmp = spp->tmp->itmp_8nodenum + 2 * nodenum;
378 int *degrees = spp->tmp->itmp_8nodenum + nodenum;
379 char *ctmp = spp->tmp->ctmp_2nodenum;
380 int i, j, k, pos, len, clique_count;
381 int col;
382 int *row; /* pointer to the row in rmatind */
383 int largest_length; /* length of indices */
384
385 /* initialize global variables */
386 new_cut = spp->tmp->cuttmp;
387 del_length = 0;
388 del_indices = NULL;
389 length = 0;
390 indices = spp->tmp->itmp_8nodenum; /* nodes that extend the rowcl */
391
392 /* for each row of the matrix */
393 clique_count = 0; largest_length = 0;
394 for (j = 0; j < rownum; j++) {
395
396 /* if the row is of zero length, take the next row */
397 len = rmatbeg[j+1] - rmatbeg[j];
398 if (!len)
399 continue;
400
401 row = rmatind + rmatbeg[j];
402
403 /* copy the row of node_node corresponding to the first column in 'row'
404 into ctmp, and take the AND of this vector with every row of
405 node_node corresponding to the rest of the columns in 'row' to
406 determine those columns that are non-orthog to every column in row */
407 memcpy(ctmp, &node_node[row[0] * nodenum], nodenum * CSIZE);
408 for (i = 1; i < len; i++) {
409 col = row[i];
410 pos = col * nodenum; /* starting position of this col in node_node */
411 for (k = 0; k < nodenum; k++)
412 ctmp[k] = ctmp[k] * node_node[pos + k];
413 }
414 for (k = 0, length = 0; k < nodenum; k++)
415 if (ctmp[k])
416 indices[length++] = k;
417 largest_length = MAX(length, largest_length);
418
419 /* if there is anything in indices, enumerate (or greedily find)
420 maximal cliques */
421 if (length) {
422 if (length < spp->par->rowcl_degree_threshold) {
423 for (i = 0; i < length; i++)
424 ctmp[i] = FALSE; /* reuse ctmp as label */
425 perm_length = len; /* global vars */
426 perm_indices = row;
427 label = ctmp;
428 clique_count += enumerate_maximal_cliques(spp, 0, etol);
429 } else {
430 /* order indices into decreasing order of their degrees and
431 copy first 'row' then 'indices' into itmp */
432 for (i = 0; i < length; i++)
433 degrees[i] = - nodes[indices[i]].degree;
434 qsort_ii(degrees, indices, length);
435 for (i = 0; i < len; i++) itmp[i] = row[i];
436 for (i = 0, k = len; i < length; i++) itmp[k++] = indices[i];
437 clique_count += greedy_maximal_clique(spp, new_cut, k, itmp, len,
438 etol);
439 }
440 }
441 }
442
443 printf("\nFound %i new violated cliques with the row-clique method\n",
444 clique_count);
445 printf("The largest admissible number was %i (threshold %i)\n",
446 largest_length, spp->par->rowcl_degree_threshold);
447 if (largest_length < spp->par->rowcl_degree_threshold)
448 printf(" all row cliques have been enumerated\n");
449 else
450 printf(" not all row cliques have been eliminated\n");
451
452 return(clique_count);
453 }
454
455 /*****************************************************************************/
456 /*****************************************************************************/
457 /* these routines are used both for both clique finding method */
458 /*****************************************************************************/
459 /*****************************************************************************/
460 /*===========================================================================*
461 * Enumerate all maximal cliques on the nodes in indices. Maximal cliques
462 * that are violated are sent to the lp. Returns the number of maximal
463 * violated cliques found. The algorithm is recursive.
464 *
465 * spp: IN, contains the graph (fgraph)
466 * new_cut: TMP, packed together when a violated cut is found
467 * perm_length: IN, the length of perm_indices
468 * perm_indices: IN, indices of nodes that MUST be in the clique, these
469 * nodes are supposed to be connected to all nodes in
470 * indices
471 * length: IN, length of indices and label
472 * indices: IN, indices of nodes on which maximal cliques are sought
473 * label: INOUT, indicates which nodes are in the clique at the moment (T/F)
474 * pos: INOUT, position within indices (and label), nodes up to position
475 * pos in indices are permanently labeled (backtrack cannot
476 * change labels)
477 *===========================================================================*/
478
479 int enumerate_maximal_cliques(spp_cg_problem *spp, int pos, double etol)
480 {
481 fnode *nodes = spp->fgraph->nodes;
482 int nodenum = spp->fgraph->nodenum;
483 char *node_node = spp->fgraph->node_node;
484
485 int i, j, k, start, cnt, found;
486 int *coef;
487 double lhs, violation;
488
489 /* starting from position pos, find the first node in indices that
490 can be added to the clique, and label it with TRUE */
491 while (pos < length) {
492 label[pos] = TRUE;
493 start = indices[pos] * nodenum;
494 for (j = 0; j < pos; j++)
495 if (label[j] && ! node_node[start + indices[j]]) {
496 label[pos] = FALSE;
497 break;
498 }
499 if (label[pos++] == TRUE)
500 break;
501 }
502
503 /* found counts the number of maximal violated cliques that have been sent
504 to the lp under the current level of recursion */
505 found = 0;
506
507 /* if not all nodes are labeled: recurse by setting the last node
508 labeled TRUE once to TRUE and once to FALSE;
509 otherwise check whether the clique found is maximal and violated */
510 if (pos < length) {
511 found += enumerate_maximal_cliques(spp, pos, etol);
512 label[pos-1] = FALSE;
513 found += enumerate_maximal_cliques(spp, pos, etol);
514 } else {
515 /* check if the clique can be extended on indices */
516
517 /* copy indices of the clique into coef (not user inds, coef is a tmp) */
518 coef = spp->tmp->itmp_8nodenum + 7 * nodenum;
519 for (j = length - 1, cnt = 0; j >= 0; j--)
520 if (label[j])
521 coef[cnt++] = indices[j];
522 if (!cnt)
523 return(found);
524
525 /* check if the clique can be extended on indices */
526 for (k = length - 1; k >= 0; k--) {
527 if (!label[k]) {
528 start = indices[k] * nodenum;
529 for (i = cnt - 1; i >= 0; i--)
530 if (!node_node[start + coef[i]])
531 break;
532 /* if k can be added to the clique, return */
533 if (i < 0)
534 return(found);
535 }
536 }
537
538 /* now the clique is maximal on indices.
539 fill relative indices into coef */
540 for (j = 0; j < perm_length; j++)
541 coef[cnt++] = perm_indices[j];
542
543 /* check if clique is violated */
544 for (j = 0, lhs = 0; j < cnt; j++)
545 lhs += nodes[coef[j]].val;
546 if (lhs < 1 + etol)
547 return(found);
548
549 /* if clique can be extended on del_indices then it can be
550 discarded */
551 for (i = 0; i < del_length; i++) {
552 start = del_indices[i] * nodenum;
553 for (j = cnt - 1; j >= 0; j--)
554 if (!node_node[start + coef[j]])
555 break;
556 /* if del_indices[i] can be added to the clique, return */
557 if (j < 0)
558 return(found);
559 }
560 /* transform relative indices into user indices and order them */
561 for (j = cnt - 1; j >= 0; j--)
562 coef[j] = nodes[coef[j]].ind;
563 qsort_i(coef, cnt);
564 memcpy(new_cut->coef, coef, cnt * ISIZE);
565 new_cut->type = CLIQUE;
566 new_cut->size = cnt * ISIZE;
567 new_cut->rhs = 1;
568 new_cut->range = 0;
569 new_cut->sense = 'L';
570
571 violation = lhs - 1;
572
573 found += register_and_send_cut(spp, new_cut, violation, etol);
574 }
575 return(found);
576 }
577
578 /*===========================================================================*/
579
580 /*===========================================================================*
581 * Find a violated clique greedily in the given array of indices, starting
582 * from pos. Return the number of violated cliques found (1 or 0).
583 * If a violated clique is found it is sent to the LP via the function
584 * register_and_send_cut.
585 * This routine overwrites the array indices: those variables in the
586 * clique will be shuffled to the beginning of the array (after pos).
587 *===========================================================================*/
588
589 int greedy_maximal_clique(spp_cg_problem *spp, cut_data *new_cut,
590 int length, int *indices, int pos, double etol)
591 {
592 fnode *nodes = spp->fgraph->nodes;
593 int nodenum = spp->fgraph->nodenum;
594 char *node_node = spp->fgraph->node_node;
595 int i, j, var, num, start;
596 char is_violated;
597 double lhs, violation;
598
599 for (j = pos, num = pos; j < length; j++) {
600 var = indices[j];
601 start = var * nodenum; /* start of row corresp to var in node_node */
602 for (i = num-1; i >= 0; i--)
603 if (!node_node[start + indices[i]])
604 break;
605 if (i < 0)
606 indices[num++] = var;
607 }
608
609 /* now the first num entries in indices contain the clique */
610 /* only cliques of size at least 3 are interesting */
611 if (num < 3)
612 return(0);
613
614 /* compute lhs */
615 for (j = 0, lhs = 0; j < num; j++)
616 lhs += nodes[indices[j]].val;
617
618 is_violated = (lhs > 1 + etol) ? TRUE: FALSE;
619
620 if (is_violated) {
621 for (j = 0; j < num; j++)
622 indices[j] = nodes[indices[j]].ind;
623 qsort_i(indices, num);
624 memcpy(new_cut->coef, (char *)indices, num * ISIZE);
625 new_cut->type = CLIQUE;
626 new_cut->size = num * ISIZE;
627 new_cut->rhs = 1;
628 new_cut->range = 0;
629 new_cut->sense = 'L';
630 violation = lhs - 1;
631
632 j = register_and_send_cut(spp, new_cut, violation, etol);
633 return(j);
634 }
635
636 return(0);
637 }