1 /***************************************************************************/
2 /* */
3 /* STORING AND SEARCHING THE CUTPOOL */
4 /* */
5 /* TSP CODE */
6 /* */
7 /* */
8 /* Written by: Applegate, Bixby, Chvatal, and Cook */
9 /* Date: March 19, 1997 */
10 /* May 27, 1997 (bico) */
11 /* */
12 /* EXPORTED FUNCTIONS: */
13 /* int CCtsp_init_cutpool (int ncount, char *poolfilename, */
14 /* CCtsp_lpcuts **pool) */
15 /* -ncount is the number of nodes in the problem */
16 /* -poolfilename is a file containing an cutpool (it can be NULL) */
17 /* -CCtsp_lpcuts will return the pool */
18 /* */
19 /* int CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, */
20 /* CCtsp_lpclique **cliques, int *cliquecount, int ncount, */
21 /* int ecount, int *elist, double *x, double maxdelta, */
22 /* int maxcliques, double **cliquevals) */
23 /* RETURNS an array of cliques having x(delta(C)) < maxdelta */
24 /* -pool points to a cutpool (or cuts of an lp) */
25 /* -cliques will return the array of cliques */
26 /* -cliquecount with return the length of the array */
27 /* -ncount is the number of nodes in the problem */
28 /* -ecount is the number of edges in elist */
29 /* -elist is a list of edges in end end format */
30 /* -x is an ecount-long array of weights */
31 /* -maxdelta is a bound on x(delta(C)) */
32 /* -maxcliques is an upperbound on the number of cliques that should */
33 /* be returned */
34 /* -cliquevals will return the values of x(delta(C)) for the cliques */
35 /* (this parameter can be NULL) */
36 /* */
37 /* void CCtsp_free_cutpool (CCtsp_lpcuts **pool) */
38 /* FREES the pool of cuts. */
39 /* */
40 /* int CCtsp_write_cutpool (int ncount, char *poolfilename, */
41 /* CCtsp_lpcuts *pool) */
42 /* WRITES pool to poolfilename. */
43 /* */
44 /* int CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, */
45 /* CCtsp_lpclique **cliques, int *cliquecount, int ncount, */
46 /* int ecount, int *elist, double *x, int nwant, */
47 /* double **cliquevals) */
48 /* RETURNS an array of cliques having x(delta(C)) as close to 3.0 as */
49 /* possible. */
50 /* -the parmeters are like those used by search_cutpool_cliques, */
51 /* where nwant is the number of cliques we would like to have in */
52 /* the array. */
53 /* */
54 /* int CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount, */
55 /* int *elist, double *x, double *cutval) */
56 /* COMPUTES the slack on each cut in the pool */
57 /* -ecount, elist, and x give an x-vector */
58 /* -cutval returns the array of slack values (it should be passed in */
59 /* as an array of length at least pool->cutcount) */
60 /* */
61 /* NOTES: */
62 /* This version does not use the compressed set references. Notes */
63 /* on the representation are given in "Chapter 4: The Linear */
64 /* Programming Problems". */
65 /* */
66 /***************************************************************************/
67
68 #include "machdefs.h"
69 #include "util.h"
70 #include "macrorus.h"
71 #include "tsp.h"
72
73 #define ZERO_EPSILON 0.0000000001
74 #define POOL_MAXCUTS 500
75 #define POOL_MINVIOL 0.001
76
77 typedef struct pooledge {
78 double x;
79 int to;
80 } pooledge;
81
82 typedef struct poolnode {
83 struct pooledge *adj;
84 int mark;
85 int deg;
86 } poolnode;
87
88 #ifdef CC_PROTOTYPE_ANSI
89
90 static int
91 init_empty_cutpool (int ncount, CCtsp_lpcuts *pool),
92 cut_eq (void *v_cut1, void *v_cut2, void *u_data),
93 read_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts *pool),
94 register_lpcuts (CCtsp_lpcuts *pool),
95 price_cliques (CCtsp_lpcuts *pool, int ncount, int ecount, int *elist,
96 double *x, double *cval);
97
98 static unsigned int
99 cut_hash (void *v_cut, void *u_data);
100
101 static void
102 sort_cliques (CCtsp_lpcut *c);
103
104 static double
105 price_clique (poolnode *nlist, CCtsp_lpclique *c, int marker);
106
107 #else
108
109 static int
110 init_empty_cutpool (),
111 cut_eq (),
112 read_cutpool (),
113 register_lpcuts (),
114 price_cliques ();
115
116 static unsigned int
117 cut_hash ();
118
119 static void
120 sort_cliques ();
121
122 static double
123 price_clique ();
124
125 #endif
126
127
128 #ifdef CC_PROTOTYPE_ANSI
CCtsp_init_cutpool(int ncount,char * poolfilename,CCtsp_lpcuts ** pool)129 int CCtsp_init_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts **pool)
130 #else
131 int CCtsp_init_cutpool (ncount, poolfilename, pool)
132 int ncount;
133 char *poolfilename;
134 CCtsp_lpcuts **pool;
135 #endif
136 {
137 int rval = 0;
138 CCtsp_lpcuts *p = (CCtsp_lpcuts *) NULL;
139
140 p = CC_SAFE_MALLOC (1, CCtsp_lpcuts);
141 if (!p) {
142 fprintf (stderr, "out of memory in CCtsp_init_cutpool\n");
143 return 1;
144 }
145 *pool = p;
146
147 p->cutcount = 0;
148 p->cuts = (CCtsp_lpcut *) NULL;
149 p->cutspace = 0;
150 p->cliqueend = 0;
151 p->cliques = (CCtsp_lpclique *) NULL;
152 p->cliquespace = 0;
153 p->cliquehash = (int *) NULL;
154 p->cuthash = (CCgenhash *) NULL;
155
156 rval = init_empty_cutpool (ncount, p);
157 if (rval) {
158 fprintf (stderr, "init_empty_cutpool failed\n"); goto CLEANUP;
159 }
160
161 if (poolfilename) {
162 rval = read_cutpool (ncount, poolfilename, p);
163 if (rval) {
164 fprintf (stderr, "read_cutpool failed\n"); goto CLEANUP;
165 }
166 }
167
168 CLEANUP:
169
170 return rval;
171 }
172
173 #ifdef CC_PROTOTYPE_ANSI
CCtsp_free_cutpool(CCtsp_lpcuts ** pool)174 void CCtsp_free_cutpool (CCtsp_lpcuts **pool)
175 #else
176 void CCtsp_free_cutpool (pool)
177 CCtsp_lpcuts **pool;
178 #endif
179 {
180 int i;
181
182 if (*pool) {
183 if ((*pool)->cuts) {
184 for (i = 0; i < (*pool)->cutcount; i++) {
185 CC_IFFREE ((*pool)->cuts[i].cliques, int);
186 }
187 CC_FREE ((*pool)->cuts, CCtsp_lpcut);
188 }
189 if ((*pool)->cliques) {
190 for (i=0; i < (*pool)->cliqueend; i++) {
191 CC_IFFREE ((*pool)->cliques[i].nodes, CCtsp_segment);
192 }
193 CC_FREE ((*pool)->cliques, CCtsp_lpclique);
194 }
195
196 CCtsp_free_cliquehash (*pool);
197
198 if ((*pool)->cuthash) {
199 CCutil_genhash_free ((*pool)->cuthash, NULL);
200 CC_FREE ((*pool)->cuthash, CCgenhash);
201 }
202 CC_FREE (*pool, CCtsp_lpcuts);
203 }
204 }
205
206 #ifdef CC_PROTOTYPE_ANSI
init_empty_cutpool(int ncount,CCtsp_lpcuts * pool)207 static int init_empty_cutpool (int ncount, CCtsp_lpcuts *pool)
208 #else
209 static int init_empty_cutpool (ncount, pool)
210 int ncount;
211 CCtsp_lpcuts *pool;
212 #endif
213 {
214 int rval = 0;
215
216 rval = CCtsp_init_cliquehash (pool, 10 * ncount);
217 if (rval) {
218 fprintf (stderr, "CCtsp_init_cliqhash failed\n");
219 return rval;
220 }
221
222 pool->cuthash = CC_SAFE_MALLOC (1, CCgenhash);
223 if (pool->cuthash == (CCgenhash *) NULL) {
224 fprintf (stderr, "Out of memory in init_empty_cutpool\n");
225 return -1;
226 }
227
228 rval = CCutil_genhash_init (pool->cuthash, 10 * ncount, cut_eq,
229 cut_hash, (void *) pool, 1.0, 0.6);
230 if (rval) {
231 fprintf (stderr, "CCgenhash_init failed\n");
232 return rval;
233 }
234
235 return 0;
236 }
237
238 #ifdef CC_PROTOTYPE_ANSI
cut_eq(void * v_cut1,void * v_cut2,void * u_data)239 static int cut_eq (void *v_cut1, void *v_cut2, void *u_data)
240 #else
241 static int cut_eq (v_cut1, v_cut2, u_data)
242 void *v_cut1;
243 void *v_cut2;
244 void *u_data;
245 #endif
246 {
247 CCtsp_lpcuts *pool = (CCtsp_lpcuts *) u_data;
248 CCtsp_lpcut *cut1 = pool->cuts + (long) v_cut1;
249 CCtsp_lpcut *cut2 = pool->cuts + (long) v_cut2;
250 int i;
251
252 if (cut1->cliquecount != cut2->cliquecount) return 1;
253 if (cut1->rhs != cut2->rhs) return 1;
254 if (cut1->sense != cut2->sense) return 1;
255 for (i=0; i<cut1->cliquecount; i++) {
256 if (cut1->cliques[i] != cut2->cliques[i]) return 1;
257 }
258 return 0;
259 }
260
261 #ifdef CC_PROTOTYPE_ANSI
cut_hash(void * v_cut,void * u_data)262 static unsigned int cut_hash (void *v_cut, void *u_data)
263 #else
264 static unsigned int cut_hash (v_cut, u_data)
265 void *v_cut;
266 void *u_data;
267 #endif
268 {
269 CCtsp_lpcuts *pool = (CCtsp_lpcuts *) u_data;
270 CCtsp_lpcut *cut = pool->cuts + (long) v_cut;
271 unsigned int x = ((unsigned int) cut->rhs) * 257 +
272 ((unsigned int) cut->sense);
273 int i;
274
275 for (i=0; i<cut->cliquecount; i++) {
276 x = x * 4099 + cut->cliques[i];
277 }
278 return x;
279 }
280
281 #ifdef CC_PROTOTYPE_ANSI
read_cutpool(int ncount,char * poolfilename,CCtsp_lpcuts * pool)282 static int read_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts *pool)
283 #else
284 static int read_cutpool (ncount, poolfilename, pool)
285 int ncount;
286 char *poolfilename;
287 CCtsp_lpcuts *pool;
288 #endif
289 {
290 CC_SFILE *in;
291 int n;
292 int rval = 0;
293
294 if (!poolfilename) {
295 fprintf (stderr, "pool file name is not set\n");
296 return 1;
297 }
298
299 in = CCutil_sopen (poolfilename, "r");
300 if (!in) {
301 fprintf (stderr, "sopen failed\n");
302 return 1;
303 }
304 if (CCutil_sread_int (in, (unsigned int *) &n)) {
305 fprintf (stderr, "CCutil_sread_int failed\n");
306 CCutil_sclose (in);
307 return 1;
308 }
309 if (n != ncount) {
310 fprintf (stderr, "cutpool %s does not have the correct ncount\n",
311 poolfilename);
312 CCutil_sclose (in);
313 return 1;
314 }
315
316 rval = CCtsp_prob_getcuts ((CCtsp_PROB_FILE *) NULL, in, pool);
317 if (rval < 0) {
318 fprintf (stderr, "CCtsp_prob_getcuts failed\n");
319 CCutil_sclose (in);
320 return rval;
321 }
322
323 rval = register_lpcuts (pool);
324 if (rval) {
325 fprintf (stderr, "register_lpcuts failed\n");
326 CCutil_sclose (in);
327 return rval;
328 }
329
330 CCutil_sclose (in);
331 return 0;
332 }
333
334 #ifdef CC_PROTOTYPE_ANSI
CCtsp_write_cutpool(int ncount,char * poolfilename,CCtsp_lpcuts * pool)335 int CCtsp_write_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts *pool)
336 #else
337 int CCtsp_write_cutpool (ncount, poolfilename, pool)
338 int ncount;
339 char *poolfilename;
340 CCtsp_lpcuts *pool;
341 #endif
342 {
343 CC_SFILE *out;
344 int rval = 0;
345
346 if (!poolfilename) {
347 fprintf (stderr, "pool file name not set\n");
348 return 1;
349 }
350
351 out = CCutil_sopen (poolfilename, "w");
352 if (!out) {
353 fprintf (stderr, "sopen failed\n");
354 return 1;
355 }
356 if (CCutil_swrite_int (out, (unsigned int) ncount)) {
357 fprintf (stderr, "CCutil_swrite_int failed\n");
358 CCutil_sclose (out);
359 return 1;
360 }
361
362 rval = CCtsp_prob_putcuts ((CCtsp_PROB_FILE *) NULL, out, pool);
363 if (rval) {
364 fprintf (stderr, "CCtsp_prob_putcuts failed\n");
365 CCutil_sclose (out);
366 return 1;
367 }
368
369 CCutil_sclose (out);
370 return 0;
371 }
372
373 #ifdef CC_PROTOTYPE_ANSI
CCtsp_search_cutpool(CCtsp_lpcuts * pool,CCtsp_lpcut_in ** cuts,int * cutcount,int ncount,int ecount,int * elist,double * x)374 int CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts,
375 int *cutcount, int ncount, int ecount, int *elist, double *x)
376 #else
377 int CCtsp_search_cutpool (pool, cuts, cutcount, ncount, ecount, elist, x)
378 CCtsp_lpcuts *pool;
379 CCtsp_lpcut_in **cuts;
380 int *cutcount;
381 int ncount, ecount;
382 int *elist;
383 double *x;
384 #endif
385 {
386 int rval = 0;
387 double *cval = (double *) NULL;
388 int *ind = (int *) NULL;
389 int i;
390 CCtsp_lpcut_in *newc;
391 double maxviol;
392
393 *cutcount = 0;
394 *cuts = (CCtsp_lpcut_in *) NULL;
395
396 if (pool->cutcount == 0) return 0;
397
398 cval = CC_SAFE_MALLOC (pool->cutcount, double);
399 if (!cval) {
400 fprintf (stderr, "out of memory in CCtsp_search_cutpool\n");
401 rval = 1; goto CLEANUP;
402 }
403 rval = CCtsp_price_cuts (pool, ncount, ecount, elist, x, cval);
404 if (rval) {
405 fprintf (stderr, "CCtsp_price_cuts failed\n");
406 goto CLEANUP;
407 }
408
409 ind = CC_SAFE_MALLOC (pool->cutcount, int);
410 if (!ind) {
411 fprintf (stderr, "out of memory in CCtsp_search_cutpool\n");
412 rval = 1; goto CLEANUP;
413 }
414
415 for (i = 0; i < pool->cutcount; i++) {
416 ind[i] = i;
417 }
418
419 CCutil_rselect (ind, 0, pool->cutcount - 1, POOL_MAXCUTS, cval);
420
421 maxviol = 0.0;
422 for (i = 0; i < pool->cutcount && i < POOL_MAXCUTS; i++) {
423 if (cval[ind[i]] < maxviol) maxviol = cval[ind[i]];
424 if (cval[ind[i]] < -POOL_MINVIOL) {
425 newc = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
426 if (!newc) {
427 fprintf (stderr, "out of memory in CCtsp_search_cutpool\n");
428 goto CLEANUP;
429 }
430 rval = CCtsp_lpcut_to_lpcut_in (pool, &pool->cuts[ind[i]], newc);
431 if (rval) {
432 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
433 CC_FREE (newc, CCtsp_lpcut_in);
434 goto CLEANUP;
435 }
436 newc->next = *cuts;
437 *cuts = newc;
438 (*cutcount)++;
439 }
440 }
441 printf ("%d pool cuts found, max violation %.3f\n", *cutcount, -maxviol);
442 rval = 0;
443
444 CLEANUP:
445
446 CC_IFFREE (cval, double);
447 CC_IFFREE (ind, int);
448 return rval;
449 }
450
451 #ifdef CC_PROTOTYPE_ANSI
CCtsp_search_cutpool_cliques(CCtsp_lpcuts * pool,CCtsp_lpclique ** cliques,int * cliquecount,int ncount,int ecount,int * elist,double * x,double maxdelta,int maxcliques,double ** cliquevals)452 int CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques,
453 int *cliquecount, int ncount, int ecount, int *elist, double *x,
454 double maxdelta, int maxcliques, double **cliquevals)
455 #else
456 int CCtsp_search_cutpool_cliques (pool, cliques, cliquecount, ncount, ecount,
457 elist, x, maxdelta, maxcliques, cliquevals)
458 CCtsp_lpcuts *pool;
459 CCtsp_lpclique **cliques;
460 int *cliquecount;
461 int ncount, ecount;
462 int *elist;
463 double *x;
464 double maxdelta;
465 int maxcliques;
466 double **cliquevals;
467 #endif
468 {
469 int rval = 0;
470 double *cval = (double *) NULL;
471 int *ind = (int *) NULL;
472 double upperdelta, lowerdelta;
473 int i, k;
474 int ccount = 0;
475
476 *cliquecount = 0;
477 *cliques = (CCtsp_lpclique *) NULL;
478 if (cliquevals) {
479 *cliquevals = (double *) NULL;
480 }
481
482 if (pool->cutcount == 0) return 0;
483
484 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
485 if (!cval) {
486 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
487 rval = 1; goto CLEANUP;
488 }
489
490 rval = price_cliques (pool, ncount, ecount, elist, x, cval);
491 if (rval) {
492 fprintf (stderr, "price_cliques failed\n");
493 goto CLEANUP;
494 }
495
496 ind = CC_SAFE_MALLOC (pool->cliqueend, int);
497 if (!ind) {
498 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
499 rval = 1; goto CLEANUP;
500 }
501 for (i = 0; i < pool->cliqueend; i++) {
502 ind[i] = i;
503 }
504
505 CCutil_rselect (ind, 0, pool->cliqueend - 1, maxcliques, cval);
506
507 upperdelta = -1.0;
508 lowerdelta = maxdelta;
509 for (i = 0; i < pool->cliqueend && i < maxcliques; i++) {
510 if (cval[ind[i]] < maxdelta) {
511 ccount++;
512 if (cval[ind[i]] < lowerdelta) lowerdelta = cval[ind[i]];
513 if (cval[ind[i]] > upperdelta) upperdelta = cval[ind[i]];
514 }
515 }
516
517 if (ccount == 0) {
518 printf ("Found no nearly tight cliques\n"); fflush (stdout);
519 goto CLEANUP;
520 }
521
522 *cliques = CC_SAFE_MALLOC (ccount, CCtsp_lpclique);
523 if (!(*cliques)) {
524 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
525 rval = 1; goto CLEANUP;
526 }
527 if (cliquevals) {
528 *cliquevals = CC_SAFE_MALLOC (ccount, double);
529 if (!(*cliquevals)) {
530 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
531 CC_FREE (*cliques, CCtsp_lpclique);
532 rval = 1; goto CLEANUP;
533 }
534 }
535
536 ccount = 0;
537 for (i = 0; i < pool->cliqueend && i < maxcliques; i++) {
538 if (cval[ind[i]] < maxdelta) {
539 rval = CCtsp_copy_lpclique (&(pool->cliques[ind[i]]),
540 &((*cliques)[ccount]));
541 if (rval) {
542 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
543 for (k = 0; k < ccount; k++) {
544 CC_FREE ((*cliques)[k].nodes, CCtsp_segment);
545 }
546 CC_FREE (*cliques, CCtsp_lpclique);
547 if (cliquevals) {
548 CC_FREE (*cliquevals, double);
549 }
550 goto CLEANUP;
551 }
552 if (cliquevals) {
553 (*cliquevals)[ccount] = cval[ind[i]];
554 }
555 ccount++;
556 }
557 }
558 *cliquecount = ccount;
559
560 printf ("%d nearly tight cliques found, range (%.3f, %.3f)\n",
561 *cliquecount, lowerdelta, upperdelta);
562 fflush (stdout);
563
564 CLEANUP:
565
566 CC_IFFREE (cval, double);
567 CC_IFFREE (ind, int);
568 return rval;
569 }
570
571 #define BRANCH_CLIQUE_GOAL 3.00
572 #define BRANCH_CLIQUE_TOL 0.99
573
574 #ifdef CC_PROTOTYPE_ANSI
CCtsp_branch_cutpool_cliques(CCtsp_lpcuts * pool,CCtsp_lpclique ** cliques,int * cliquecount,int ncount,int ecount,int * elist,double * x,int nwant,double ** cliquevals)575 int CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques,
576 int *cliquecount, int ncount, int ecount, int *elist, double *x,
577 int nwant, double **cliquevals)
578 #else
579 int CCtsp_branch_cutpool_cliques (pool, cliques, cliquecount, ncount, ecount,
580 elist, x, nwant, cliquevals)
581 CCtsp_lpcuts *pool;
582 CCtsp_lpclique **cliques;
583 int *cliquecount;
584 int ncount, ecount;
585 int *elist;
586 double *x;
587 int nwant;
588 double **cliquevals;
589 #endif
590 {
591 int rval = 0;
592 double *cval = (double *) NULL;
593 double upperdelta, lowerdelta;
594 double t;
595 int i, k;
596 int ccount = 0;
597 int *blist = (int *) NULL;
598 double *bval = (double *) NULL;
599
600 printf ("branch_cutpool_cliques ...\n"); fflush (stdout);
601
602 *cliquecount = 0;
603 *cliques = (CCtsp_lpclique *) NULL;
604 if (cliquevals) {
605 *cliquevals = (double *) NULL;
606 }
607
608 if (pool->cutcount == 0 || nwant <= 0) return 0;
609
610 blist = CC_SAFE_MALLOC (nwant + 1, int);
611 bval = CC_SAFE_MALLOC (nwant + 1, double);
612 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
613 if (!blist || !bval || !cval) {
614 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
615 rval = 1; goto CLEANUP;
616 }
617
618 rval = price_cliques (pool, ncount, ecount, elist, x, cval);
619 if (rval) {
620 fprintf (stderr, "price_cliques failed\n");
621 goto CLEANUP;
622 }
623
624 for (i = 0; i < nwant; i++) {
625 blist[i] = -1;
626 bval[i] = CCtsp_LP_MAXDOUBLE;
627 }
628 blist[nwant] = -1;
629 bval[i] = -1.0;
630
631 for (i = 0; i < pool->cliqueend; i++) {
632 t = CC_OURABS (BRANCH_CLIQUE_GOAL - cval[i]);
633 if (t < bval[0] && t < BRANCH_CLIQUE_TOL) {
634 for (k = 0; t < bval[k+1]; k++) {
635 blist[k] = blist[k+1];
636 bval[k] = bval[k+1];
637 }
638 blist[k] = i;
639 bval[k] = t;
640 }
641 }
642
643 upperdelta = -1.0;
644 lowerdelta = CCtsp_LP_MAXDOUBLE;
645 for (i = 0; i < nwant; i++) {
646 if (blist[i] != -1) {
647 if (upperdelta < cval[blist[i]]) {
648 upperdelta = cval[blist[i]];
649 }
650 if (lowerdelta > cval[blist[i]]) {
651 lowerdelta = cval[blist[i]];
652 }
653 ccount++;
654 }
655 }
656
657 if (ccount == 0) {
658 printf ("Found no nearly tight cliques\n"); fflush (stdout);
659 goto CLEANUP;
660 }
661
662 *cliques = CC_SAFE_MALLOC (ccount, CCtsp_lpclique);
663 if (!(*cliques)) {
664 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
665 rval = 1; goto CLEANUP;
666 }
667 if (cliquevals) {
668 *cliquevals = CC_SAFE_MALLOC (ccount, double);
669 if (!(*cliquevals)) {
670 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
671 CC_FREE (*cliques, CCtsp_lpclique);
672 rval = 1; goto CLEANUP;
673 }
674 }
675
676 ccount = 0;
677 for (i = nwant - 1; i >= 0; i--) {
678 if (blist[i] != -1) {
679 rval = CCtsp_copy_lpclique (&(pool->cliques[blist[i]]),
680 &((*cliques)[ccount]));
681 if (rval) {
682 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
683 for (k = 0; k < ccount; k++) {
684 CC_FREE ((*cliques)[k].nodes, CCtsp_segment);
685 }
686 CC_FREE (*cliques, CCtsp_lpclique);
687 if (cliquevals) {
688 CC_FREE (*cliquevals, double);
689 }
690 goto CLEANUP;
691 }
692 if (cliquevals) {
693 (*cliquevals)[ccount] = cval[blist[i]];
694 }
695 ccount++;
696 }
697 }
698 *cliquecount = ccount;
699
700 printf ("%d candidate branching cliques, range (%.3f, %.3f)\n",
701 *cliquecount, lowerdelta, upperdelta);
702 fflush (stdout);
703
704
705 CLEANUP:
706
707 CC_IFFREE (blist, int);
708 CC_IFFREE (bval, double);
709 CC_IFFREE (cval, double);
710 return rval;
711 }
712
713
714 #ifdef CC_PROTOTYPE_ANSI
CCtsp_add_to_cutpool(CCtsp_lpcuts * pool,CCtsp_lpcuts * cuts,CCtsp_lpcut * c)715 int CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts,
716 CCtsp_lpcut *c)
717 #else
718 int CCtsp_add_to_cutpool (pool, cuts, c)
719 CCtsp_lpcuts *pool;
720 CCtsp_lpcuts *cuts;
721 CCtsp_lpcut *c;
722 #endif
723 {
724 int rval = 0;
725 CCtsp_lpcut_in cin;
726 int k;
727
728 if (!c || c->cliquecount <= 1)
729 return 0;
730
731 cin.cliquecount = 0;
732 cin.cliques = (CCtsp_lpclique *) NULL;
733
734
735 rval = CCtsp_lpcut_to_lpcut_in (cuts, c, &cin);
736 if (rval) {
737 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
738 goto CLEANUP;
739 }
740
741 rval = CCtsp_add_to_cutpool_lpcut_in (pool, &cin);
742 if (rval) {
743 fprintf (stderr, "CCtsp_add_to_cutpool_lpcut_in failed\n");
744 goto CLEANUP;
745 }
746
747 CLEANUP:
748
749 for (k = 0; k < cin.cliquecount; k++) {
750 CC_IFFREE (cin.cliques[k].nodes, CCtsp_segment);
751 }
752 CC_IFFREE (cin.cliques, CCtsp_lpclique);
753
754 return rval;
755 }
756
757 #ifdef CC_PROTOTYPE_ANSI
CCtsp_add_to_cutpool_lpcut_in(CCtsp_lpcuts * pool,CCtsp_lpcut_in * cut)758 int CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool, CCtsp_lpcut_in *cut)
759 #else
760 int CCtsp_add_to_cutpool_lpcut_in (pool, cut)
761 CCtsp_lpcuts *pool;
762 CCtsp_lpcut_in *cut;
763 #endif
764 {
765 int rval = 0;
766 CCtsp_lpcut new;
767 int cutloc;
768 unsigned int hval;
769
770 if (!pool)
771 return 0;
772
773 new.rhs = cut->rhs;
774 new.branch = cut->branch;
775 new.sense = cut->sense;
776 new.modcount = 0;
777 new.mods = (CCtsp_sparser *) NULL;
778 new.handlecount = 0;
779 new.cliquecount = 0;
780 new.cliques = (int *) NULL;
781 new.age = 0;
782
783 rval = CCtsp_register_cliques (pool, cut, &new);
784 if (rval) {
785 fprintf (stderr, "register_cliques failed\n");
786 return rval;
787 }
788
789 sort_cliques (&new);
790
791 cutloc = CCtsp_add_cut_to_cutlist (pool, &new);
792 if (cutloc < 0) {
793 fprintf (stderr, "CCtsp_add_cut_to_cutlist failed\n");
794 CCtsp_unregister_cliques (pool, &new);
795 return cutloc;
796 }
797
798 hval = CCutil_genhash_hash (pool->cuthash, (void *) ((long) cutloc));
799 if (CCutil_genhash_lookup_h (pool->cuthash, hval,
800 (void *) ((long) cutloc))) {
801 /* cut was already in pool */
802 CCtsp_delete_cut_from_cutlist (pool, cutloc);
803 return 0;
804 }
805
806 rval = CCutil_genhash_insert_h (pool->cuthash, hval, (void *) ((long) cutloc),
807 (void *) ((long) 1));
808 if (rval) {
809 fprintf (stderr, "CCgenhash_insert_h failed\n");
810 CCtsp_delete_cut_from_cutlist (pool, cutloc);
811 return rval;
812 }
813
814 return 0;
815 }
816
817 #ifdef CC_PROTOTYPE_ANSI
sort_cliques(CCtsp_lpcut * c)818 static void sort_cliques (CCtsp_lpcut *c)
819 #else
820 static void sort_cliques (c)
821 CCtsp_lpcut *c;
822 #endif
823 {
824 CCutil_int_array_quicksort (c->cliques, c->handlecount);
825 CCutil_int_array_quicksort (c->cliques + c->handlecount,
826 c->cliquecount - c->handlecount);
827 }
828
829 #ifdef CC_PROTOTYPE_ANSI
register_lpcuts(CCtsp_lpcuts * pool)830 static int register_lpcuts (CCtsp_lpcuts *pool)
831 #else
832 static int register_lpcuts (pool)
833 CCtsp_lpcuts *pool;
834 #endif
835 {
836 int i;
837 unsigned int hval;
838 int rval = 0;
839 int ndup = 0;
840
841 for (i=0; i<pool->cutcount; i++) {
842 sort_cliques (&pool->cuts[i]);
843 hval = CCutil_genhash_hash (pool->cuthash, (void *) ((long) i));
844 if (CCutil_genhash_lookup_h (pool->cuthash, hval,
845 (void *) ((long) i))) {
846 ndup++;
847 } else {
848 rval = CCutil_genhash_insert_h (pool->cuthash, hval,
849 (void *) ((long) i),
850 (void *) ((long) 1));
851 if (rval) {
852 fprintf (stderr, "CCgenhash_insert_h failed\n");
853 return rval;
854 }
855 }
856 }
857 if (ndup) {
858 printf ("%d duplicates detected in pool\n", ndup);
859 fflush (stdout);
860 }
861 return 0;
862 }
863
864 #ifdef CC_PROTOTYPE_ANSI
CCtsp_display_cutpool(CCtsp_lpcuts * pool)865 int CCtsp_display_cutpool (CCtsp_lpcuts *pool)
866 #else
867 int CCtsp_display_cutpool (pool)
868 CCtsp_lpcuts *pool;
869 #endif
870 {
871 int i, k;
872 CCtsp_lpcut_in c;
873
874 for (i = 0; i < pool->cutcount; i++) {
875 if (CCtsp_lpcut_to_lpcut_in (pool, &(pool->cuts[i]), &c)) {
876 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
877 return 1;
878 }
879 CCtsp_print_lpcut_in (&c);
880 for (k = 0; k < c.cliquecount; k++) {
881 CC_IFFREE (c.cliques[k].nodes, CCtsp_segment);
882 }
883 }
884
885 return 0;
886 }
887
888 #ifdef CC_PROTOTYPE_ANSI
CCtsp_price_cuts(CCtsp_lpcuts * pool,int ncount,int ecount,int * elist,double * x,double * cutval)889 int CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount, int *elist,
890 double *x, double *cutval)
891 #else
892 int CCtsp_price_cuts (pool, ncount, ecount, elist, x, cutval)
893 CCtsp_lpcuts *pool;
894 int ncount;
895 int ecount;
896 int *elist;
897 double *x;
898 double *cutval;
899 #endif
900 {
901 double *cval = (double *) NULL;
902 int cutcount = pool->cutcount;
903 int i, j;
904 CCtsp_lpcut *c;
905 int rval = 0;
906
907 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
908 if (!cval) {
909 fprintf (stderr, "out of memory in CCtsp_price_cuts\n");
910 return 1;
911 }
912
913 rval = price_cliques (pool, ncount, ecount, elist, x, cval);
914 if (rval) {
915 fprintf (stderr, "price_cliques failed\n");
916 return rval;
917 }
918
919 for (i = 0, c = pool->cuts; i < cutcount; i++, c++) {
920 cutval[i] = (double) -(c->rhs);
921 for (j = 0; j < c->cliquecount; j++) {
922 cutval[i] += cval[c->cliques[j]];
923 }
924 }
925
926 CC_FREE (cval, double);
927 return 0;
928 }
929
930 #ifdef CC_PROTOTYPE_ANSI
price_cliques(CCtsp_lpcuts * pool,int ncount,int ecount,int * elist,double * x,double * cval)931 static int price_cliques (CCtsp_lpcuts *pool, int ncount, int ecount,
932 int *elist, double *x, double *cval)
933 #else
934 static int price_cliques (pool, ncount, ecount, elist, x, cval)
935 CCtsp_lpcuts *pool;
936 int ncount;
937 int ecount;
938 int *elist;
939 double *x;
940 double *cval;
941 #endif
942 {
943 poolnode *nlist = (poolnode *) NULL;
944 pooledge *espace = (pooledge *) NULL;
945 pooledge *p;
946 char *marks = (char *) NULL;
947 int marker = 0;
948 int i, j, a, b, count;
949 int cend = pool->cliqueend;
950 int rval = 0;
951
952 nlist = CC_SAFE_MALLOC (ncount, poolnode);
953 if (!nlist) {
954 fprintf (stderr, "out of memory in price_cliques\n");
955 rval = 1; goto CLEANUP;
956 }
957
958 for (i = 0; i < ncount; i++) {
959 nlist[i].mark = 0;
960 nlist[i].deg = 0;
961 }
962
963 count = 0;
964 for (i = 0; i < ecount; i++) {
965 if (x[i] >= ZERO_EPSILON) {
966 nlist[elist[2*i]].deg++;
967 nlist[elist[2*i+1]].deg++;
968 count++;
969 }
970 }
971 espace = CC_SAFE_MALLOC (2*count, pooledge);
972 if (!espace) {
973 fprintf (stderr, "out of memory in price_cliques\n");
974 rval = 1; goto CLEANUP;
975 }
976
977 p = espace;
978 for (i = 0; i < ncount; i++) {
979 nlist[i].adj = p;
980 p += nlist[i].deg;
981 nlist[i].deg = 0;
982 }
983 for (i = 0; i < ecount; i++) {
984 if (x[i] >= ZERO_EPSILON) {
985 a = elist[2*i];
986 b = elist[2*i+1];
987 nlist[a].adj[nlist[a].deg].x = x[i];
988 nlist[a].adj[nlist[a].deg++].to = b;
989 nlist[b].adj[nlist[b].deg].x = x[i];
990 nlist[b].adj[nlist[b].deg++].to = a;
991 }
992 }
993
994 marks = CC_SAFE_MALLOC (cend, char);
995 if (!marks) {
996 fprintf (stderr, "out of memory in price_cliques\n");
997 rval = 1; goto CLEANUP;
998 }
999
1000 for (i = 0; i < cend; i++) {
1001 marks[i] = 0;
1002 }
1003 for (i = 0; i < pool->cutcount; i++) {
1004 for (j = 0; j < pool->cuts[i].cliquecount; j++) {
1005 marks[pool->cuts[i].cliques[j]] = 1;
1006 }
1007 }
1008
1009 for (i = 0; i < cend; i++) {
1010 if (marks[i]) {
1011 marker++;
1012 cval[i] = price_clique (nlist, &(pool->cliques[i]), marker);
1013 } else {
1014 cval[i] = 0.0;
1015 }
1016 }
1017
1018 CLEANUP:
1019
1020 CC_IFFREE (nlist, poolnode);
1021 CC_IFFREE (espace, pooledge);
1022 CC_IFFREE (marks, char);
1023 return rval;
1024 }
1025
1026 #ifdef CC_PROTOTYPE_ANSI
price_clique(poolnode * nlist,CCtsp_lpclique * c,int marker)1027 static double price_clique (poolnode *nlist, CCtsp_lpclique *c, int marker)
1028 #else
1029 static double price_clique (nlist, c, marker)
1030 poolnode *nlist;
1031 CCtsp_lpclique *c;
1032 int marker;
1033 #endif
1034 {
1035 double val = 0.0;
1036 poolnode *n;
1037 int i, j, k;
1038
1039 for (i = 0; i < c->segcount; i++) {
1040 for (j = c->nodes[i].lo; j <= c->nodes[i].hi; j++) {
1041 nlist[j].mark = marker;
1042 }
1043 }
1044 for (i = 0; i < c->segcount; i++) {
1045 for (j = c->nodes[i].lo; j <= c->nodes[i].hi; j++) {
1046 n = &(nlist[j]);
1047 for (k = 0; k < n->deg; k++) {
1048 if (nlist[n->adj[k].to].mark != marker) {
1049 val += n->adj[k].x;
1050 }
1051 }
1052 }
1053 }
1054 return val;
1055 }
1056