1 /****************************************************************************/
2 /* */
3 /* This file is part of CONCORDE */
4 /* */
5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */
6 /* Vasek Chvatal, and William Cook */
7 /* */
8 /* Permission is granted for academic research use. For other uses, */
9 /* contact the authors for licensing options. */
10 /* */
11 /* Use at your own risk. We make no guarantees about the */
12 /* correctness or usefulness of this code. */
13 /* */
14 /****************************************************************************/
15
16 /****************************************************************************/
17 /* */
18 /* STORING AND SEARCHING THE CUTPOOL */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: March 19, 1997 */
25 /* May 27, 1997 (bico) */
26 /* January 30, 2003 (bico) */
27 /* */
28 /* EXPORTED FUNCTIONS: */
29 /* */
30 /* int CCtsp_init_cutpool (int *ncount, char *poolfilename, */
31 /* CCtsp_lpcuts **pool) */
32 /* -ncount is a pointer to the number of nodes in the problem */
33 /* -poolfilename is a file containing an cutpool (it can be NULL) */
34 /* -CCtsp_lpcuts will return the pool */
35 /* NOTES: poolfilename must be non-NULL or ncount must be */
36 /* non-NULL and *ncount nonzero. If ncount is non-NULL but */
37 /* *ncount == zero, then *ncount will be set to the number of */
38 /* nodes in the cutpool in poolfilename */
39 /* NOTES: */
40 /* This version does not use the compressed set references. Notes */
41 /* on the representation are given in "Chapter 4: The Linear */
42 /* Programming Problems". */
43 /* */
44 /* int CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts, */
45 /* int *cutcount, double *maxviol, int ncount, int ecount, */
46 /* int *elist, double *x, int nthreads, CCrandstate *rstate) */
47 /* RETURNS an array of cuts having x(delta(C)) < rhs(C) */
48 /* -pool points to a cutpool (or cuts of an lp) */
49 /* -cuts will return the array of cuts */
50 /* -cutcount with return the length of the array */
51 /* -ncount is the number of nodes in the problem */
52 /* -ecount is the number of edges in elist */
53 /* -elist is a list of edges in end end format */
54 /* -x is an ecount-long array of weights */
55 /* -nthreads is the number of threads to use. 0 ==> sequential code */
56 /* threads are only used if CC_POSIXTHREADS is defined */
57 /* */
58 /* int CCtsp_search_remotepool (char *remotehost, */
59 /* unsigned short remoteport, CCtsp_lpcut_in **cuts, */
60 /* int *cutcount, double *maxviol, int ncount, int ecount, */
61 /* int *elist, double *x) */
62 /* RETURNS an array of cuts having x(delta(C)) < rhs(C) from a remote */
63 /* cutpool */
64 /* -remotehost is the host with the cuts */
65 /* -remoteport is the port on which to contact the remote server */
66 /* (if remoteport == 0, use CCtsp_CUT_PORT) */
67 /* -cuts will return the array of cuts */
68 /* -cutcount with return the length of the array */
69 /* -ncount is the number of nodes in the problem */
70 /* -ecount is the number of edges in elist */
71 /* -elist is a list of edges in end end format */
72 /* -x is an ecount-long array of weights */
73 /* */
74 /* int CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, */
75 /* CCtsp_lpclique **cliques, int *cliquecount, int ncount, */
76 /* int ecount, int *elist, double *x, double maxdelta, */
77 /* int maxcliques, double **cliquevals, CCrandstate *rstate) */
78 /* RETURNS an array of cliques having x(delta(C)) < maxdelta */
79 /* -pool points to a cutpool (or cuts of an lp) */
80 /* -cliques will return the array of cliques */
81 /* -cliquecount with return the length of the array */
82 /* -ncount is the number of nodes in the problem */
83 /* -ecount is the number of edges in elist */
84 /* -elist is a list of edges in end end format */
85 /* -x is an ecount-long array of weights */
86 /* -maxdelta is a bound on x(delta(C)) */
87 /* -maxcliques is an upperbound on the number of cliques that should */
88 /* be returned */
89 /* -cliquevals will return the values of x(delta(C)) for the cliques */
90 /* (this parameter can be NULL) */
91 /* */
92 /* int CCtsp_add_cut_to_cutlist (CCtsp_lpcuts *cuts, CCtsp_lpcut *c) */
93 /* NONE */
94 /* */
95 /* void CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts *cuts, int ind) */
96 /* NONE */
97 /* */
98 /* void CCtsp_free_cutpool (CCtsp_lpcuts **pool) */
99 /* FREES the pool of cuts. */
100 /* */
101 /* int CCtsp_write_cutpool (int ncount, const char *poolfilename, */
102 /* CCtsp_lpcuts *pool) */
103 /* WRITES pool to poolfilename. */
104 /* */
105 /* int CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, */
106 /* CCtsp_lpclique **cliques, int *cliquecount, int ncount, */
107 /* int ecount, int *elist, double *x, int nwant, */
108 /* double **cliquevals, int silent) */
109 /* RETURNS an array of cliques having x(delta(C)) as close to 3.0 as */
110 /* possible. */
111 /* -the parmeters are like those used by search_cutpool_cliques, */
112 /* where nwant is the number of cliques we would like to have in */
113 /* the array. */
114 /* */
115 /* int CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount, */
116 /* int *elist, double *x, double *cutval) */
117 /* COMPUTES the slack on each cut in the pool */
118 /* -ecount, elist, and x give an x-vector */
119 /* -cutval returns the array of slack values (it should be passed in */
120 /* as an array of length at least pool->cutcount) */
121 /* */
122 /* int CCtsp_price_cuts_threaded (CCtsp_lpcuts *pool, int ncount, */
123 /* int ecount, int *elist, double *x, double *cutval, */
124 /* int numthreads) */
125 /* COMPUTES the slack on each cut in the pool in parallel */
126 /* -ecount, elist, and x give an x-vector */
127 /* -cutval returns the array of slack values (it should be passed in */
128 /* as an array of length at least pool->cutcount) */
129 /* -nthreads is the number of parallel threads to use. */
130 /* */
131 /* int CCtsp_get_clique_prices (CCtsp_lpcuts *pool, int **p_cliquenums, */
132 /* double **p_cliquevals, double mindelta, double maxdelta, */
133 /* int *p_cliquecount, int ncount, int ecount, int *elist, */
134 /* double *x) */
135 /* RETURNS the id's and x(delta(C)) for cliques in the pool. */
136 /* -the parameters pool, ncount, ecount, elist, and x are like those */
137 /* used by search_cutpool_cliques. */
138 /* -mindelta and maxdelta are bounds on x(delta(C)) */
139 /* -cliquenums and cliquevals return id's and x(delta(C)) for */
140 /* cliques with x(delta(C)) between mindelta and maxdelta */
141 /* -cliquecount returns the number of cliques in cliquenums/vals */
142 /* -use CCtsp_get_clique to retrive specific cliques. */
143 /* */
144 /* int CCtsp_get_clique (CCtsp_lpcuts *pool, int cliquenum, */
145 /* CCtsp_lpclique **p_clique) */
146 /* RETURNS p_clique, a pointer to the clique numbered clqiuenum in */
147 /* the pool. Note that this clique is not a copy, and thus should */
148 /* not be freed. */
149 /* */
150 /* int CCtsp_display_cutpool (CCtsp_lpcuts *pool) */
151 /* DISPLAYS the contents of a cutpool. */
152 /* */
153 /* int CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts, */
154 /* CCtsp_lpcut *c) */
155 /* -pool is the pool to add the cut to */
156 /* -cuts is the lpcuts the cut is from */
157 /* -c is the cut */
158 /* ADDS a cut to a pool */
159 /* */
160 /* int CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool, */
161 /* CCtsp_lpcut_in *c) */
162 /* -pool is the pool to add the cut to */
163 /* -c is the cut */
164 /* ADDS a cut to a pool */
165 /* */
166 /* void CCtsp_free_lpcut_in (CCtsp_lpcut_in *c) */
167 /* FREES the fields in the CCtsp_lpcut pointed to by c. */
168 /* */
169 /* void CCtsp_free_lpclique (CCtsp_lpclique *c) */
170 /* FREES the fields in the CCtsp_lpclique pointed to by c. */
171 /* */
172 /* void CCtsp_free_lpdomino (CCtsp_lpdomino *c) */
173 /* FREES the fields in the CCtsp_lpdomino pointed to by c. */
174 /* */
175 /* int CCtsp_read_cuts (CC_SFILE *f, int *ncount, CCtsp_lpcuts *cuts, */
176 /* int readmods, int buildhash) */
177 /* READS the cuts from f into cuts. */
178 /* -readmods indicates whether or not the file contains sparser mods */
179 /* */
180 /* int CCtsp_read_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount) */
181 /* MISSING */
182 /* */
183 /* int CCtsp_read_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount) */
184 /* MISSING */
185 /* */
186 /* int CCtsp_read_lpdomino (CC_SFILE *f, CCtsp_lpdomino *d, int ncount) */
187 /* READS the lpdomino from the file stream. */
188 /* */
189 /* int CCtsp_send_newcuts (int ncount, CCtsp_lpcuts *pool, */
190 /* char *remotehost, unsigned short remoteport) */
191 /* SENDS the new cuts from pool to the remote host */
192 /* */
193 /* int CCtsp_write_cuts (CC_SFILE *f, int ncount, CCtsp_lpcuts *cuts, */
194 /* int writemods) */
195 /* WRITES the cuts from cuts to f. */
196 /* -writemods indicates whether or not the file should contain */
197 /* sparser mods */
198 /* */
199 /* int CCtsp_write_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount) */
200 /* MISSING */
201 /* */
202 /* int CCtsp_write_lpcut (CC_SFILE *f, CCtsp_lpcuts *cuts, */
203 /* CCtsp_lpcut *c, int ncount) */
204 /* MISSING */
205 /* */
206 /* int CCtsp_write_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount) */
207 /* MISSING */
208 /* */
209 /* int CCtsp_copy_cuts (CC_SFILE *f, CC_SFILE *t, int copymods) */
210 /* COPIES the cuts from f to t. */
211 /* */
212 /* int CCtsp_register_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c, */
213 /* CCtsp_lpcut *new) */
214 /* BUILDS the references to the cliques in c into the cut strucure */
215 /* pointed to by cuts and creates an array of the indices of the */
216 /* the cliques in CCtsp_lpcut new */
217 /* -cuts is the structure holding the set of cuts */
218 /* -c describes the cut to be added to the structure */
219 /* -new returns the array of clique indices */
220 /* */
221 /* void CCtsp_unregister_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut *c) */
222 /* REMOVES the references to the cliques in cut c (and deletes the */
223 /* cliques if they have no more references) and frees the array */
224 /* of clique indices in c */
225 /* -cuts is the structure holding the set of cuts */
226 /* -c is the cut containing the cliques to be removed */
227 /* */
228 /* int CCtsp_register_dominos (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c, */
229 /* CCtsp_lpcut *new) */
230 /* BUILDS the references to the dominos in c into the cut strucure */
231 /* pointed to by cuts and creates an array of the indices of the */
232 /* the dominos in CCtsp_lpcut new */
233 /* */
234 /* void CCtsp_unregister_dominos (CCtsp_lpcuts *cuts, CCtsp_lpcut *c) */
235 /* REMOVES the references to the dominos in cut c (and deletes the */
236 /* dominos if they have no more references) and frees the array */
237 /* of domino indices in c */
238 /* */
239 /****************************************************************************/
240
241 #include "machdefs.h"
242 #include "util.h"
243 #include "macrorus.h"
244 #include "tsp.h"
245
246 #define ZERO_EPSILON 0.0000000001
247 #define POOL_MAXCUTS 500
248 #define POOL_MINVIOL 0.001
249
250 #define PROB_CUTS_VERSION 2 /* Version 1 is pre-dominos */
251
252 typedef struct pooledge {
253 double x;
254 int to;
255 } pooledge;
256
257 typedef struct poolnode {
258 struct pooledge *adj;
259 int mark;
260 int deg;
261 } poolnode;
262
263
264 static int
265 init_empty_cutpool_hash (int ncount, CCtsp_lpcuts *pool),
266 cut_eq (void *v_cut1, void *v_cut2, void *u_data),
267 read_cutpool (int *ncount, char *poolfilename, CCtsp_lpcuts *pool),
268 register_lpcuts (CCtsp_lpcuts *pool),
269 price_cliques (CCtsp_lpclique *cliques, int ncount, int ecount, int *elist,
270 double *x, double *cval, int cend),
271 make_pricing_graph (int ncount, int ecount, int *elist, double *x,
272 poolnode **p_nlist, pooledge **p_espace);
273
274 static unsigned int
275 cut_hash (void *v_cut, void *u_data);
276
277 static void
278 #ifdef CC_POSIXTHREADS
279 *price_cliques_thread (void *args),
280 *price_cuts_thread (void *args),
281 rebalance_load (int nthreads, double *workload, double *worktime,
282 double *work),
283 #endif
284 price_cuts (CCtsp_lpcut *cuts, int cutcount, double *cval,
285 double *cutval),
286 sort_cliques (CCtsp_lpcut *c),
287 sort_dominos (CCtsp_lpcut *c);
288
289 static double
290 price_clique (poolnode *nlist, CCtsp_lpclique *c, int marker);
291
292
293
CCtsp_init_cutpool(int * ncount,char * poolfilename,CCtsp_lpcuts ** pool)294 int CCtsp_init_cutpool (int *ncount, char *poolfilename, CCtsp_lpcuts **pool)
295 {
296 int rval = 0;
297 CCtsp_lpcuts *p = (CCtsp_lpcuts *) NULL;
298
299 p = CC_SAFE_MALLOC (1, CCtsp_lpcuts);
300 if (!p) {
301 fprintf (stderr, "out of memory in CCtsp_init_cutpool\n");
302 return 1;
303 }
304 *pool = p;
305
306 p->cutcount = 0;
307 p->savecount = 0;
308 p->cuts = (CCtsp_lpcut *) NULL;
309 p->cutspace = 0;
310 p->cliqueend = 0;
311 p->cliques = (CCtsp_lpclique *) NULL;
312 p->cliquespace = 0;
313 p->cliquehash = (int *) NULL;
314 p->dominoend = 0;
315 p->dominos = (CCtsp_lpdomino *) NULL;
316 p->dominospace = 0;
317 p->dominohash = (int *) NULL;
318 p->cuthash = (CCgenhash *) NULL;
319 p->workloads = (double *) NULL;
320
321 if (poolfilename == (char *) NULL) {
322 if (ncount == (int *) NULL || *ncount <= 0) {
323 fprintf (stderr, "Neither poolfilename nor ncount\n");
324 rval = 1; goto CLEANUP;
325 }
326 rval = init_empty_cutpool_hash (*ncount, p);
327 if (rval) {
328 fprintf (stderr, "init_empty_cutpool_hash failed\n"); goto CLEANUP;
329 }
330 } else {
331 rval = read_cutpool (ncount, poolfilename, p);
332 if (rval) {
333 fprintf (stderr, "read_cutpool failed\n"); goto CLEANUP;
334 }
335 }
336
337 CLEANUP:
338 return rval;
339 }
340
CCtsp_free_cutpool(CCtsp_lpcuts ** pool)341 void CCtsp_free_cutpool (CCtsp_lpcuts **pool)
342 {
343 int i, k;
344
345 if (*pool) {
346 if ((*pool)->cuts) {
347 for (i = 0; i < (*pool)->cutcount; i++) {
348 CC_IFFREE ((*pool)->cuts[i].cliques, int);
349 CCtsp_free_skeleton (&(*pool)->cuts[i].skel);
350 }
351 CC_FREE ((*pool)->cuts, CCtsp_lpcut);
352 }
353 if ((*pool)->cliques) {
354 for (i=0; i < (*pool)->cliqueend; i++) {
355 CC_IFFREE ((*pool)->cliques[i].nodes, CCtsp_segment);
356 }
357 CC_FREE ((*pool)->cliques, CCtsp_lpclique);
358 }
359 if ((*pool)->dominos) {
360 for (i=0; i < (*pool)->dominoend; i++) {
361 for (k = 0; k < 2; k++) {
362 CC_IFFREE ((*pool)->dominos[i].sets[k].nodes,
363 CCtsp_segment);
364 }
365 }
366 CC_FREE ((*pool)->dominos, CCtsp_lpdomino);
367 }
368
369 CCtsp_free_cliquehash (*pool);
370 CCtsp_free_dominohash (*pool);
371
372 if ((*pool)->cuthash) {
373 CCutil_genhash_free ((*pool)->cuthash, NULL);
374 CC_FREE ((*pool)->cuthash, CCgenhash);
375 }
376 CC_IFFREE ((*pool)->workloads, double);
377 CC_FREE (*pool, CCtsp_lpcuts);
378 }
379 }
380
init_empty_cutpool_hash(int ncount,CCtsp_lpcuts * pool)381 static int init_empty_cutpool_hash (int ncount, CCtsp_lpcuts *pool)
382 {
383 int rval = 0;
384
385 rval = CCtsp_init_cliquehash (pool, 10 * ncount);
386 CCcheck_rval (rval, "CCtsp_init_cliquehash failed");
387
388 rval = CCtsp_init_dominohash (pool, 10 * ncount);
389 CCcheck_rval (rval, "CCtsp_init_dominohash failed");
390
391 pool->cuthash = CC_SAFE_MALLOC (1, CCgenhash);
392 CCcheck_NULL (pool->cuthash, "out of memory in init_empty_cutpool_hash");
393
394 rval = CCutil_genhash_init (pool->cuthash, 10 * ncount, cut_eq,
395 cut_hash, (void *) pool, 1.0, 0.6);
396 CCcheck_rval (rval, "CCutil_genhash_init failed");
397
398 CLEANUP:
399
400 return rval;
401 }
402
cut_eq(void * v_cut1,void * v_cut2,void * u_data)403 static int cut_eq (void *v_cut1, void *v_cut2, void *u_data)
404 {
405 CCtsp_lpcuts *pool = (CCtsp_lpcuts *) u_data;
406 CCtsp_lpcut *cut1 = pool->cuts + (long) v_cut1;
407 CCtsp_lpcut *cut2 = pool->cuts + (long) v_cut2;
408 int i;
409
410 if (cut1->cliquecount != cut2->cliquecount) return 1;
411 if (cut1->dominocount != cut2->dominocount) return 1;
412 if (cut1->rhs != cut2->rhs) return 1;
413 if (cut1->sense != cut2->sense) return 1;
414 for (i=0; i<cut1->cliquecount; i++) {
415 if (cut1->cliques[i] != cut2->cliques[i]) return 1;
416 }
417 for (i=0; i<cut1->dominocount; i++) {
418 if (cut1->dominos[i] != cut2->dominos[i]) return 1;
419 }
420 #if 0
421 {
422 int diff = 0;
423 CCtsp_compare_skeletons (&cut1->skel, &cut2->skel, &diff);
424 if (diff) {
425 printf ("SURPRISE - cuts look equal but have different skeletons\n");
426 return 1;
427 }
428 }
429 #endif
430 return 0;
431 }
432
cut_hash(void * v_cut,void * u_data)433 static unsigned int cut_hash (void *v_cut, void *u_data)
434 {
435 CCtsp_lpcuts *pool = (CCtsp_lpcuts *) u_data;
436 CCtsp_lpcut *cut = pool->cuts + (long) v_cut;
437 unsigned int x = ((unsigned int) cut->rhs) * 257 +
438 ((unsigned int) cut->sense);
439 int i;
440
441 for (i=0; i<cut->cliquecount; i++) {
442 x = x * 4099 + cut->cliques[i];
443 }
444 for (i=0; i<cut->dominocount; i++) {
445 x = x * 4099 + cut->dominos[i];
446 }
447 return x;
448 }
449
read_cutpool(int * ncount,char * poolfilename,CCtsp_lpcuts * pool)450 static int read_cutpool (int *ncount, char *poolfilename, CCtsp_lpcuts *pool)
451 {
452 CC_SFILE *in = (CC_SFILE *) NULL;
453 int n;
454 int rval = 0;
455
456 if (poolfilename == (char *) NULL) {
457 fprintf (stderr, "pool file name is not set\n");
458 rval = 1; goto CLEANUP;
459 }
460
461 in = CCutil_sopen (poolfilename, "r");
462 if (!in) {
463 fprintf (stderr, "CCutil_sopen failed\n");
464 rval = 1; goto CLEANUP;
465 }
466
467 rval = CCtsp_read_cuts (in, &n, pool, 0, 1);
468 if (rval < 0) {
469 fprintf (stderr, "CCtsp_read_cuts failed\n"); goto CLEANUP;
470 }
471
472 if (ncount != (int *) NULL && *ncount > 0 && n != *ncount) {
473 fprintf (stderr, "cutpool %s does not have the correct ncount\n",
474 poolfilename);
475 rval = 1; goto CLEANUP;
476 }
477
478 if (ncount != (int *) NULL) *ncount = n;
479
480 rval = CCutil_sclose (in);
481 in = (CC_SFILE *) NULL;
482 if (rval) {
483 fprintf (stderr, "CCutil_sclose failed\n"); goto CLEANUP;
484 }
485
486 rval = 0;
487
488 CLEANUP:
489 if (in != (CC_SFILE *) NULL) {
490 CCutil_sclose (in);
491 }
492
493 return rval;
494 }
495
CCtsp_read_cuts(CC_SFILE * f,int * ncount,CCtsp_lpcuts * cuts,int readmods,int buildhash)496 int CCtsp_read_cuts (CC_SFILE *f, int *ncount, CCtsp_lpcuts *cuts,
497 int readmods, int buildhash)
498 {
499 int i, j, k, ncliq, ndom, rhs, cliq, dom, nmod, n, mult;
500 char sense;
501 int cliqcount = 0, cutcount = 0, dominocount = 0;
502 CCtsp_lpclique c;
503 CCtsp_lpdomino d;
504 CCtsp_lpcut u;
505 int *hits = (int *) NULL;
506 int *domhits = (int *) NULL;
507 char version;
508 int rval;
509 int nbits, cbits, dbits;
510
511 CCtsp_init_lpclique (&c);
512
513 if (CCutil_sread_char (f, &version)) goto FAILURE;
514
515 if (version != 1 && version != 2) {
516 fprintf (stderr, "Unknown cuts version %d\n", (unsigned) version);
517 goto FAILURE;
518 } else {
519 if (CCutil_sread_int (f, ncount)) goto FAILURE;
520 nbits = CCutil_sbits (*ncount);
521
522 if (buildhash) {
523 rval = init_empty_cutpool_hash (*ncount, cuts);
524 if (rval) {
525 fprintf (stderr, "init_empty_cutpool_hash failed\n");
526 goto FAILURE;
527 }
528 }
529
530 if (CCutil_sread_int (f, &cliqcount)) goto FAILURE;
531 for (i = 0; i < cliqcount; i++) {
532 rval = CCtsp_read_lpclique (f, &c, *ncount);
533 if (rval) {
534 fprintf (stderr, "CCtsp_read_lpclique failed\n");
535 goto FAILURE;
536 }
537 k = CCtsp_register_clique (cuts, &c);
538 if (k == -1) {
539 fprintf (stderr, "CCtsp_register_clique failed\n");
540 goto FAILURE;
541 }
542 if (k != i) {
543 fprintf (stderr, "clique registration number is out of seq\n");
544 goto FAILURE;
545 }
546 CCtsp_free_lpclique (&c);
547 }
548
549 if (version == 1) {
550 dominocount = 0;
551 } else {
552 if (CCutil_sread_int (f, &dominocount)) goto FAILURE;
553 }
554 for (i = 0; i < dominocount; i++) {
555 rval = CCtsp_read_lpdomino (f, &d, *ncount);
556 if (rval) {
557 fprintf (stderr, "CCtsp_read_lpdomino failed\n");
558 goto FAILURE;
559 }
560 k = CCtsp_register_domino (cuts, &d);
561 if (k == -1) {
562 fprintf (stderr, "CCtsp_register_domino failed\n");
563 goto FAILURE;
564 }
565 if (k != i) {
566 fprintf (stderr, "domino registration number is out of seq\n");
567 goto FAILURE;
568 }
569 CCtsp_free_lpdomino (&d);
570 }
571
572 if (cliqcount) {
573 hits = CC_SAFE_MALLOC (cliqcount, int);
574 if (!hits) {
575 fprintf (stderr, "out of memory in CCtsp_read_cuts\n");
576 goto FAILURE;
577 }
578 for (i = 0; i < cliqcount; i++) hits[i] = 0;
579 }
580
581 if (dominocount) {
582 domhits = CC_SAFE_MALLOC (dominocount, int);
583 if (!domhits) {
584 fprintf (stderr, "out of memory in CCtsp_read_cuts\n");
585 goto FAILURE;
586 }
587 for (i = 0; i < dominocount; i++) domhits[i] = 0;
588 }
589
590 cbits = CCutil_sbits (cliqcount);
591 dbits = CCutil_sbits (dominocount);
592 if (CCutil_sread_int (f, &cutcount)) goto FAILURE;
593
594 for (i=0; i<cutcount; i++) {
595 CCtsp_init_lpcut (&u);
596 if (CCutil_sread_int (f, &ncliq)) goto FAILURE;
597 if (version == 1) {
598 ndom = 0;
599 } else {
600 if (CCutil_sread_int (f, &ndom)) goto FAILURE;
601 }
602 if (CCutil_sread_int (f, &rhs)) goto FAILURE;
603 if (CCutil_sread_char (f, &sense)) goto FAILURE;
604 u.cliquecount = ncliq;
605 u.dominocount = ndom;
606 u.rhs = rhs;
607 u.sense = sense;
608 u.branch = 0;
609 u.age = 0;
610 u.cliques = CC_SAFE_MALLOC (ncliq, int);
611 if (!u.cliques) {
612 fprintf (stderr, "out of memory in CCtsp_read_cuts\n");
613 goto FAILURE;
614 }
615 for (j = 0; j < ncliq; j++) {
616 if (CCutil_sread_bits (f, &cliq, cbits))
617 goto FAILURE;
618 u.cliques[j] = cliq;
619 if (hits[cliq])
620 cuts->cliques[cliq].refcount++;
621 else
622 hits[cliq] = 1;
623 }
624 if (ndom) {
625 u.dominos = CC_SAFE_MALLOC (ndom, int);
626 if (!u.dominos) {
627 fprintf (stderr, "out of memory in CCtsp_read_cuts\n");
628 goto FAILURE;
629 }
630 for (j = 0; j < ndom; j++) {
631 if (CCutil_sread_bits (f, &dom, dbits)) {
632 goto FAILURE;
633 }
634 u.dominos[j] = dom;
635 if (domhits[dom]) {
636 cuts->dominos[dom].refcount++;
637 } else {
638 domhits[dom] = 1;
639 }
640 }
641 } else {
642 u.dominos = (int *) NULL;
643 }
644 if (readmods) {
645 if (CCutil_sread_int (f, &nmod)) goto FAILURE;
646 u.modcount = nmod;
647 if (nmod) {
648 u.mods = CC_SAFE_MALLOC (nmod, CCtsp_sparser);
649 if (!u.mods) {
650 fprintf (stderr, "out of memory in CCtsp_read_cuts\n");
651 CC_FREE (u.cliques, int);
652 goto FAILURE;
653 }
654 } else {
655 u.mods = (CCtsp_sparser *) NULL;
656 }
657 for (j = 0; j < nmod; j++) {
658 if (CCutil_sread_bits (f, &n, nbits))
659 goto FAILURE;
660 if (CCutil_sread_int (f, &mult))
661 goto FAILURE;
662 u.mods[j].node = (unsigned int) n;
663 u.mods[j].mult = (unsigned int) mult;
664 }
665 } else {
666 u.mods = (CCtsp_sparser *) NULL;
667 u.modcount = 0;
668 }
669
670 rval = CCtsp_read_skeleton (f, &u.skel, *ncount);
671 if (rval) {
672 fprintf (stderr, "CCtsp_read_skeleton failed\n");
673 goto FAILURE;
674 }
675
676 k = CCtsp_add_cut_to_cutlist (cuts, &u);
677 if (k == -1) {
678 fprintf (stderr, "CCtsp_add_cut_to_cutlist failed\n");
679 goto FAILURE;
680 }
681 if (k != i) {
682 fprintf (stderr, "cut location is out of seq\n");
683 goto FAILURE;
684 }
685 }
686
687 CC_IFFREE (hits, int);
688 CC_IFFREE (domhits, int);
689
690 if (buildhash) {
691 rval = register_lpcuts (cuts);
692 if (rval) {
693 fprintf (stderr, "register_lpcuts failed\n");
694 goto FAILURE;
695 }
696 }
697 }
698
699 return 0;
700
701 FAILURE:
702
703 CC_IFFREE (hits, int);
704 CC_IFFREE (domhits, int);
705 if (cutcount) {
706 for (i = 0; i < cutcount; i++) {
707 CCtsp_delete_cut_from_cutlist (cuts, i);
708 }
709 } else {
710 for (i = 0; i < cliqcount; i++) {
711 CCtsp_unregister_clique (cuts, i);
712 }
713 for (i = 0; i < dominocount; i++) {
714 CCtsp_unregister_domino (cuts, i);
715 }
716 }
717 return -1;
718 }
719
CCtsp_read_lpcut_in(CC_SFILE * f,CCtsp_lpcut_in * c,int ncount)720 int CCtsp_read_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount)
721 {
722 int rval = 0;
723 int ncliques, ndominos;
724 int i;
725 int rhs;
726 char sense;
727
728 CCtsp_init_lpcut_in (c);
729
730 rval = CCutil_sread_int (f, &ncliques);
731 CCcheck_rval (rval, "CCutil_sread_int failed");
732
733 rval = CCutil_sread_int (f, &ndominos);
734 CCcheck_rval (rval, "CCutil_sread_int failed");
735
736 c->cliquecount = ncliques;
737 c->cliques = CC_SAFE_MALLOC (ncliques, CCtsp_lpclique);
738 CCcheck_NULL (c->cliques, "out of memory in CCtsp_read_lpcut_in");
739 for (i=0; i<ncliques; i++) {
740 CCtsp_init_lpclique (&c->cliques[i]);
741 }
742 for (i = 0; i < ncliques; i++) {
743 rval = CCtsp_read_lpclique (f, &c->cliques[i], ncount);
744 CCcheck_rval (rval, "CCtsp_read_lpclique failed");
745 }
746
747 c->dominocount = ndominos;
748 if (ndominos > 0) {
749 c->dominos = CC_SAFE_MALLOC (ndominos, CCtsp_lpdomino);
750 CCcheck_NULL (c->dominos, "out of memory in CCtsp_read_lpcut_in");
751 for (i=0; i<ndominos; i++) {
752 CCtsp_init_lpdomino (&c->dominos[i]);
753 }
754 for (i = 0; i < ndominos; i++) {
755 rval = CCtsp_read_lpdomino (f, &c->dominos[i], ncount);
756 CCcheck_rval (rval, "CCtsp_read_lpdomino failed");
757 }
758 }
759
760 rval = CCutil_sread_int (f, &rhs);
761 CCcheck_rval (rval, "CCutil_sread_int failed");
762 c->rhs = rhs;
763
764 rval = CCutil_sread_char (f, &sense);
765 CCcheck_rval (rval, "CCutil_sread_int failed");
766 c->sense = sense;
767
768 c->branch = 0;
769
770 rval = CCtsp_read_skeleton (f, &c->skel, ncount);
771 if (rval) {
772 fprintf (stderr, "CCtsp_read_skeleton failed\n");
773 goto CLEANUP;
774 }
775
776 rval = 0;
777
778 CLEANUP:
779
780 if (rval) {
781 CCtsp_free_lpcut_in (c);
782 }
783 return rval;
784 }
785
CCtsp_read_lpclique(CC_SFILE * f,CCtsp_lpclique * c,int ncount)786 int CCtsp_read_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount)
787 {
788 int rval;
789 int size;
790 int i;
791 int lo;
792 int hi;
793 int nbits = CCutil_sbits (ncount);
794
795 c->nodes = (CCtsp_segment *) NULL;
796
797 rval = CCutil_sread_bits (f, &size, nbits);
798 if (rval) {
799 fprintf (stderr, "CCutil_sread_int failed\n");
800 goto CLEANUP;
801 }
802 c->nodes = CC_SAFE_MALLOC (size, CCtsp_segment);
803 if (c->nodes == (CCtsp_segment *) NULL) {
804 fprintf (stderr, "Out of memory in CCtsp_read_lpclique\n");
805 rval = 1; goto CLEANUP;
806 }
807 c->segcount = size;
808
809 for (i=0; i < size; i++) {
810 rval = CCutil_sread_bits (f, &lo, nbits);
811 if (rval) {
812 fprintf (stderr, "CCutil_sread_int failed\n");
813 goto CLEANUP;
814 }
815 rval = CCutil_sread_bits (f, &hi, nbits);
816 if (rval) {
817 fprintf (stderr, "CCutil_sread_int failed\n");
818 goto CLEANUP;
819 }
820 c->nodes[i].lo = lo;
821 c->nodes[i].hi = hi;
822 }
823 rval = 0;
824
825 CLEANUP:
826
827 if (rval) {
828 CCtsp_free_lpclique (c);
829 }
830 return rval;
831 }
832
CCtsp_read_lpdomino(CC_SFILE * f,CCtsp_lpdomino * d,int ncount)833 int CCtsp_read_lpdomino (CC_SFILE *f, CCtsp_lpdomino *d, int ncount)
834 {
835 int rval = 0;
836 int k;
837
838 CCtsp_init_lpdomino (d);
839
840 for (k = 0; k < 2; k++) {
841 rval = CCtsp_read_lpclique (f, &(d->sets[k]), ncount);
842 CCcheck_rval (rval, "CCtsp_read_lpclique failed");
843 }
844
845 CLEANUP:
846
847 if (rval) {
848 CCtsp_free_lpdomino (d);
849 }
850 return rval;
851 }
852
CCtsp_write_cuts(CC_SFILE * f,int ncount,CCtsp_lpcuts * cuts,int writemods)853 int CCtsp_write_cuts (CC_SFILE *f, int ncount, CCtsp_lpcuts *cuts,
854 int writemods)
855 {
856 int *marks = (int *) NULL;
857 int *dmarks = (int *) NULL;
858 int cend = cuts->cliqueend;
859 int dend = cuts->dominoend;
860 int i, j;
861 int rval;
862 int cnt = 0, dcnt = 0;
863 int cbits, dbits, nbits;
864
865 rval = CCutil_swrite_char (f, PROB_CUTS_VERSION);
866 CCcheck_rval (rval, "CCutil_swrite_char failed");
867 rval = CCutil_swrite_int (f, ncount);
868 CCcheck_rval (rval, "CCutil_swrite_int failed");
869 nbits = CCutil_sbits (ncount);
870
871 if (cend > 0) {
872 marks = CC_SAFE_MALLOC (cend, int);
873 CCcheck_NULL (marks, "out of memory in CCtsp_write_cuts");
874 for (i = 0; i < cend; i++) marks[i] = 0;
875
876 for (i = 0; i < cuts->cutcount; i++) {
877 for (j = 0; j < cuts->cuts[i].cliquecount; j++) {
878 marks[cuts->cuts[i].cliques[j]]++;
879 }
880 }
881 for (i = 0; i < cend; i++) {
882 if (marks[i]) {
883 if (marks[i] != cuts->cliques[i].refcount) {
884 fprintf (stderr, "ERROR in refcount for clique %d\n", i);
885 rval = 1; goto CLEANUP;
886 }
887 marks[i] = cnt+1;
888 cnt++;
889 }
890 }
891 }
892
893 cbits = CCutil_sbits (cnt);
894 rval = CCutil_swrite_int (f, cnt);
895 if (rval) goto CLEANUP;
896
897 for (i = 0; i < cend; i++) {
898 if (marks[i]) {
899 rval = CCtsp_write_lpclique (f, &cuts->cliques[i], ncount);
900 CCcheck_rval (rval, "CCtsp_write_lpclique failed");
901 }
902 }
903
904
905 if (dend > 0) {
906 dmarks = CC_SAFE_MALLOC (dend, int);
907 CCcheck_NULL (dmarks, "out of memory in CCtsp_write_cuts");
908 for (i = 0; i < dend; i++) dmarks[i] = 0;
909
910 for (i = 0; i < cuts->cutcount; i++) {
911 for (j = 0; j < cuts->cuts[i].dominocount; j++) {
912 dmarks[cuts->cuts[i].dominos[j]]++;
913 }
914 }
915 for (i = 0; i < dend; i++) {
916 if (dmarks[i]) {
917 if (dmarks[i] != cuts->dominos[i].refcount) {
918 fprintf (stderr, "ERROR in ref for domino %d (%d, %d)\n",
919 i, dmarks[i], cuts->dominos[i].refcount);
920 rval = 1; goto CLEANUP;
921 }
922 dmarks[i] = dcnt+1;
923 dcnt++;
924 }
925 }
926 }
927
928 dbits = CCutil_sbits (dcnt);
929 rval = CCutil_swrite_int (f, dcnt);
930 if (rval) goto CLEANUP;
931
932 for (i = 0; i < dend; i++) {
933 if (dmarks[i]) {
934 rval = CCtsp_write_lpdomino (f, &cuts->dominos[i], ncount);
935 CCcheck_rval (rval, "CCtsp_write_lpdomino failed");
936 }
937 }
938
939
940 rval = CCutil_swrite_int (f, cuts->cutcount);
941 if (rval) goto CLEANUP;
942
943 for (i = 0; i < cuts->cutcount; i++) {
944 rval = CCutil_swrite_int (f, cuts->cuts[i].cliquecount);
945 if (rval) goto CLEANUP;
946 rval = CCutil_swrite_int (f, cuts->cuts[i].dominocount);
947 if (rval) goto CLEANUP;
948 rval = CCutil_swrite_int (f, cuts->cuts[i].rhs);
949 if (rval) goto CLEANUP;
950 rval = CCutil_swrite_char (f, cuts->cuts[i].sense);
951 if (rval) goto CLEANUP;
952
953 for (j = 0; j < cuts->cuts[i].cliquecount; j++) {
954 rval = CCutil_swrite_bits (f,marks[cuts->cuts[i].cliques[j]] - 1,
955 cbits);
956 CCcheck_rval (rval, "CCutil_swrite_bits failed");
957 }
958 for (j = 0; j < cuts->cuts[i].dominocount; j++) {
959 rval = CCutil_swrite_bits (f,dmarks[cuts->cuts[i].dominos[j]] - 1,
960 dbits);
961 CCcheck_rval (rval, "CCutil_swrite_bits failed");
962 }
963 if (writemods) {
964 rval = CCutil_swrite_int (f, cuts->cuts[i].modcount);
965 if (rval) goto CLEANUP;
966 for (j = 0; j < cuts->cuts[i].modcount; j++) {
967 rval = CCutil_swrite_bits (f, cuts->cuts[i].mods[j].node,
968 nbits);
969 if (rval) goto CLEANUP;
970 rval = CCutil_swrite_int (f, cuts->cuts[i].mods[j].mult);
971 if (rval) goto CLEANUP;
972 }
973 }
974 rval = CCtsp_write_skeleton (f, &cuts->cuts[i].skel, ncount);
975 CCcheck_rval (rval, "CCtsp_write_skeleton failed");
976 }
977
978 rval = 0;
979
980 CLEANUP:
981
982 CC_IFFREE (marks, int);
983 CC_IFFREE (dmarks, int);
984 return rval;
985 }
986
CCtsp_send_newcuts(int ncount,CCtsp_lpcuts * pool,char * remotehost,unsigned short remoteport)987 int CCtsp_send_newcuts (int ncount, CCtsp_lpcuts *pool, char *remotehost,
988 unsigned short remoteport)
989 {
990 CC_SFILE *f = (CC_SFILE *) NULL;
991 int i;
992 int rval = 0;
993
994 #ifdef CC_NETREADY
995 f = CCutil_snet_open (remotehost, remoteport);
996 if (f == (CC_SFILE *) NULL) {
997 fprintf (stderr, "CCutil_snet_open failed\n");
998 rval = 1; goto CLEANUP;
999 }
1000 #endif /* CC_NETREADY */
1001
1002 rval = CCutil_swrite_char (f, CCtsp_POOL_PUTCUTS);
1003 CCcheck_rval (rval, "CCutil_swrite_char failed");
1004
1005 rval = CCutil_swrite_int (f, ncount);
1006 CCcheck_rval (rval, "CCutil_swrite_int failed");
1007
1008 rval = CCutil_swrite_int (f, pool->cutcount - pool->savecount);
1009 CCcheck_rval (rval, "CCutil_swrite_int failed");
1010
1011 for (i=pool->savecount; i<pool->cutcount; i++) {
1012 rval = CCtsp_write_lpcut (f, pool, &pool->cuts[i], ncount);
1013 CCcheck_rval (rval, "CCtsp_write_lpcut failed");
1014 }
1015
1016 rval = CCutil_sclose (f);
1017 f = (CC_SFILE *) NULL;
1018 CCcheck_rval (rval, "CCutil_sclose failed");
1019
1020 pool->savecount = pool->cutcount;
1021
1022 CLEANUP:
1023
1024 if (f != (CC_SFILE *) NULL) {
1025 CCutil_sclose (f);
1026 }
1027 return rval;
1028 }
1029
CCtsp_write_lpcut_in(CC_SFILE * f,CCtsp_lpcut_in * c,int ncount)1030 int CCtsp_write_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount)
1031 {
1032 int rval = 0;
1033 int i;
1034
1035 rval = CCutil_swrite_int (f, c->cliquecount);
1036 CCcheck_rval (rval, "CCutil_swrite_int failed");
1037
1038 rval = CCutil_swrite_int (f, c->dominocount);
1039 CCcheck_rval (rval, "CCutil_swrite_int failed");
1040
1041 for (i = 0; i < c->cliquecount; i++) {
1042 rval = CCtsp_write_lpclique (f, &c->cliques[i], ncount);
1043 CCcheck_rval (rval, "CCtsp_write_lpclique failed");
1044 }
1045
1046 for (i = 0; i < c->dominocount; i++) {
1047 rval = CCtsp_write_lpdomino (f, &c->dominos[i], ncount);
1048 CCcheck_rval (rval, "CCtsp_write_lpdomino failed");
1049 }
1050
1051 rval = CCutil_swrite_int (f, c->rhs);
1052 CCcheck_rval (rval, "CCutil_swrite_int failed");
1053
1054 rval = CCutil_swrite_char (f, c->sense);
1055 CCcheck_rval (rval, "CCutil_swrite_char failed");
1056
1057 rval = CCtsp_write_skeleton (f, &c->skel, ncount);
1058 CCcheck_rval (rval, "CCtsp_write_skeleton failed");
1059
1060 CLEANUP:
1061
1062 return rval;
1063 }
1064
CCtsp_write_lpcut(CC_SFILE * f,CCtsp_lpcuts * cuts,CCtsp_lpcut * c,int ncount)1065 int CCtsp_write_lpcut (CC_SFILE *f, CCtsp_lpcuts *cuts, CCtsp_lpcut *c,
1066 int ncount)
1067 {
1068 int rval = 0;
1069 int i;
1070
1071 rval = CCutil_swrite_int (f, c->cliquecount);
1072 CCcheck_rval (rval, "CCutil_swrite_int failed");
1073
1074 rval = CCutil_swrite_int (f, c->dominocount);
1075 CCcheck_rval (rval, "CCutil_swrite_int failed");
1076
1077 for (i = 0; i < c->cliquecount; i++) {
1078 rval = CCtsp_write_lpclique (f, &cuts->cliques[c->cliques[i]], ncount);
1079 CCcheck_rval (rval, "CCtsp_write_lpclique failed");
1080 }
1081
1082 for (i = 0; i < c->dominocount; i++) {
1083 rval = CCtsp_write_lpdomino (f, &cuts->dominos[c->dominos[i]], ncount);
1084 CCcheck_rval (rval, "CCtsp_write_lpdomino failed");
1085 }
1086
1087 rval = CCutil_swrite_int (f, c->rhs);
1088 CCcheck_rval (rval, "CCutil_swrite_int failed");
1089
1090 rval = CCutil_swrite_char (f, c->sense);
1091 CCcheck_rval (rval, "CCutil_swrite_char failed");
1092
1093 rval = CCtsp_write_skeleton (f, &c->skel, ncount);
1094 CCcheck_rval (rval, "CCtsp_write_skeleton failed");
1095
1096 CLEANUP:
1097
1098 return rval;
1099 }
1100
CCtsp_write_lpclique(CC_SFILE * f,CCtsp_lpclique * c,int ncount)1101 int CCtsp_write_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount)
1102 {
1103 int rval = 0;
1104 int i;
1105 int nbits = CCutil_sbits (ncount);
1106
1107 rval = CCutil_swrite_bits (f, c->segcount, nbits);
1108 CCcheck_rval (rval, "CCutil_swrite_bits failed");
1109
1110 for (i=0; i < c->segcount; i++) {
1111 rval = CCutil_swrite_bits (f, c->nodes[i].lo, nbits);
1112 CCcheck_rval (rval, "CCutil_swrite_bits failed");
1113
1114 rval = CCutil_swrite_bits (f, c->nodes[i].hi, nbits);
1115 CCcheck_rval (rval, "CCutil_swrite_bits failed");
1116 }
1117
1118 CLEANUP:
1119
1120 return rval;
1121 }
1122
CCtsp_write_lpdomino(CC_SFILE * f,CCtsp_lpdomino * c,int ncount)1123 int CCtsp_write_lpdomino (CC_SFILE *f, CCtsp_lpdomino *c, int ncount)
1124 {
1125 int rval = 0;
1126 int k;
1127
1128 for (k = 0; k < 2; k++) {
1129 rval = CCtsp_write_lpclique (f, &(c->sets[k]), ncount);
1130 CCcheck_rval (rval, "CCutil_write_lpcplique failed");
1131 }
1132
1133 CLEANUP:
1134
1135 return rval;
1136 }
1137
CCtsp_write_cutpool(int ncount,const char * poolfilename,CCtsp_lpcuts * pool)1138 int CCtsp_write_cutpool (int ncount, const char *poolfilename,
1139 CCtsp_lpcuts *pool)
1140 {
1141 CC_SFILE *out;
1142 int rval = 0;
1143
1144 if (!poolfilename) {
1145 fprintf (stderr, "pool file name not set\n");
1146 return 1;
1147 }
1148
1149 out = CCutil_sopen (poolfilename, "w");
1150 if (!out) {
1151 fprintf (stderr, "CCutil_sopen failed\n");
1152 return 1;
1153 }
1154
1155 rval = CCtsp_write_cuts (out, ncount, pool, 0);
1156 if (rval) {
1157 fprintf (stderr, "CCtsp_write_cuts failed\n");
1158 CCutil_sclose (out);
1159 return 1;
1160 }
1161
1162 CCutil_sclose (out);
1163 return 0;
1164 }
1165
CCtsp_copy_cuts(CC_SFILE * f,CC_SFILE * t,int copymods)1166 int CCtsp_copy_cuts (CC_SFILE *f, CC_SFILE *t, int copymods)
1167 {
1168 int rval;
1169 int cliqcount, dominocount;
1170 int cutcount;
1171 int cnt, ndom;
1172 int cbits, dbits;
1173 int nbits;
1174 char version;
1175 char ch;
1176 int ncount;
1177 CCtsp_lpclique c;
1178 CCtsp_lpdomino d;
1179 CCtsp_skeleton skel;
1180 int i;
1181 int j;
1182 int k;
1183
1184 CCtsp_init_lpclique (&c);
1185 CCtsp_init_lpdomino (&d);
1186 CCtsp_init_skeleton (&skel);
1187
1188 rval = CCutil_sread_char (f, &version);
1189 if (rval) goto CLEANUP;
1190 rval = CCutil_swrite_char (t, PROB_CUTS_VERSION);
1191 if (rval) goto CLEANUP;
1192
1193 if (version != 1 && version != 2) {
1194 fprintf (stderr, "Unknown cuts version %d\n", (unsigned) version);
1195 rval = 1; goto CLEANUP;
1196 }
1197
1198 rval = CCutil_sread_int (f, &ncount);
1199 if (rval) goto CLEANUP;
1200 rval = CCutil_swrite_int (t, ncount);
1201 if (rval) goto CLEANUP;
1202 nbits = CCutil_sbits (ncount);
1203
1204 rval = CCutil_sread_int (f, &cliqcount);
1205 if (rval) goto CLEANUP;
1206 rval = CCutil_swrite_int (t, cliqcount);
1207 if (rval) goto CLEANUP;
1208
1209 for (i = 0; i < cliqcount; i++) {
1210 rval = CCtsp_read_lpclique (f, &c, ncount);
1211 if (rval) goto CLEANUP;
1212 rval = CCtsp_write_lpclique (t, &c, ncount);
1213 if (rval) goto CLEANUP;
1214 CCtsp_free_lpclique (&c);
1215 }
1216
1217 if (version == 1) {
1218 dominocount = 0;
1219 } else {
1220 rval = CCutil_sread_int (f, &dominocount);
1221 CCcheck_rval (rval, "CCutil_sread_int failed");
1222 }
1223 rval = CCutil_swrite_int (t, dominocount);
1224 CCcheck_rval (rval, "CCutil_swrite_int failed");
1225
1226 for (i = 0; i < dominocount; i++) {
1227 rval = CCtsp_read_lpdomino (f, &d, ncount);
1228 CCcheck_rval (rval, "CCtsp_read_lpdomino failed");
1229 rval = CCtsp_write_lpdomino (t, &d, ncount);
1230 CCcheck_rval (rval, "CCtsp_write_lpdomino failed");
1231 }
1232
1233 cbits = CCutil_sbits (cliqcount);
1234 dbits = CCutil_sbits (dominocount);
1235
1236 rval = CCutil_sread_int (f, &cutcount);
1237 if (rval) goto CLEANUP;
1238 rval = CCutil_swrite_int (t, cutcount);
1239 if (rval) goto CLEANUP;
1240
1241 for (i = 0; i < cutcount; i++) {
1242 rval = CCutil_sread_int (f, &cnt);
1243 if (rval) goto CLEANUP;
1244 rval = CCutil_swrite_int (t, cnt);
1245 if (rval) goto CLEANUP;
1246
1247 if (version == 1) {
1248 ndom = 0;
1249 } else {
1250 rval = CCutil_sread_int (f, &ndom);
1251 CCcheck_rval (rval, "CCutil_sread_int failed");
1252 }
1253 rval = CCutil_swrite_int (t, ndom);
1254 if (rval) goto CLEANUP;
1255
1256 rval = CCutil_sread_int (f, &j); /* rhs */
1257 if (rval) goto CLEANUP;
1258 rval = CCutil_swrite_int (t, j);
1259 if (rval) goto CLEANUP;
1260 rval = CCutil_sread_char (f, &ch); /* sense */
1261 if (rval) goto CLEANUP;
1262 rval = CCutil_swrite_char (t, ch);
1263 if (rval) goto CLEANUP;
1264
1265 for (j = 0; j < cnt; j++) {
1266 rval = CCutil_sread_bits (f, &k, cbits);
1267 if (rval) goto CLEANUP;
1268 rval = CCutil_swrite_bits (t, k, cbits);
1269 if (rval) goto CLEANUP;
1270 }
1271
1272 for (j = 0; j < ndom; j++) {
1273 rval = CCutil_sread_bits (f, &k, dbits);
1274 if (rval) goto CLEANUP;
1275 rval = CCutil_swrite_bits (t, k, dbits);
1276 if (rval) goto CLEANUP;
1277 }
1278
1279 if (copymods) {
1280 rval = CCutil_sread_int (f, &cnt);
1281 if (rval) goto CLEANUP;
1282 rval = CCutil_swrite_int (t, cnt);
1283 if (rval) goto CLEANUP;
1284 for (j = 0; j < cnt; j++) {
1285 rval = CCutil_sread_bits (f, &k, nbits);
1286 if (rval) goto CLEANUP;
1287 rval = CCutil_swrite_bits (t, k, nbits);
1288 if (rval) goto CLEANUP;
1289 rval = CCutil_sread_int (f, &k);/* mult */
1290 if (rval) goto CLEANUP;
1291 rval = CCutil_swrite_int (t, k);
1292 if (rval) goto CLEANUP;
1293 }
1294 }
1295
1296 rval = CCtsp_read_skeleton (f, &skel, ncount);
1297 if (rval) goto CLEANUP;
1298 rval = CCtsp_write_skeleton (t, &skel, ncount);
1299 if (rval) goto CLEANUP;
1300 CCtsp_free_skeleton (&skel);
1301 }
1302
1303 CLEANUP:
1304
1305 CCtsp_free_lpclique (&c);
1306 CCtsp_free_lpdomino (&d);
1307 CCtsp_free_skeleton (&skel);
1308 return rval;
1309 }
1310
CCtsp_search_cutpool(CCtsp_lpcuts * pool,CCtsp_lpcut_in ** cuts,int * cutcount,double * maxviol,int ncount,int ecount,int * elist,double * x,int nthreads,CCrandstate * rstate)1311 int CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts,
1312 int *cutcount, double *maxviol, int ncount, int ecount, int *elist,
1313 double *x, int nthreads, CCrandstate *rstate)
1314 {
1315 int rval = 0;
1316 double *cval = (double *) NULL;
1317 int *ind = (int *) NULL;
1318 int i;
1319 CCtsp_lpcut_in *newc;
1320 double lmaxviol;
1321
1322 /*
1323 printf ("CCtsp_search_cutpool (%d)\n", pool->cutcount);
1324 fflush (stdout);
1325 */
1326
1327 for (i = 0; i < pool->cutcount; i++) {
1328 if (pool->cuts[i].dominocount != 0) {
1329 fprintf (stderr, "POOL yipes %d\n", pool->cuts[i].dominocount);
1330 rval = 1; goto CLEANUP;
1331 }
1332 }
1333
1334 *cutcount = 0;
1335 *maxviol = 0.0;
1336 *cuts = (CCtsp_lpcut_in *) NULL;
1337
1338 if (pool->cutcount == 0) return 0;
1339
1340 cval = CC_SAFE_MALLOC (pool->cutcount, double);
1341 if (!cval) {
1342 fprintf (stderr, "out of memory in CCtsp_search_cutpool\n");
1343 rval = 1; goto CLEANUP;
1344 }
1345
1346 if (nthreads > 0) {
1347 rval = CCtsp_price_cuts_threaded (pool, ncount, ecount, elist, x, cval,
1348 nthreads);
1349 if (rval) {
1350 fprintf (stderr, "CCtsp_price_cuts_threaded failed\n");
1351 goto CLEANUP;
1352 }
1353 } else {
1354 rval = CCtsp_price_cuts (pool, ncount, ecount, elist, x, cval);
1355 if (rval) {
1356 fprintf (stderr, "CCtsp_price_cuts failed\n");
1357 goto CLEANUP;
1358 }
1359 }
1360
1361 ind = CC_SAFE_MALLOC (pool->cutcount, int);
1362 if (!ind) {
1363 fprintf (stderr, "out of memory in CCtsp_search_cutpool\n");
1364 rval = 1; goto CLEANUP;
1365 }
1366
1367 for (i = 0; i < pool->cutcount; i++) {
1368 ind[i] = i;
1369 }
1370
1371 CCutil_rselect (ind, 0, pool->cutcount - 1, POOL_MAXCUTS, cval, rstate);
1372
1373 lmaxviol = 0.0;
1374 for (i = 0; i < pool->cutcount && i < POOL_MAXCUTS; i++) {
1375 if (cval[ind[i]] < lmaxviol) lmaxviol = cval[ind[i]];
1376 if (cval[ind[i]] < -POOL_MINVIOL) {
1377 newc = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
1378 CCcheck_NULL (newc, "out of memory in CCtsp_search_cutpool");
1379 rval = CCtsp_lpcut_to_lpcut_in (pool, &pool->cuts[ind[i]], newc);
1380 if (rval) {
1381 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
1382 CC_FREE (newc, CCtsp_lpcut_in);
1383 goto CLEANUP;
1384 }
1385 newc->next = *cuts;
1386 *cuts = newc;
1387 (*cutcount)++;
1388 }
1389 }
1390 *maxviol = -lmaxviol;
1391 rval = 0;
1392
1393 CLEANUP:
1394
1395 CC_IFFREE (cval, double);
1396 CC_IFFREE (ind, int);
1397 return rval;
1398 }
1399
CCtsp_search_remotepool(char * remotehost,unsigned short remoteport,CCtsp_lpcut_in ** cuts,int * cutcount,double * maxviol,int ncount,int ecount,int * elist,double * x)1400 int CCtsp_search_remotepool (char *remotehost, unsigned short remoteport,
1401 CCtsp_lpcut_in **cuts, int *cutcount, double *maxviol, int ncount,
1402 int ecount, int *elist, double *x)
1403 {
1404 CC_SFILE *f = (CC_SFILE *) NULL;
1405 int rval = 0;
1406 int i;
1407 CCtsp_lpcut_in *newc = (CCtsp_lpcut_in *) NULL;
1408 int cnt;
1409
1410 *cutcount = 0;
1411 *cuts = (CCtsp_lpcut_in *) NULL;
1412
1413 #ifdef CC_NETREADY
1414 f = CCutil_snet_open (remotehost, remoteport);
1415 if (f == (CC_SFILE *) NULL) {
1416 fprintf (stderr, "CCutil_snet_open failed\n");
1417 rval = 1; goto CLEANUP;
1418 }
1419 #endif /* CC_NETREADY */
1420
1421 rval = CCutil_swrite_char (f, CCtsp_POOL_GETCUTS);
1422 if (rval) {
1423 fprintf (stderr, "CCutil_swrite_char failed\n");
1424 goto CLEANUP;
1425 }
1426
1427 rval = CCutil_swrite_int (f, ncount);
1428 if (rval) {
1429 fprintf (stderr, "CCutil_swrite_int failed\n");
1430 goto CLEANUP;
1431 }
1432
1433 rval = CCutil_swrite_int (f, ecount);
1434 if (rval) {
1435 fprintf (stderr, "CCutil_swrite_int failed\n");
1436 goto CLEANUP;
1437 }
1438
1439 for (i=0; i<ecount; i++) {
1440 rval = CCutil_swrite_int (f, elist[2*i]);
1441 if (rval) {
1442 fprintf (stderr, "CCutil_swrite_int failed\n");
1443 goto CLEANUP;
1444 }
1445 rval = CCutil_swrite_int (f, elist[2*i+1]);
1446 if (rval) {
1447 fprintf (stderr, "CCutil_swrite_int failed\n");
1448 goto CLEANUP;
1449 }
1450 rval = CCutil_swrite_double (f, x[i]);
1451 if (rval) {
1452 fprintf (stderr, "CCutil_swrite_double failed\n");
1453 goto CLEANUP;
1454 }
1455 }
1456
1457 rval = CCutil_sread_int (f, &cnt);
1458 if (rval) {
1459 fprintf (stderr, "CCutil_sread_int failed\n");
1460 goto CLEANUP;
1461 }
1462
1463 rval = CCutil_sread_double (f, maxviol);
1464 if (rval) {
1465 fprintf (stderr, "CCutil_sread_double failed\n");
1466 goto CLEANUP;
1467 }
1468
1469 for (i=0; i<cnt; i++) {
1470 newc = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
1471 CCcheck_NULL (newc, "out of memory in CCtsp_search_cutpool");
1472 rval = CCtsp_read_lpcut_in (f, newc, ncount);
1473 if (rval) {
1474 fprintf (stderr, "read_lpcut_in failed\n");
1475 goto CLEANUP;
1476 }
1477 newc->next = *cuts;
1478 *cuts = newc;
1479 (*cutcount)++;
1480 newc = (CCtsp_lpcut_in *) NULL;
1481 }
1482
1483 rval = CCutil_sclose (f);
1484 f = (CC_SFILE *) NULL;
1485 if (rval) {
1486 fprintf (stderr, "CCutil_sclose failed\n");
1487 goto CLEANUP;
1488 }
1489
1490 rval = 0;
1491
1492 CLEANUP:
1493
1494 if (f != (CC_SFILE *) NULL) {
1495 CCutil_sclose (f);
1496 }
1497 CC_IFFREE (newc, CCtsp_lpcut_in);
1498 if (rval) {
1499 fprintf (stderr, "Failure in CCtsp_search_remotepool, continuing anyway\n");
1500 rval = 0;
1501 }
1502
1503 return rval;
1504 }
1505
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,CCrandstate * rstate)1506 int CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques,
1507 int *cliquecount, int ncount, int ecount, int *elist, double *x,
1508 double maxdelta, int maxcliques, double **cliquevals,
1509 CCrandstate *rstate)
1510 {
1511 int rval = 0;
1512 double *cval = (double *) NULL;
1513 int *ind = (int *) NULL;
1514 double upperdelta, lowerdelta;
1515 int i, k;
1516 int ccount = 0;
1517
1518 *cliquecount = 0;
1519 *cliques = (CCtsp_lpclique *) NULL;
1520 if (cliquevals) {
1521 *cliquevals = (double *) NULL;
1522 }
1523
1524 if (pool->cutcount == 0) return 0;
1525
1526 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
1527 if (!cval) {
1528 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1529 rval = 1; goto CLEANUP;
1530 }
1531
1532 rval = price_cliques (pool->cliques, ncount, ecount, elist, x, cval,
1533 pool->cliqueend);
1534 if (rval) {
1535 fprintf (stderr, "price_cliques failed\n");
1536 goto CLEANUP;
1537 }
1538
1539 ind = CC_SAFE_MALLOC (pool->cliqueend, int);
1540 if (!ind) {
1541 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1542 rval = 1; goto CLEANUP;
1543 }
1544 for (i = 0; i < pool->cliqueend; i++) {
1545 ind[i] = i;
1546 }
1547
1548 CCutil_rselect (ind, 0, pool->cliqueend - 1, maxcliques, cval, rstate);
1549
1550 upperdelta = -1.0;
1551 lowerdelta = maxdelta;
1552 for (i = 0; i < pool->cliqueend && i < maxcliques; i++) {
1553 if (cval[ind[i]] < maxdelta) {
1554 ccount++;
1555 if (cval[ind[i]] < lowerdelta) lowerdelta = cval[ind[i]];
1556 if (cval[ind[i]] > upperdelta) upperdelta = cval[ind[i]];
1557 }
1558 }
1559
1560 if (ccount == 0) {
1561 printf ("Found no nearly tight cliques\n"); fflush (stdout);
1562 goto CLEANUP;
1563 }
1564
1565 *cliques = CC_SAFE_MALLOC (ccount, CCtsp_lpclique);
1566 if (!(*cliques)) {
1567 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1568 rval = 1; goto CLEANUP;
1569 }
1570 if (cliquevals) {
1571 *cliquevals = CC_SAFE_MALLOC (ccount, double);
1572 if (!(*cliquevals)) {
1573 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1574 CC_FREE (*cliques, CCtsp_lpclique);
1575 rval = 1; goto CLEANUP;
1576 }
1577 }
1578
1579 ccount = 0;
1580 for (i = 0; i < pool->cliqueend && i < maxcliques; i++) {
1581 if (cval[ind[i]] < maxdelta) {
1582 rval = CCtsp_copy_lpclique (&(pool->cliques[ind[i]]),
1583 &((*cliques)[ccount]));
1584 if (rval) {
1585 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
1586 for (k = 0; k < ccount; k++) {
1587 CC_FREE ((*cliques)[k].nodes, CCtsp_segment);
1588 }
1589 CC_FREE (*cliques, CCtsp_lpclique);
1590 if (cliquevals) {
1591 CC_FREE (*cliquevals, double);
1592 }
1593 goto CLEANUP;
1594 }
1595 if (cliquevals) {
1596 (*cliquevals)[ccount] = cval[ind[i]];
1597 }
1598 ccount++;
1599 }
1600 }
1601 *cliquecount = ccount;
1602
1603 printf ("%d nearly tight cliques found, range (%.3f, %.3f)\n",
1604 *cliquecount, lowerdelta, upperdelta);
1605 fflush (stdout);
1606
1607 CLEANUP:
1608
1609 CC_IFFREE (cval, double);
1610 CC_IFFREE (ind, int);
1611 return rval;
1612 }
1613
1614 #define BRANCH_CLIQUE_GOAL 3.00
1615 #define BRANCH_CLIQUE_TOL 0.99
1616
CCtsp_branch_cutpool_cliques(CCtsp_lpcuts * pool,CCtsp_lpclique ** cliques,int * cliquecount,int ncount,int ecount,int * elist,double * x,int nwant,double ** cliquevals,int silent)1617 int CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques,
1618 int *cliquecount, int ncount, int ecount, int *elist, double *x,
1619 int nwant, double **cliquevals, int silent)
1620 {
1621 int rval = 0;
1622 double *cval = (double *) NULL;
1623 double upperdelta, lowerdelta;
1624 double t;
1625 int i, k;
1626 int ccount = 0;
1627 int *blist = (int *) NULL;
1628 double *bval = (double *) NULL;
1629
1630 *cliquecount = 0;
1631 *cliques = (CCtsp_lpclique *) NULL;
1632 if (cliquevals) {
1633 *cliquevals = (double *) NULL;
1634 }
1635
1636 if (pool->cutcount == 0 || nwant <= 0) return 0;
1637
1638 blist = CC_SAFE_MALLOC (nwant + 1, int);
1639 bval = CC_SAFE_MALLOC (nwant + 1, double);
1640 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
1641 if (!blist || !bval || !cval) {
1642 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1643 rval = 1; goto CLEANUP;
1644 }
1645
1646 rval = price_cliques (pool->cliques, ncount, ecount, elist, x, cval,
1647 pool->cliqueend);
1648 if (rval) {
1649 fprintf (stderr, "price_cliques failed\n");
1650 goto CLEANUP;
1651 }
1652
1653 for (i = 0; i < nwant; i++) {
1654 blist[i] = -1;
1655 bval[i] = CCtsp_LP_MAXDOUBLE;
1656 }
1657 blist[nwant] = -1;
1658 bval[i] = -1.0;
1659
1660 for (i = 0; i < pool->cliqueend; i++) {
1661 t = CC_OURABS (BRANCH_CLIQUE_GOAL - cval[i]);
1662 if (t < bval[0] && t < BRANCH_CLIQUE_TOL) {
1663 for (k = 0; t < bval[k+1]; k++) {
1664 blist[k] = blist[k+1];
1665 bval[k] = bval[k+1];
1666 }
1667 blist[k] = i;
1668 bval[k] = t;
1669 }
1670 }
1671
1672 upperdelta = -1.0;
1673 lowerdelta = CCtsp_LP_MAXDOUBLE;
1674 for (i = 0; i < nwant; i++) {
1675 if (blist[i] != -1) {
1676 if (upperdelta < cval[blist[i]]) {
1677 upperdelta = cval[blist[i]];
1678 }
1679 if (lowerdelta > cval[blist[i]]) {
1680 lowerdelta = cval[blist[i]];
1681 }
1682 ccount++;
1683 }
1684 }
1685
1686 if (ccount == 0) {
1687 printf ("Found no nearly tight cliques\n"); fflush (stdout);
1688 goto CLEANUP;
1689 }
1690
1691 *cliques = CC_SAFE_MALLOC (ccount, CCtsp_lpclique);
1692 if (!(*cliques)) {
1693 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1694 rval = 1; goto CLEANUP;
1695 }
1696 if (cliquevals) {
1697 *cliquevals = CC_SAFE_MALLOC (ccount, double);
1698 if (!(*cliquevals)) {
1699 fprintf (stderr, "out of memory in CCtsp_search_cutpool_cliques\n");
1700 CC_FREE (*cliques, CCtsp_lpclique);
1701 rval = 1; goto CLEANUP;
1702 }
1703 }
1704
1705 ccount = 0;
1706 for (i = nwant - 1; i >= 0; i--) {
1707 if (blist[i] != -1) {
1708 rval = CCtsp_copy_lpclique (&(pool->cliques[blist[i]]),
1709 &((*cliques)[ccount]));
1710 if (rval) {
1711 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
1712 for (k = 0; k < ccount; k++) {
1713 CC_FREE ((*cliques)[k].nodes, CCtsp_segment);
1714 }
1715 CC_FREE (*cliques, CCtsp_lpclique);
1716 if (cliquevals) {
1717 CC_FREE (*cliquevals, double);
1718 }
1719 goto CLEANUP;
1720 }
1721 if (cliquevals) {
1722 (*cliquevals)[ccount] = cval[blist[i]];
1723 }
1724 ccount++;
1725 }
1726 }
1727 *cliquecount = ccount;
1728
1729 if (!silent) {
1730 printf ("%d candidate branching cliques, range (%.3f, %.3f)\n",
1731 *cliquecount, lowerdelta, upperdelta);
1732 fflush (stdout);
1733 }
1734
1735
1736 CLEANUP:
1737
1738 CC_IFFREE (blist, int);
1739 CC_IFFREE (bval, double);
1740 CC_IFFREE (cval, double);
1741 return rval;
1742 }
1743
CCtsp_get_clique_prices(CCtsp_lpcuts * pool,int ** p_cliquenums,double ** p_cliquevals,double mindelta,double maxdelta,int * p_cliquecount,int ncount,int ecount,int * elist,double * x)1744 int CCtsp_get_clique_prices (CCtsp_lpcuts *pool, int **p_cliquenums,
1745 double **p_cliquevals, double mindelta, double maxdelta,
1746 int *p_cliquecount, int ncount, int ecount, int *elist, double *x)
1747 {
1748 double *cval = (double *) NULL;
1749 int i;
1750 int rval;
1751 int cliquecount = 0;
1752 int *cliquenums = (int *) NULL;
1753 double *cliquevals = (double *) NULL;
1754
1755 if (p_cliquevals) *p_cliquevals = (double *) NULL;
1756 *p_cliquenums = (int *) NULL;
1757 *p_cliquecount = 0;
1758
1759 if (pool->cutcount == 0) return 0;
1760
1761 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
1762 if (cval == (double *) NULL) {
1763 fprintf (stderr, "Out of memory in CCtsp_get_clique_prices\n");
1764 rval = 1; goto CLEANUP;
1765 }
1766
1767 rval = price_cliques (pool->cliques, ncount, ecount, elist, x, cval,
1768 pool->cliqueend);
1769 if (rval) {
1770 fprintf (stderr, "price_cliques failed\n");
1771 goto CLEANUP;
1772 }
1773
1774 cliquecount = 0;
1775 for (i=0; i<pool->cliqueend; i++) {
1776 if (pool->cliques[i].segcount > 0 &&
1777 cval[i] >= mindelta && cval[i] <= maxdelta) {
1778 cliquecount++;
1779 }
1780 }
1781
1782 if (cliquecount == 0) {
1783 rval = 0; goto CLEANUP;
1784 }
1785
1786 cliquenums = CC_SAFE_MALLOC (cliquecount, int);
1787 if (cliquenums == (int *) NULL) {
1788 fprintf (stderr, "Out of memory in CCtsp_get_clique_prices\n");
1789 rval = 1; goto CLEANUP;
1790 }
1791
1792 if (p_cliquevals) {
1793 cliquevals = CC_SAFE_MALLOC (cliquecount, double);
1794 if (cliquevals == (double *) NULL) {
1795 fprintf (stderr, "Out of memory in CCtsp_get_clique_prices\n");
1796 rval = 1; goto CLEANUP;
1797 }
1798 }
1799
1800 cliquecount = 0;
1801 for (i=0; i<pool->cliqueend; i++) {
1802 if (pool->cliques[i].segcount > 0 &&
1803 cval[i] >= mindelta && cval[i] <= maxdelta) {
1804 cliquenums[cliquecount] = i;
1805 if (cliquevals) cliquevals[cliquecount] = cval[i];
1806 cliquecount++;
1807 }
1808 }
1809
1810 rval = 0;
1811
1812 CLEANUP:
1813
1814 if (rval) {
1815 CC_IFFREE (cliquenums, int);
1816 CC_IFFREE (cliquevals, double);
1817 cliquecount = 0;
1818 }
1819 CC_IFFREE (cval, double);
1820 *p_cliquenums = cliquenums;
1821 if (p_cliquevals) *p_cliquevals = cliquevals;
1822 *p_cliquecount = cliquecount;
1823 return rval;
1824 }
1825
CCtsp_get_clique(CCtsp_lpcuts * pool,int cliquenum,CCtsp_lpclique ** p_clique)1826 int CCtsp_get_clique (CCtsp_lpcuts *pool, int cliquenum,
1827 CCtsp_lpclique **p_clique)
1828 {
1829 if (cliquenum < 0 || cliquenum >= pool->cliqueend ||
1830 pool->cliques[cliquenum].segcount <= 0) {
1831 fprintf (stderr, "Illegal cliquenum in CCtsp_get_clique\n");
1832 return -1;
1833 }
1834 *p_clique = &pool->cliques[cliquenum];
1835 return 0;
1836 }
1837
CCtsp_add_to_cutpool(CCtsp_lpcuts * pool,CCtsp_lpcuts * cuts,CCtsp_lpcut * c)1838 int CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts,
1839 CCtsp_lpcut *c)
1840 {
1841 int rval = 0;
1842 CCtsp_lpcut_in cin;
1843
1844 if (!c || c->cliquecount <= 1)
1845 return 0;
1846
1847 CCtsp_init_lpcut_in (&cin);
1848
1849 rval = CCtsp_lpcut_to_lpcut_in (cuts, c, &cin);
1850 if (rval) {
1851 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
1852 goto CLEANUP;
1853 }
1854
1855 rval = CCtsp_add_to_cutpool_lpcut_in (pool, &cin);
1856 if (rval) {
1857 fprintf (stderr, "CCtsp_add_to_cutpool_lpcut_in failed\n");
1858 goto CLEANUP;
1859 }
1860
1861 CLEANUP:
1862
1863 CCtsp_free_lpcut_in (&cin);
1864 return rval;
1865 }
1866
CCtsp_add_to_dominopool(CCtsp_lpcuts * pool,CCtsp_lpcuts * cuts,CCtsp_lpcut * c)1867 int CCtsp_add_to_dominopool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts,
1868 CCtsp_lpcut *c)
1869 {
1870 int rval = 0;
1871 CCtsp_lpcut_in cin;
1872
1873 /*
1874 printf ("CCtsp_add_to_dominopool (%d, %d)\n", c->cliquecount,
1875 c->dominocount);
1876 fflush (stdout);
1877 */
1878
1879 if (!pool) {
1880 fprintf (stderr, "NO domino pool!\n");
1881 rval = 1; goto CLEANUP;
1882 }
1883
1884 if (!c) return 0;
1885
1886 CCtsp_init_lpcut_in (&cin);
1887
1888 rval = CCtsp_lpcut_to_lpcut_in (cuts, c, &cin);
1889 if (rval) {
1890 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
1891 goto CLEANUP;
1892 }
1893
1894 rval = CCtsp_add_to_cutpool_lpcut_in (pool, &cin);
1895 if (rval) {
1896 fprintf (stderr, "CCtsp_add_to_cutpool_lpcut_in failed\n");
1897 goto CLEANUP;
1898 }
1899
1900 CLEANUP:
1901
1902 CCtsp_free_lpcut_in (&cin);
1903 return rval;
1904 }
1905
CCtsp_add_to_cutpool_lpcut_in(CCtsp_lpcuts * pool,CCtsp_lpcut_in * cut)1906 int CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool, CCtsp_lpcut_in *cut)
1907 {
1908 int rval = 0;
1909 CCtsp_lpcut new;
1910 int cutloc;
1911 unsigned int hval;
1912
1913 if (!pool) goto CLEANUP;
1914
1915 CCtsp_init_lpcut (&new);
1916
1917 new.rhs = cut->rhs;
1918 new.branch = cut->branch;
1919 new.sense = cut->sense;
1920
1921 rval = CCtsp_register_cliques (pool, cut, &new);
1922 CCcheck_rval (rval, "CCtsp_register_cliques failed");
1923
1924 rval = CCtsp_register_dominos (pool, cut, &new);
1925 CCcheck_rval (rval, "CCtsp_register_dominos failed");
1926
1927 rval = CCtsp_copy_skeleton (&cut->skel, &new.skel);
1928 if (rval) {
1929 fprintf (stderr, "CCtsp_copy_skeleton failed\n");
1930 CCtsp_unregister_cliques (pool, &new);
1931 CCtsp_unregister_dominos (pool, &new);
1932 goto CLEANUP;
1933 }
1934
1935 sort_cliques (&new);
1936 sort_dominos (&new);
1937
1938 cutloc = CCtsp_add_cut_to_cutlist (pool, &new);
1939 if (cutloc < 0) {
1940 fprintf (stderr, "CCtsp_add_cut_to_cutlist failed\n");
1941 CCtsp_unregister_cliques (pool, &new);
1942 CCtsp_unregister_dominos (pool, &new);
1943 rval = cutloc;
1944 goto CLEANUP;
1945 }
1946
1947 hval = CCutil_genhash_hash (pool->cuthash, (void *) ((long) cutloc));
1948 if (CCutil_genhash_lookup_h (pool->cuthash, hval,
1949 (void *) ((long) cutloc))) {
1950 /* cut was already in pool */
1951 CCtsp_delete_cut_from_cutlist (pool, cutloc);
1952 goto CLEANUP;
1953 }
1954
1955 rval = CCutil_genhash_insert_h (pool->cuthash, hval,
1956 (void *) ((long) cutloc), (void *) ((long) 1));
1957 if (rval) {
1958 fprintf (stderr, "CCutil_genhash_insert_h failed\n");
1959 CCtsp_delete_cut_from_cutlist (pool, cutloc);
1960 goto CLEANUP;
1961 }
1962
1963 CLEANUP:
1964
1965 return rval;
1966 }
1967
sort_cliques(CCtsp_lpcut * c)1968 static void sort_cliques (CCtsp_lpcut *c)
1969 {
1970 CCutil_int_array_quicksort (c->cliques, c->cliquecount);
1971 }
1972
sort_dominos(CCtsp_lpcut * c)1973 static void sort_dominos (CCtsp_lpcut *c)
1974 {
1975 CCutil_int_array_quicksort (c->dominos, c->dominocount);
1976 }
1977
1978
register_lpcuts(CCtsp_lpcuts * pool)1979 static int register_lpcuts (CCtsp_lpcuts *pool)
1980 {
1981 int i;
1982 unsigned int hval;
1983 int rval = 0;
1984 int ndup = 0;
1985
1986 for (i=0; i<pool->cutcount; i++) {
1987 sort_cliques (&pool->cuts[i]);
1988 sort_dominos (&pool->cuts[i]);
1989 hval = CCutil_genhash_hash (pool->cuthash, (void *) ((long) i));
1990 if (CCutil_genhash_lookup_h (pool->cuthash, hval,
1991 (void *) ((long) i))) {
1992 ndup++;
1993 } else {
1994 rval = CCutil_genhash_insert_h (pool->cuthash, hval,
1995 (void *) ((long) i), (void *) ((long) 1));
1996 if (rval) {
1997 fprintf (stderr, "CCutil_genhash_insert_h failed\n");
1998 return rval;
1999 }
2000 }
2001 }
2002 if (ndup) {
2003 printf ("%d duplicates detected in pool\n", ndup);
2004 fflush (stdout);
2005 }
2006 return 0;
2007 }
2008
CCtsp_display_cutpool(CCtsp_lpcuts * pool)2009 int CCtsp_display_cutpool (CCtsp_lpcuts *pool)
2010 {
2011 int i;
2012 CCtsp_lpcut_in c;
2013
2014 for (i = 0; i < pool->cutcount; i++) {
2015 if (CCtsp_lpcut_to_lpcut_in (pool, &(pool->cuts[i]), &c)) {
2016 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
2017 return 1;
2018 }
2019 CCtsp_print_lpcut_in (&c);
2020 CCtsp_free_lpcut_in (&c);
2021 }
2022
2023 return 0;
2024 }
2025
CCtsp_price_cuts(CCtsp_lpcuts * pool,int ncount,int ecount,int * elist,double * x,double * cutval)2026 int CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount,
2027 int *elist, double *x, double *cutval)
2028 {
2029 double *cval = (double *) NULL;
2030 int rval = 0;
2031
2032 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
2033 CCcheck_NULL (cval, "out of memory in CCtsp_price_cuts");
2034
2035 rval = price_cliques (pool->cliques, ncount, ecount, elist, x, cval,
2036 pool->cliqueend);
2037 CCcheck_rval (rval, "price_cliques failed");
2038
2039 price_cuts (pool->cuts, pool->cutcount, cval, cutval);
2040
2041 CLEANUP:
2042
2043 CC_IFFREE (cval, double);
2044 return rval;
2045 }
2046
2047 #ifdef CC_POSIXTHREADS
2048
2049 typedef struct priceclique_args {
2050 CCtsp_lpclique *cliques;
2051 int ncount;
2052 int ecount;
2053 int *elist;
2054 double *x;
2055 double *cval;
2056 int cend;
2057 int rval;
2058 double real_zeit;
2059 } priceclique_args;
2060
2061 typedef struct pricecut_args {
2062 CCtsp_lpcut *cuts;
2063 int cutcount;
2064 double *cval;
2065 double *cutval;
2066 int rval;
2067 double real_zeit;
2068 } pricecut_args;
2069
price_cliques_thread(void * args)2070 static void *price_cliques_thread (void *args)
2071 {
2072 priceclique_args *clargs = (priceclique_args *) args;
2073 double szeit = CCutil_real_zeit();
2074
2075 clargs->rval = price_cliques (clargs->cliques, clargs->ncount,
2076 clargs->ecount, clargs->elist, clargs->x, clargs->cval, clargs->cend);
2077
2078 clargs->real_zeit = CCutil_real_zeit() - szeit;
2079
2080 return clargs;
2081 }
2082
price_cuts_thread(void * args)2083 static void *price_cuts_thread (void *args)
2084 {
2085 pricecut_args *cuargs = (pricecut_args *) args;
2086 double szeit = CCutil_real_zeit();
2087
2088 price_cuts (cuargs->cuts, cuargs->cutcount, cuargs->cval, cuargs->cutval);
2089
2090 cuargs->real_zeit = CCutil_real_zeit() - szeit;
2091 cuargs->rval = 0;
2092
2093 return cuargs;
2094 }
2095
2096 /* rebalance_load makes the (unrealistic) assumption that the worktime
2097 * in each thread was uniformly distributed over the workload for that
2098 * thread.
2099 */
rebalance_load(int nthreads,double * workload,double * worktime,double * work)2100 static void rebalance_load (int nthreads, double *workload, double *worktime,
2101 double *work)
2102 {
2103 double goal;
2104 int i;
2105 int j;
2106 double iload;
2107 double itime;
2108 double jload;
2109 double jtime;
2110
2111 goal = 0.0;
2112 for (i=0; i<nthreads; i++) {
2113 /* try to cope with roundoff in real times */
2114 if (worktime[i] == 0.0) worktime[i] = 1.0;
2115 goal += worktime[i];
2116 }
2117 goal /= nthreads;
2118
2119 i = 0;
2120 j = 0;
2121 jload = workload[j];
2122 jtime = worktime[j];
2123 iload = 0.0;
2124 itime = goal;
2125 while (i < nthreads) {
2126 if (jtime == 0.0 || itime >= jtime) {
2127 itime -= jtime;
2128 iload += jload;
2129 j++;
2130 if (j < nthreads) {
2131 jload = workload[j];
2132 jtime = worktime[j];
2133 } else {
2134 jload = 0.0;
2135 jtime = 1e10;
2136 }
2137 } else {
2138 iload += itime / jtime * jload;
2139 jload -= itime / jtime * jload;
2140 jtime -= itime;
2141 work[i] = iload;
2142 i++;
2143 iload = 0.0;
2144 itime = goal;
2145 }
2146 }
2147
2148 goal = 0.0;
2149 for (i=0; i<nthreads; i++) {
2150 goal += work[i];
2151 }
2152 if (goal == 0.0) goal = 1.0;
2153 for (i=0; i<nthreads; i++) {
2154 workload[i] = work[i] / goal;
2155 }
2156 }
2157
2158 #endif /* CC_POSIXTHREADS */
2159
CCtsp_price_cuts_threaded(CCtsp_lpcuts * pool,int ncount,int ecount,int * elist,double * x,double * cutval,CC_UNUSED int nthreads)2160 int CCtsp_price_cuts_threaded (CCtsp_lpcuts *pool, int ncount, int ecount,
2161 int *elist, double *x, double *cutval, CC_UNUSED int nthreads)
2162 {
2163 #ifndef CC_POSIXTHREADS
2164 return CCtsp_price_cuts (pool, ncount, ecount, elist, x, cutval);
2165 #else /* CC_POSIXTHREADS */
2166 double *cval = (double *) NULL;
2167 priceclique_args *clargs = (priceclique_args *) NULL;
2168 priceclique_args *clrval;
2169 pricecut_args *cuargs = (pricecut_args *) NULL;
2170 pricecut_args *curval;
2171 void *thr_rval;
2172 pthread_t *thread_id = (pthread_t *) NULL;
2173 pthread_attr_t attr;
2174 int cstart;
2175 int cend;
2176 int i;
2177 double *cliqueworkload;
2178 double *cutworkload;
2179 double *worktimes;
2180 double *balancework;
2181 int rval = 0;
2182
2183 if (pool->workloads != (double *) NULL &&
2184 pool->workloads[0] != (double) nthreads) {
2185 CC_FREE (pool->workloads, double);
2186 }
2187
2188 if (pool->workloads == (double *) NULL) {
2189 pool->workloads = CC_SAFE_MALLOC (nthreads*4+1, double);
2190 if (pool->workloads == (double *) NULL) {
2191 fprintf (stderr, "Out of memory in CCtsp_price_cuts_threaded\n");
2192 rval = 1; goto CLEANUP;
2193 }
2194 pool->workloads[0] = (double) nthreads;
2195 cliqueworkload = pool->workloads + 1;
2196 cutworkload = pool->workloads + 1 + nthreads;
2197 for (i=0; i<nthreads; i++) {
2198 cliqueworkload[i] = 1.0 / ((double) nthreads);
2199 cutworkload[i] = 1.0 / ((double) nthreads);
2200 }
2201 }
2202
2203 /* nthreads, two workloads, and worktimes are all packed in workloads */
2204 cliqueworkload = pool->workloads + 1;
2205 cutworkload = pool->workloads + 1 + nthreads;
2206 worktimes = pool->workloads + 1 + nthreads + nthreads;
2207 balancework = pool->workloads + 1 + nthreads + nthreads + nthreads;
2208
2209 cval = CC_SAFE_MALLOC (pool->cliqueend, double);
2210 clargs = CC_SAFE_MALLOC (nthreads, priceclique_args);
2211 cuargs = CC_SAFE_MALLOC (nthreads, pricecut_args);
2212 thread_id = CC_SAFE_MALLOC (nthreads, pthread_t);
2213 if (cval == (double *) NULL ||
2214 clargs == (priceclique_args *) NULL ||
2215 cuargs == (pricecut_args *) NULL ||
2216 thread_id == (pthread_t *) NULL) {
2217 fprintf (stderr, "out of memory in CCtsp_price_cuts\n");
2218 rval = 1; goto CLEANUP;
2219 }
2220
2221 rval = pthread_attr_init (&attr);
2222 if (rval) {
2223 fprintf (stderr, "pthread_attr_init failed, rval %d\n", rval);
2224 rval = 1; goto CLEANUP;
2225 }
2226
2227 #ifdef PTHREAD_CREATE_JOINABLE
2228 rval = pthread_attr_setdetachstate (&attr, PTHREAD_CREATE_JOINABLE);
2229 if (rval) {
2230 fprintf (stderr, "pthread_attr_setdetachstate failed, rval %d\n",
2231 rval);
2232 rval = 1; goto CLEANUP;
2233 }
2234 #else
2235 #ifdef PTHREAD_CREATE_UNDETACHED
2236 rval = pthread_attr_setdetachstate (&attr, PTHREAD_CREATE_UNDETACHED);
2237 if (rval) {
2238 fprintf (stderr, "pthread_attr_setdetachstate failed, rval %d\n",
2239 rval);
2240 rval = 1; goto CLEANUP;
2241 }
2242 #endif
2243 #endif
2244
2245 cstart = 0;
2246 for (i=0; i<nthreads; i++) {
2247 if (i == nthreads-1) {
2248 cend = pool->cliqueend;
2249 } else {
2250 cend = cstart + (int) (cliqueworkload[i] * pool->cliqueend);
2251 }
2252 clargs[i].cliques = pool->cliques + cstart;
2253 clargs[i].ncount = ncount;
2254 clargs[i].ecount = ecount;
2255 clargs[i].elist = elist;
2256 clargs[i].x = x;
2257 clargs[i].cval = cval + cstart;
2258 clargs[i].cend = cend - cstart;
2259 clargs[i].rval = 0;
2260 cstart = cend;
2261 rval = pthread_create (&thread_id[i], &attr, price_cliques_thread,
2262 &clargs[i]);
2263 if (rval) {
2264 perror ("pthread_create");
2265 fprintf (stderr, "pthread_create failed, rval %d\n", rval);
2266 goto CLEANUP;
2267 }
2268 }
2269 for (i=0; i<nthreads; i++) {
2270 rval = pthread_join (thread_id[i], &thr_rval);
2271 if (rval) {
2272 fprintf (stderr, "pthread_join failed\n");
2273 goto CLEANUP;
2274 }
2275 clrval = (priceclique_args *) thr_rval;
2276 if (clrval->rval) {
2277 fprintf (stderr, "pricing clique thread failed\n");
2278 rval = clrval->rval; goto CLEANUP;
2279 }
2280 worktimes[i] = clrval->real_zeit;
2281 }
2282
2283 printf ("\nThread clique:");
2284 for (i=0; i<nthreads; i++) {
2285 printf (" %.0f", worktimes[i]);
2286 }
2287 fflush (stdout);
2288
2289 rebalance_load (nthreads, cliqueworkload, worktimes, balancework);
2290
2291 cstart = 0;
2292 for (i=0; i<nthreads; i++) {
2293 if (i == nthreads-1) {
2294 cend = pool->cutcount;
2295 } else {
2296 cend = cstart + cutworkload[i] * pool->cutcount;
2297 }
2298 cuargs[i].cuts = pool->cuts + cstart;
2299 cuargs[i].cutcount = cend - cstart;
2300 cuargs[i].cval = cval;
2301 cuargs[i].cutval = cutval + cstart;
2302 cuargs[i].rval = 0;
2303 cstart = cend;
2304 rval = pthread_create (&thread_id[i], &attr, price_cuts_thread,
2305 &cuargs[i]);
2306 if (rval) {
2307 fprintf (stderr, "pthread_create failed\n");
2308 goto CLEANUP;
2309 }
2310 }
2311 for (i=0; i<nthreads; i++) {
2312 rval = pthread_join (thread_id[i], &thr_rval);
2313 if (rval) {
2314 fprintf (stderr, "pthread_join failed\n");
2315 goto CLEANUP;
2316 }
2317 curval = (pricecut_args *) thr_rval;
2318 if (curval->rval) {
2319 fprintf (stderr, "pricing cut thread failed\n");
2320 rval = curval->rval; goto CLEANUP;
2321 }
2322 worktimes[i] = curval->real_zeit;
2323 }
2324
2325 printf (" cut:");
2326 for (i=0; i<nthreads; i++) {
2327 printf (" %.0f", worktimes[i]);
2328 }
2329 printf ("\n");
2330 fflush (stdout);
2331
2332 rebalance_load (nthreads, cutworkload, worktimes, balancework);
2333
2334 rval = 0;
2335
2336 CLEANUP:
2337 CC_IFFREE (cval, double);
2338 CC_IFFREE (clargs, priceclique_args);
2339 CC_IFFREE (cuargs, pricecut_args);
2340 CC_IFFREE (thread_id, pthread_t);
2341 return rval;
2342 #endif /* CC_POSIXTHREADS */
2343 }
2344
price_cuts(CCtsp_lpcut * cuts,int cutcount,double * cval,double * cutval)2345 static void price_cuts (CCtsp_lpcut *cuts, int cutcount, double *cval,
2346 double *cutval)
2347 {
2348 int i, j;
2349 CCtsp_lpcut *c;
2350 double v;
2351
2352 for (i = 0, c = cuts; i < cutcount; i++, c++) {
2353 if (c->dominocount == 0) {
2354 v = (double) -(c->rhs);
2355 for (j = 0; j < c->cliquecount; j++) {
2356 v += cval[c->cliques[j]];
2357 }
2358 cutval[i] = v;
2359 } else {
2360 cutval[i] = 1000.0; /* For now, do not price dominos */
2361 /* We can easily add domino pricing, but the parallel */
2362 /* code will be not be so easy, since dominos are */
2363 /* shared among the threads. */
2364 }
2365 }
2366 }
2367
price_cliques(CCtsp_lpclique * cliques,int ncount,int ecount,int * elist,double * x,double * cval,int cend)2368 static int price_cliques (CCtsp_lpclique *cliques, int ncount, int ecount,
2369 int *elist, double *x, double *cval, int cend)
2370 {
2371 poolnode *nlist = (poolnode *) NULL;
2372 pooledge *espace = (pooledge *) NULL;
2373 int marker = 0;
2374 int i;
2375 int rval = 0;
2376
2377 rval = make_pricing_graph (ncount, ecount, elist, x, &nlist, &espace);
2378 if (rval) {
2379 fprintf (stderr, "make_pricing_graph failed\n");
2380 goto CLEANUP;
2381 }
2382 for (i = 0; i < cend; i++) {
2383 if (cliques[i].segcount > 0) {
2384 marker++;
2385 cval[i] = price_clique (nlist, &(cliques[i]), marker);
2386 } else {
2387 cval[i] = -1.0;
2388 }
2389 }
2390
2391 CLEANUP:
2392
2393 CC_IFFREE (nlist, poolnode);
2394 CC_IFFREE (espace, pooledge);
2395 return rval;
2396 }
2397
make_pricing_graph(int ncount,int ecount,int * elist,double * x,poolnode ** p_nlist,pooledge ** p_espace)2398 static int make_pricing_graph (int ncount, int ecount, int *elist, double *x,
2399 poolnode **p_nlist, pooledge **p_espace)
2400 {
2401 poolnode *nlist = (poolnode *) NULL;
2402 pooledge *espace = (pooledge *) NULL;
2403 pooledge *p;
2404 int i;
2405 int count;
2406 int a, b;
2407 int rval;
2408
2409 *p_nlist = (poolnode *) NULL;
2410 *p_espace = (pooledge *) NULL;
2411
2412 nlist = CC_SAFE_MALLOC (ncount, poolnode);
2413 if (nlist == (poolnode *) NULL) {
2414 fprintf (stderr, "out of memory in make_pricing_graph\n");
2415 rval = 1; goto CLEANUP;
2416 }
2417
2418 for (i = 0; i < ncount; i++) {
2419 nlist[i].mark = 0;
2420 nlist[i].deg = 0;
2421 }
2422
2423 count = 0;
2424 for (i = 0; i < ecount; i++) {
2425 if (x[i] >= ZERO_EPSILON) {
2426 nlist[elist[2*i]].deg++;
2427 nlist[elist[2*i+1]].deg++;
2428 count++;
2429 }
2430 }
2431
2432 espace = CC_SAFE_MALLOC (2*count, pooledge);
2433 if (espace == (pooledge *) NULL) {
2434 fprintf (stderr, "out of memory in price_cliques\n");
2435 rval = 1; goto CLEANUP;
2436 }
2437
2438 p = espace;
2439 for (i = 0; i < ncount; i++) {
2440 nlist[i].adj = p;
2441 p += nlist[i].deg;
2442 nlist[i].deg = 0;
2443 }
2444 for (i = 0; i < ecount; i++) {
2445 if (x[i] >= ZERO_EPSILON) {
2446 a = elist[2*i];
2447 b = elist[2*i+1];
2448 nlist[a].adj[nlist[a].deg].x = x[i];
2449 nlist[a].adj[nlist[a].deg++].to = b;
2450 nlist[b].adj[nlist[b].deg].x = x[i];
2451 nlist[b].adj[nlist[b].deg++].to = a;
2452 }
2453 }
2454
2455 *p_nlist = nlist;
2456 *p_espace = espace;
2457
2458 rval = 0;
2459 CLEANUP:
2460 if (rval) {
2461 CC_IFFREE (nlist, poolnode);
2462 CC_IFFREE (espace, pooledge);
2463 }
2464 return rval;
2465 }
2466
price_clique(poolnode * nlist,CCtsp_lpclique * c,int marker)2467 static double price_clique (poolnode *nlist, CCtsp_lpclique *c, int marker)
2468 {
2469 double val = 0.0;
2470 poolnode *n;
2471 int tmp, j, k;
2472
2473 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
2474 nlist[j].mark = marker;
2475 }
2476 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
2477 n = &(nlist[j]);
2478 for (k = 0; k < n->deg; k++) {
2479 if (nlist[n->adj[k].to].mark != marker) {
2480 val += n->adj[k].x;
2481 }
2482 }
2483 }
2484 return val;
2485 }
2486
CCtsp_free_lpcut_in(CCtsp_lpcut_in * c)2487 void CCtsp_free_lpcut_in (CCtsp_lpcut_in *c)
2488 {
2489 int i;
2490
2491 if (c != (CCtsp_lpcut_in *) NULL) {
2492 if (c->cliques != (CCtsp_lpclique *) NULL) {
2493 for (i = 0; i < c->cliquecount; i++) {
2494 CCtsp_free_lpclique (&c->cliques[i]);
2495 }
2496 CC_IFFREE (c->cliques, CCtsp_lpclique);
2497 }
2498 if (c->dominos != (CCtsp_lpdomino *) NULL) {
2499 for (i = 0; i < c->dominocount; i++) {
2500 CCtsp_free_lpdomino (&c->dominos[i]);
2501 }
2502 CC_IFFREE (c->dominos, CCtsp_lpdomino);
2503 }
2504 CCtsp_free_skeleton (&c->skel);
2505 }
2506 }
2507
CCtsp_free_lpclique(CCtsp_lpclique * c)2508 void CCtsp_free_lpclique (CCtsp_lpclique *c)
2509 {
2510 if (c) {
2511 CC_IFFREE (c->nodes, CCtsp_segment);
2512 c->segcount = 0;
2513 c->hashnext = 0;
2514 c->refcount = 0;
2515 }
2516 }
2517
CCtsp_free_lpdomino(CCtsp_lpdomino * c)2518 void CCtsp_free_lpdomino (CCtsp_lpdomino *c)
2519 {
2520 if (c) {
2521 CCtsp_free_lpclique (&(c->sets[0]));
2522 CCtsp_free_lpclique (&(c->sets[1]));
2523 c->hashnext = 0;
2524 c->refcount = 0;
2525 }
2526 }
2527
CCtsp_register_cliques(CCtsp_lpcuts * cuts,CCtsp_lpcut_in * c,CCtsp_lpcut * new)2528 int CCtsp_register_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c,
2529 CCtsp_lpcut *new)
2530 {
2531 int i, j;
2532
2533 new->cliques = CC_SAFE_MALLOC (c->cliquecount, int);
2534 if (!new->cliques) return 1;
2535 new->cliquecount = c->cliquecount;
2536 for (i = 0; i < c->cliquecount; i++) {
2537 new->cliques[i] = CCtsp_register_clique (cuts, &c->cliques[i]);
2538 if (new->cliques[i] == -1) {
2539 for (j=0; j<i; j++) {
2540 CCtsp_unregister_clique (cuts, new->cliques[j]);
2541 }
2542 CC_FREE (new->cliques, int);
2543 return 1;
2544 }
2545 }
2546 return 0;
2547 }
2548
CCtsp_unregister_cliques(CCtsp_lpcuts * cuts,CCtsp_lpcut * c)2549 void CCtsp_unregister_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut *c)
2550 {
2551 int i;
2552
2553 for (i = 0; i < c->cliquecount; i++) {
2554 CCtsp_unregister_clique (cuts, c->cliques[i]);
2555 }
2556 CC_FREE (c->cliques, int);
2557 c->cliquecount = 0;
2558 }
2559
CCtsp_register_dominos(CCtsp_lpcuts * cuts,CCtsp_lpcut_in * c,CCtsp_lpcut * new)2560 int CCtsp_register_dominos (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c,
2561 CCtsp_lpcut *new)
2562 {
2563 int i, j;
2564
2565 if (c->dominocount > 0 ) {
2566 new->dominos = CC_SAFE_MALLOC (c->dominocount, int);
2567 if (!new->dominos) return 1;
2568 new->dominocount = c->dominocount;
2569 for (i = 0; i < c->dominocount; i++) {
2570 new->dominos[i] = CCtsp_register_domino (cuts, &c->dominos[i]);
2571 if (new->dominos[i] == -1) {
2572 for (j=0; j<i; j++) {
2573 CCtsp_unregister_domino (cuts, new->dominos[j]);
2574 }
2575 CC_FREE (new->dominos, int);
2576 return 1;
2577 }
2578 }
2579 }
2580 return 0;
2581 }
2582
CCtsp_unregister_dominos(CCtsp_lpcuts * cuts,CCtsp_lpcut * c)2583 void CCtsp_unregister_dominos (CCtsp_lpcuts *cuts, CCtsp_lpcut *c)
2584 {
2585 int i;
2586
2587 if (c->dominocount > 0 ) {
2588 for (i = 0; i < c->dominocount; i++) {
2589 CCtsp_unregister_domino (cuts, c->dominos[i]);
2590 }
2591 CC_FREE (c->dominos, int);
2592 c->dominocount = 0;
2593 }
2594 }
2595
CCtsp_add_cut_to_cutlist(CCtsp_lpcuts * cuts,CCtsp_lpcut * c)2596 int CCtsp_add_cut_to_cutlist (CCtsp_lpcuts *cuts, CCtsp_lpcut *c)
2597 {
2598 if (cuts->cutcount >= cuts->cutspace) {
2599 if (CCutil_reallocrus_scale ((void **) &cuts->cuts, &cuts->cutspace,
2600 cuts->cutcount + 1, 1.3, sizeof (CCtsp_lpcut))) {
2601 return -1;
2602 }
2603 }
2604 cuts->cuts[cuts->cutcount] = *c;
2605 return cuts->cutcount++;
2606 }
2607
CCtsp_delete_cut_from_cutlist(CCtsp_lpcuts * cuts,int ind)2608 void CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts *cuts, int ind)
2609 {
2610 int i;
2611
2612 /*
2613 printf ("CCtsp_delete_cut_from_cutlist (%d)\n",
2614 cuts->cuts[ind].dominocount);
2615 fflush (stdout);
2616 */
2617
2618 CCtsp_unregister_cliques (cuts, &cuts->cuts[ind]);
2619 CCtsp_unregister_dominos (cuts, &cuts->cuts[ind]);
2620 CC_IFFREE (cuts->cuts[ind].mods, CCtsp_sparser);
2621 CCtsp_free_skeleton (&cuts->cuts[ind].skel);
2622 for (i = ind+1; i < cuts->cutcount; i++) {
2623 cuts->cuts[i-1] = cuts->cuts[i];
2624 }
2625 cuts->cutcount--;
2626 }
2627