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 /* THE CONTROLLER FOR CUTTING PLANES */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: June 27, 1997 */
25 /* */
26 /* EXPORTED FUNCTIONS: */
27 /* */
28 /* void CCtsp_init_cutselect (CCtsp_cutselect *s) */
29 /* INITIALIZES the cut selections */
30 /* */
31 /* void CCtsp_cutselect_dominos (CCtsp_cutselect *s, int domsel) */
32 /* SETS the domino field according to value of domsel */
33 /* */
34 /* void CCtsp_cutselect_tighten (CCtsp_cutselect *s, int tighten) */
35 /* SETS the usetighten field according to value of tighten */
36 /* */
37 /* void CCtsp_cutselect_chunksize (CCtsp_cutselect *s, int chunksize) */
38 /* SETS the maxchunksize filed according to value of chunksize */
39 /* */
40 /* void CCtsp_cutselect_filecuts (CCtsp_cutselect *s, char *fname) */
41 /* SETS the cutselector to read cuts from file fname */
42 /* */
43 /* void CCtsp_cutselect_remotepool (CCtsp_cutselect *s, char *cutbossname) */
44 /* SETS the cutselector to use the specified cutboss */
45 /* */
46 /* void CCtsp_cutselect_domboss (CCtsp_cutselect *s, char *dombossname) */
47 /* SETS the cutselector to use the specified domino boss */
48 /* */
49 /* void CCtsp_init_tentative_cutselect (CCtsp_cutselect *s) */
50 /* INITIALIZES the cut selections for tenative branching */
51 /* */
52 /* int CCtsp_cutselect_set_tols (CCtsp_cutselect *s, CCtsp_lp *lp, */
53 /* int level, int silent) */
54 /* SETS the tolerances for the cut selections */
55 /* -level should be set to 0 for tentative cutting */
56 /* NOTES: The lp should be solved before this call. */
57 /* */
58 /* int CCtsp_cutting_multiple_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, */
59 /* int savelp, int maxlocal, int update_tol, int silent, */
60 /* CCrandstate *rstate) */
61 /* CALLS CCtsp_cutting_loop multiple times, incrementing maxchunksize */
62 /* from 16 up to maxlocal, going up by 4 each time. */
63 /* */
64 /* int CCtsp_cutting_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, */
65 /* int savelp, int silent, CCrandstate *rstate) */
66 /* CALLS the cutting plane and pricing routines. */
67 /* -sel should be set with the desired cut selection. */
68 /* -savelp should be set to a nonzero value to write the lps to after */
69 /* rounds of cuts */
70 /* -silent turns off most output if set to a nonzero value */
71 /* NOTES: It returns a 2 if the lp becomes infeasible */
72 /* */
73 /* int CCtsp_subtour_loop (CCtsp_lp *lp, int silent, */
74 /* CCrandstate *rstate) */
75 /* CALLS the cutting and pricing to optimize over the subtour polytope. */
76 /* */
77 /* int CCtsp_blossom_loop (CCtsp_lp *lp, int silent, */
78 /* CCrandstate *rstate) */
79 /* CALLS the cutting and pricing to optimize over the blossom polytope. */
80 /* */
81 /* int CCtsp_subtour_and_blossom_loop (CCtsp_lp *lp, int silent, */
82 /* CCrandstate *rstate) */
83 /* CALLS the cutting and princing to optimize over subtours and */
84 /* trivial blossoms. */
85 /* */
86 /* int CCtsp_pricing_loop (CCtsp_lp *lp, double *bnd, int silent, */
87 /* CCrandstate *rstate) */
88 /* ADDS negative reduced costs edges to lp and returns the current */
89 /* lowerbound. */
90 /* -bnd can be NULL */
91 /* NOTES: The LP must have full_edges_valid. */
92 /* */
93 /* int CCtsp_call_x_heuristic (CCtsp_lp *lp, double *val, int *outcyc, */
94 /* int silent, CCrandstate *rstate) */
95 /* CALLS the x-greedy LK heuristic with the current LP solution. */
96 /* -val returns the length of the tour. */
97 /* -outcyc will return the tour in node-node-node format if the */
98 /* length of the tour is less than lp->upperbound; the array should */
99 /* at least of length ncount (it can be NULL) */
100 /* */
101 /* int CCtsp_bb_cutting (char *probname, int probnum, int prob_newnum, */
102 /* int ncount, CCdatagroup *dat, int *ptour, double *upbound, */
103 /* CCtsp_lpcuts *pool, CCtsp_cutselect *sel, double *val, */
104 /* int *prune, int *foundtour, int *besttour, int level, */
105 /* int silent, CCrandstate *rstate) */
106 /* CALLS the cutting loop after reading the lp; writes the result to */
107 /* prob file prob_newnum; using exact price to verify pruned runs */
108 /* -upbound should be passed in as the current bound; if a better */
109 /* tour is found then upbound will be updated */
110 /* -val returns the lp bound; it is CCtsp_LP_MAXDOUBLE if infeasible */
111 /* -prune is set to 1 if bbnode can be pruned */
112 /* -foundtour is set to 1 if a better tour is found. */
113 /* -besttour (if not NULL) will return a better tour if one is found. */
114 /* -level should be set to 0 for tentative cutting */
115 /* */
116 /****************************************************************************/
117
118 #include "machdefs.h"
119 #include "util.h"
120 #include "tsp.h"
121 #include "bigguy.h"
122 #include "cut.h"
123 #include "pq.h"
124 #include "cuttree.h"
125 #include "consec1.h"
126 #include "necklace.h"
127 #include "localcut.h"
128 #if 0
129 #include "verify.h"
130 #endif
131
132 #define BIX_CHUNKS
133 #undef DAVE_CHUNKS
134 #undef OLD_CHUNKS
135 #undef CUTTREE_DISPLAY
136 #undef POLISHED_CHUNKS
137
138 static int
139 call_add_cuts (CCtsp_lp *lp, CCtsp_lpcut_in **cuts, int *cut_added,
140 int *xcount, int **xlist, double **x, double *val, int tighten,
141 int *istour, int silent, CCrandstate *rstate),
142 lp_value (CCtsp_lp *lp, double *val),
143 lp_x (CCtsp_lp *lp, int *xcount, int **xlist, double **x),
144 full_edge_check (CCtsp_lp *lp, int *nadded, int silent,
145 CCrandstate *rstate),
146 sparse_edge_check (CCtsp_lp *lp, CCtsp_edgegenerator *eg, int *nadded,
147 double *bnd, int silent, CCrandstate *rstate),
148 bb_cutting_work (CCtsp_lp **lp, char *probname, int probnum,
149 int ncount, CCdatagroup *dat, int *ptour, double upbound,
150 CCtsp_lpcuts *pool, CCtsp_cutselect *sel, double *val, int level,
151 int silent, CCrandstate *rstate),
152 grab_close_x (int ncount, int xcount, int *xlist, double *x,
153 int *newcount, int **newlist, double **newx, double mult),
154 no_tighten (int ncount, int xcount, int *xlist, double *x, int *test,
155 double tol),
156 CC_UNUSED grab_polished_x (CCtsp_lp *lp, double dust_val, int *newcount,
157 int **newlist, double **newx),
158 CC_UNUSED grab_polished2_x (CCtsp_lp *lp, double dust_val, int *newcount,
159 int **newlist, double **newx);
160
161
162
CCtsp_init_cutselect(CCtsp_cutselect * s)163 void CCtsp_init_cutselect (CCtsp_cutselect *s)
164 {
165 s->cutpool = 1; /* 1 */
166 s->remotepool = 0;
167 s->remotehost = (char *) NULL;
168 s->remoteport = 0;
169 s->domboss = 0;
170 s->dombosshost = (char *) NULL;
171 s->connect = 1; /* 1 */
172 s->segments = 1; /* 1 */
173 s->blockcombs = 1; /* 1 */
174 s->growcombs = 0; /* 0 */
175 s->prclique = 0; /* 0 */
176 s->exactsubtour = 1; /* 1 */
177 s->exactblossom = 0; /* 0 */
178 s->tighten_lp = 1; /* 1 */
179 s->teething_lp = 1; /* 1 */
180 s->tighten_pool = 0; /* 0 */ /* Slow when pool is large */
181 s->teething_pool = 0; /* 0 */
182 s->cliquetree_lp = 0; /* 0 */
183 s->fastblossom = 1; /* 1 */
184 s->ghfastblossom = 1; /* 1 */
185 s->consecutiveones = 1; /* 1 */ /* Slow on large instances */
186 s->necklace = 0; /* 0 */ /* Uses a big chunk of memory */
187 s->usetighten = 0; /* 0 */
188 s->extra_connect = 0; /* 0 */
189 s->decker_lp = 1; /* 1 */
190 s->decker_pool = 0; /* 0 */
191 s->star_lp = 0; /* 0 */ /* Slow on very large instances */
192 s->star_pool = 0; /* 0 */ /* Slow on most instances */
193 s->handling_lp = 1; /* 1 */
194 s->handling_pool = 0; /* 0 */
195 s->maxchunksize = 16; /* 16 */
196 s->filecuts = 0; /* 0 */
197 s->filecutname = (char *) NULL;
198 s->nexttol = 0.0;
199 s->roundtol = 0.0;
200 s->dominos = 0;
201 s->shrunk_dominos = 0;
202 s->fastcuts = 0; /* Keep this at 0 (changes tols) */
203 }
204
CCtsp_cutselect_dominos(CCtsp_cutselect * s,int domsel)205 void CCtsp_cutselect_dominos (CCtsp_cutselect *s, int domsel)
206 {
207 if (domsel == 1 || domsel == 3) s->dominos = 1;
208 if (domsel == 2 || domsel == 3) s->shrunk_dominos = 1;
209 }
210
CCtsp_cutselect_tighten(CCtsp_cutselect * s,int tighten)211 void CCtsp_cutselect_tighten (CCtsp_cutselect *s, int tighten)
212 {
213 s->usetighten = tighten;
214 }
215
CCtsp_cutselect_chunksize(CCtsp_cutselect * s,int chunksize)216 void CCtsp_cutselect_chunksize (CCtsp_cutselect *s, int chunksize)
217 {
218 s->maxchunksize = chunksize;
219 }
220
CCtsp_cutselect_filecuts(CCtsp_cutselect * s,char * fname)221 void CCtsp_cutselect_filecuts (CCtsp_cutselect *s, char *fname)
222 {
223 s->filecuts = 1;
224 s->filecutname = fname;
225 }
226
CCtsp_cutselect_remotepool(CCtsp_cutselect * s,char * cutbossname)227 void CCtsp_cutselect_remotepool (CCtsp_cutselect *s, char *cutbossname)
228 {
229 s->remotepool = 1;
230 s->remotehost = cutbossname;
231 s->remoteport = CCtsp_CUT_PORT;
232 }
233
CCtsp_cutselect_domboss(CCtsp_cutselect * s,char * dombossname)234 void CCtsp_cutselect_domboss (CCtsp_cutselect *s, char *dombossname)
235 {
236 s->domboss = 1;
237 s->dombosshost = dombossname;
238 }
239
CCtsp_init_tentative_cutselect(CCtsp_cutselect * s)240 void CCtsp_init_tentative_cutselect (CCtsp_cutselect *s)
241 {
242 s->cutpool = 1;
243 s->remotepool = 0;
244 s->remotehost = (char *) NULL;
245 s->remoteport = 0;
246 s->domboss = 0;
247 s->dombosshost = (char *) NULL;
248 s->connect = 1;
249 s->segments = 1;
250 s->blockcombs = 1;
251 s->growcombs = 0;
252 s->prclique = 0;
253 s->exactsubtour = 1;
254 s->exactblossom = 0;
255 s->tighten_lp = 1;
256 s->teething_lp = 1;
257 s->tighten_pool = 0;
258 s->teething_pool = 0;
259 s->cliquetree_lp = 0;
260 s->fastblossom = 1;
261 s->ghfastblossom = 1;
262 s->consecutiveones = 0;
263 s->necklace = 0; /* 1 */
264 s->usetighten = 1;
265 s->extra_connect = 0;
266 s->decker_lp = 1;
267 s->decker_pool = 0;
268 s->star_lp = 1;
269 s->star_pool = 0;
270 s->handling_lp = 1;
271 s->handling_pool = 0;
272 s->maxchunksize = 0;
273 s->filecuts = 0;
274 s->filecutname = (char *) NULL;
275 s->nexttol = 0.0;
276 s->roundtol = 0.0;
277 s->dominos = 0;
278 s->shrunk_dominos = 0;
279 s->fastcuts = 0;
280 }
281
CCtsp_init_simple_cutselect(CCtsp_cutselect * s)282 void CCtsp_init_simple_cutselect (CCtsp_cutselect *s)
283 {
284 s->cutpool = 0;
285 s->remotepool = 0;
286 s->remotehost = (char *) NULL;
287 s->remoteport = 0;
288 s->domboss = 0;
289 s->dombosshost = (char *) NULL;
290 s->connect = 1;
291 s->segments = 1;
292 s->blockcombs = 0;
293 s->growcombs = 0;
294 s->prclique = 0;
295 s->exactsubtour = 0;
296 s->exactblossom = 0;
297 s->tighten_lp = 1;
298 s->teething_lp = 0;
299 s->tighten_pool = 0;
300 s->teething_pool = 0;
301 s->cliquetree_lp = 0;
302 s->fastblossom = 0;
303 s->ghfastblossom = 0;
304 s->consecutiveones = 0;
305 s->necklace = 0;
306 s->usetighten = 0;
307 s->extra_connect = 0;
308 s->decker_lp = 1;
309 s->decker_pool = 0;
310 s->star_lp = 0;
311 s->star_pool = 0;
312 s->handling_lp = 0;
313 s->handling_pool = 0;
314 s->maxchunksize = 0;
315 s->filecuts = 0;
316 s->filecutname = (char *) NULL;
317 s->nexttol = 0.0;
318 s->roundtol = 0.0;
319 s->dominos = 0;
320 s->shrunk_dominos = 0;
321 s->fastcuts = 0;
322 }
323
CCtsp_init_fast_cutselect(CCtsp_cutselect * s)324 void CCtsp_init_fast_cutselect (CCtsp_cutselect *s)
325 {
326 s->cutpool = 0;
327 s->remotepool = 0;
328 s->remotehost = (char *) NULL;
329 s->remoteport = 0;
330 s->domboss = 0;
331 s->dombosshost = (char *) NULL;
332 s->connect = 1;
333 s->segments = 1;
334 s->blockcombs = 1;
335 s->growcombs = 0;
336 s->prclique = 0;
337 s->exactsubtour = 1;
338 s->exactblossom = 0;
339 s->tighten_lp = 1;
340 s->teething_lp = 0;
341 s->tighten_pool = 0;
342 s->teething_pool = 0;
343 s->cliquetree_lp = 0;
344 s->fastblossom = 1;
345 s->ghfastblossom = 1;
346 s->consecutiveones = 0;
347 s->necklace = 0;
348 s->usetighten = 0;
349 s->extra_connect = 0;
350 s->decker_lp = 1;
351 s->decker_pool = 0;
352 s->star_lp = 0;
353 s->star_pool = 0;
354 s->handling_lp = 0;
355 s->handling_pool = 0;
356 s->maxchunksize = 0;
357 s->filecuts = 0;
358 s->filecutname = (char *) NULL;
359 s->nexttol = 0.0;
360 s->roundtol = 0.0;
361 s->dominos = 0;
362 s->shrunk_dominos = 0;
363 s->fastcuts = 1;
364 }
365
CCtsp_cutselect_set_tols(CCtsp_cutselect * s,CCtsp_lp * lp,int level,int silent)366 int CCtsp_cutselect_set_tols (CCtsp_cutselect *s, CCtsp_lp *lp, int level,
367 int silent)
368 {
369 double ub, lb, beta;
370 int rval;
371
372 rval = CCtsp_get_lp_result (lp, &lb, &ub, (int *) NULL,
373 (int **) NULL, (double **) NULL, (double **) NULL,
374 (double **) NULL, (double **) NULL);
375 if (rval) {
376 fprintf (stderr, "CCtsp_get_lp_result failed\n"); return rval;
377 }
378
379 #ifdef CCtsp_CUTS_DELTA
380 if (ub - lb < 1.0) {
381 beta = 1.0;
382 } else {
383 if (ub > 2*lb) beta = lb;
384 else beta = ub - lb;
385 }
386 #else
387 if (ub > 2*lb) beta = lb;
388 else beta = ub;
389 #endif
390
391 if (level == -1) {
392 s->nexttol = 10.0 * CCtsp_TENTATIVE_CUTS_NEXT_TOL * beta;
393 s->roundtol = 10.0 * CCtsp_TENTATIVE_CUTS_NEXT_ROUND * beta;
394 } else if (level == 0) {
395 s->nexttol = CCtsp_TENTATIVE_CUTS_NEXT_TOL * beta;
396 s->roundtol = CCtsp_TENTATIVE_CUTS_NEXT_ROUND * beta;
397 } else {
398 s->nexttol = CCtsp_CUTS_NEXT_TOL * beta;
399 s->roundtol = CCtsp_CUTS_NEXT_ROUND * beta;
400 }
401
402 /* Simple Branching
403 s->nexttol = 2 * CCtsp_CUTS_NEXT_TOL * beta;
404 s->roundtol = 2 * CCtsp_CUTS_NEXT_ROUND * beta;
405 */
406
407
408 if (!silent) {
409 printf ("Setting tolerances: next cuts %.4f next round %.4f\n",
410 s->nexttol, s->roundtol);
411 fflush (stdout);
412 }
413
414 return 0;
415 }
416
CCtsp_cutting_multiple_loop(CCtsp_lp * lp,CCtsp_cutselect * sel,int savelp,int maxlocal,int update_tol,int silent,CCrandstate * rstate)417 int CCtsp_cutting_multiple_loop (CCtsp_lp *lp, CCtsp_cutselect *sel,
418 int savelp, int maxlocal, int update_tol, int silent,
419 CCrandstate *rstate)
420 {
421 int rval = 0;
422 int k;
423
424 if (maxlocal < 16) {
425 rval = CCtsp_cutting_loop (lp, sel, savelp, silent, rstate);
426 } else {
427 for (k = 16; k <= maxlocal; k += 4) {
428 sel->maxchunksize = k;
429 printf ("SETTING MAXCHUNKSIZE = %d\n", k); fflush (stdout);
430 if (update_tol) {
431 rval = CCtsp_cutselect_set_tols (sel, lp, 1, 0);
432 if (rval) {
433 fprintf (stderr, "CCtsp_cutselect_set_tols failed\n");
434 /* Reset rval, since 2 has a special meaning */
435 rval = 1; goto CLEANUP;
436 }
437 }
438 rval = CCtsp_cutting_loop (lp, sel, savelp, silent, rstate);
439 if (rval) {
440 fprintf (stderr, "CCtsp_cutting_loop returned %d\n", rval);
441 goto CLEANUP;
442 }
443 }
444 if (maxlocal % 4 != 0) {
445 sel->maxchunksize = maxlocal;
446 printf ("SETTING MAXCHUNKSIZE = %d\n", maxlocal); fflush (stdout);
447 if (update_tol) {
448 rval = CCtsp_cutselect_set_tols (sel, lp, 1, 0);
449 if (rval) {
450 fprintf (stderr, "CCtsp_cutselect_set_tols failed\n");
451 /* Reset rval, since 2 has a special meaning */
452 rval = 1; goto CLEANUP;
453 }
454 }
455 rval = CCtsp_cutting_loop (lp, sel, savelp, silent, rstate);
456 }
457 }
458
459 CLEANUP:
460
461 return rval;
462 }
463
464
465 #define LOOP_FULL (25) /* to force a full price after 25 inner loops */
466 #define CC_NO_NEAREST (50) /* the initial sparse graph for pricing */
467
CCtsp_cutting_loop(CCtsp_lp * lp,CCtsp_cutselect * sel,int savelp,int silent,CCrandstate * rstate)468 int CCtsp_cutting_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, int savelp,
469 int silent, CCrandstate *rstate)
470 {
471 int xcount, cutcount, cutcount_connect, cut_added, edge_added, closecount;
472 int ttest = 0;
473 int *xlist = (int *) NULL;
474 int *closelist = (int *) NULL;
475 int outside = 0;
476 double newval, oldval, ub;
477 double priceval;
478 double *x = (double *) NULL;
479 double *closex = (double *) NULL;
480 CCtsp_lpcut_in *cuts = (CCtsp_lpcut_in *) NULL;
481 CCtsp_edgegenerator eginside;
482 int rval = 0;
483 int loopcount = 0;
484 int istour = 0;
485 double maxviol;
486 double save_nexttol = sel->nexttol;
487 double save_roundtol = sel->roundtol;
488 double lcimprove = CCtsp_LP_MAXDOUBLE;
489 #if defined(BIX_CHUNKS) || defined(DAVE_CHUNKS) || defined(POLISHED_CHUNKS)
490 double otherimprove = 0.0;
491 #endif
492 #if defined(POLISHED_CHUNKS)
493 int i;
494 #endif
495 double z;
496 double dval;
497 double szeit = CCutil_zeit ();
498 CCchunk_localcut_timer lc_timer;
499
500 CCutil_start_timer (&lp->stats.cutting_loop);
501 CCchunk_init_localcut_timer (&lc_timer);
502
503 eginside.ncount = 0;
504 if (lp->fulladj) {
505 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
506 lp->fulladj, 0, silent, rstate);
507 if (rval) {
508 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
509 rval = 1; goto CLEANUP;
510 }
511 } else if (lp->dat) {
512 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
513 (CCtsp_genadj *) NULL, CC_NO_NEAREST, silent, rstate);
514 if (rval) {
515 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
516 rval = 1; goto CLEANUP;
517 }
518 }
519
520 rval = CCtsp_get_lp_result (lp, (double *) NULL, &ub, (int *) NULL,
521 (int **) NULL, (double **) NULL, (double **) NULL,
522 (double **) NULL, (double **) NULL);
523 if (rval) {
524 fprintf (stderr, "CCtsp_get_lp_result failed\n");
525 rval = 1; goto CLEANUP;
526 }
527
528 do {
529 loopcount = 0;
530 cutcount_connect = 0;
531 do {
532 CCutil_start_timer (&lp->stats.cutting_inner_loop);
533
534 rval = CCtsp_resparsify_lp (lp, silent);
535 if (rval) {
536 fprintf (stderr, "CCtsp_resparsify_lp failed\n");
537 rval = 1; goto CLEANUP;
538 }
539
540 cut_added = 0;
541 rval = lp_value (lp, &oldval);
542 if (rval) {rval = 1; goto CLEANUP;}
543
544 newval = oldval;
545
546 rval = lp_x (lp, &xcount, &xlist, &x);
547 if (rval) {rval = 1; goto CLEANUP;}
548
549 rval = CCtsp_check_integral (lp, &dval, (int **) NULL, &istour,
550 silent);
551 if (rval) {
552 fprintf (stderr, "CCtsp_check_integral failed\n"); goto CLEANUP;
553 }
554 if (istour) goto OUT_LOOP;
555
556 if (sel->filecuts) {
557 CCutil_start_timer (&lp->stats.cuts_filecut);
558 rval = CCtsp_file_cuts (sel->filecutname, &cuts, &cutcount,
559 lp->graph.ncount, lp->perm);
560 if (rval) {
561 fprintf (stderr, "CCtsp_file_cuts failed\n");
562 rval = 1; goto CLEANUP;
563 }
564 z = CCutil_stop_timer (&lp->stats.cuts_filecut, 0);
565 if (!silent) {
566 printf ("Found %2d file cuts in %.2f seconds\n",
567 cutcount, z);
568 fflush (stdout);
569 }
570 if (cutcount) {
571 CCutil_start_timer (&lp->stats.cuts_filecut_opt);
572 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
573 &xlist, &x, &newval, sel->usetighten,
574 &istour, silent, rstate);
575 if (rval) {
576 fprintf (stderr, "call_add_cuts failed\n");
577 goto CLEANUP;
578 }
579 CCutil_stop_timer (&lp->stats.cuts_filecut_opt, 0);
580 if (istour) goto OUT_LOOP;
581 }
582 }
583
584 if (sel->cutpool) {
585 int qqq = 0;
586 do {
587 CCutil_start_timer (&lp->stats.cuts_cutpool);
588 rval = CCtsp_search_cutpool (lp->pool, &cuts, &cutcount,
589 &maxviol, lp->graph.ncount, xcount, xlist, x, 0,
590 rstate);
591 if (rval) {
592 fprintf (stderr, "CCtsp_search_cutpool failed\n");
593 rval = 1; goto CLEANUP;
594 }
595 z = CCutil_stop_timer (&lp->stats.cuts_cutpool, 0);
596 if (cutcount) {
597 if (!silent) {
598 printf ("Found %2d pool cuts (viol %.4f) in %.2f seconds\n",
599 cutcount, maxviol, z);
600 fflush (stdout);
601 }
602 CCutil_start_timer (&lp->stats.cuts_cutpool_opt);
603 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
604 &xlist, &x, &newval, sel->usetighten,
605 &istour, silent, rstate);
606 if (rval) {
607 fprintf (stderr, "call_add_cuts failed\n");
608 goto CLEANUP;
609 }
610 CCutil_stop_timer (&lp->stats.cuts_cutpool_opt, 0);
611 if (istour) goto OUT_LOOP;
612 }
613 qqq++;
614 } while (cutcount && qqq < 1 /* 10 */);
615 }
616
617 if (sel->connect) {
618 CCutil_start_timer (&lp->stats.cuts_connect);
619 rval = CCtsp_connect_cuts (&cuts, &cutcount, lp->graph.ncount,
620 xcount, xlist, x);
621 if (rval) {
622 fprintf (stderr, "CCtsp_connect_cuts failed\n");
623 rval = 1; goto CLEANUP;
624 }
625 z = CCutil_stop_timer (&lp->stats.cuts_connect, 0);
626 if (!silent) {
627 printf ("Found %2d connect cuts in %.2f seconds\n",
628 cutcount, z);
629 fflush (stdout);
630 }
631 if (cutcount) {
632 CCutil_start_timer (&lp->stats.cuts_connect_opt);
633 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
634 &xlist, &x, &newval, sel->usetighten,
635 &istour, silent, rstate);
636 if (rval) {
637 fprintf (stderr, "call_add_cuts failed\n");
638 goto CLEANUP;
639 }
640 CCutil_stop_timer (&lp->stats.cuts_connect_opt, 0);
641 if (istour) goto OUT_LOOP;
642 }
643 }
644
645 if (sel->segments) {
646 CCutil_start_timer (&lp->stats.cuts_segment);
647 rval = CCtsp_segment_cuts (&cuts, &cutcount, lp->graph.ncount,
648 xcount, xlist, x);
649 if (rval) {
650 fprintf (stderr, "CCtsp_segment_cuts failed\n");
651 rval = 1; goto CLEANUP;
652 }
653 z = CCutil_stop_timer (&lp->stats.cuts_segment, 0);
654 if (!silent) {
655 printf ("Found %2d segment cuts in %.2f seconds\n",
656 cutcount, z);
657 fflush (stdout);
658 }
659 if (cutcount) {
660 CCutil_start_timer (&lp->stats.cuts_segment_opt);
661 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
662 &xlist, &x, &newval, sel->usetighten,
663 &istour, silent, rstate);
664 if (rval) {
665 fprintf (stderr, "call_add_cuts failed\n");
666 goto CLEANUP;
667 }
668 CCutil_stop_timer (&lp->stats.cuts_segment_opt, 0);
669 if (istour) goto OUT_LOOP;
670 }
671 }
672
673 if (sel->fastblossom) {
674 CCutil_start_timer (&lp->stats.cuts_fastblossom);
675 rval = CCtsp_fastblossom (&cuts, &cutcount, lp->graph.ncount,
676 xcount, xlist, x);
677 if (rval) {
678 fprintf (stderr, "CCtsp_fastblossom failed\n");
679 rval = 1; goto CLEANUP;
680 }
681 z = CCutil_stop_timer (&lp->stats.cuts_fastblossom, 0);
682 if (!silent) {
683 printf ("Found %2d Fast Blossoms in %.2f seconds\n",
684 cutcount, z);
685 fflush (stdout);
686 }
687 if (cutcount) {
688 CCutil_start_timer (&lp->stats.cuts_fastblossom_opt);
689 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
690 &xlist, &x, &newval, sel->usetighten,
691 &istour, silent, rstate);
692 if (rval) {
693 fprintf (stderr, "call_add_cuts failed\n");
694 goto CLEANUP;
695 }
696 CCutil_stop_timer (&lp->stats.cuts_fastblossom_opt, 0);
697 if (istour) goto OUT_LOOP;
698 }
699 }
700
701 if (sel->ghfastblossom) {
702 CCutil_start_timer (&lp->stats.cuts_ghfastblossom);
703 rval = CCtsp_ghfastblossom (&cuts, &cutcount, lp->graph.ncount,
704 xcount, xlist, x);
705 if (rval) {
706 fprintf (stderr, "CCtsp_ghfastblossom failed\n");
707 rval = 1; goto CLEANUP;
708 }
709 z = CCutil_stop_timer (&lp->stats.cuts_ghfastblossom, 0);
710 if (!silent) {
711 printf ("Found %2d Groetschel-Holland Blossoms in %.2f seconds\n",
712 cutcount, z);
713 fflush (stdout);
714 }
715 if (cutcount) {
716 CCutil_start_timer (&lp->stats.cuts_ghfastblossom_opt);
717 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
718 &xlist, &x, &newval, sel->usetighten,
719 &istour, silent, rstate);
720 if (rval) {
721 fprintf (stderr, "call_add_cuts failed\n");
722 goto CLEANUP;
723 }
724 CCutil_stop_timer (&lp->stats.cuts_ghfastblossom_opt, 0);
725 if (istour) goto OUT_LOOP;
726 }
727 }
728
729 if (sel->remotepool) {
730 int qqq = 0;
731 do {
732 CCutil_start_timer (&lp->stats.cuts_remotepool);
733 rval = CCtsp_search_remotepool (sel->remotehost,
734 sel->remoteport, &cuts, &cutcount, &maxviol,
735 lp->graph.ncount, xcount, xlist, x);
736 if (rval) {
737 fprintf (stderr, "CCtsp_search_remotepool failed\n");
738 rval = 1; goto CLEANUP;
739 }
740 z = CCutil_stop_timer (&lp->stats.cuts_remotepool, 0);
741 if (cutcount) {
742 if (!silent) {
743 printf ("%d remote pool cuts found (viol %.3f) in %.2f seconds\n",
744 cutcount, maxviol, z);
745 fflush (stdout);
746 }
747 CCutil_start_timer (&lp->stats.cuts_remotepool_opt);
748 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
749 &xlist, &x, &newval, sel->usetighten,
750 &istour, silent, rstate);
751 if (rval) {
752 fprintf (stderr, "call_add_cuts failed\n");
753 goto CLEANUP;
754 }
755 CCutil_stop_timer (&lp->stats.cuts_remotepool_opt, 0);
756 if (istour) goto OUT_LOOP;
757 }
758 qqq++;
759 } while (cutcount && qqq < 1 /* 1 */);
760 }
761
762 if (sel->blockcombs) {
763 CCutil_start_timer (&lp->stats.cuts_blockcomb);
764 rval = CCtsp_block_combs (&cuts, &cutcount, lp->graph.ncount,
765 xcount, xlist, x, silent);
766 if (rval) {
767 fprintf (stderr, "CCtsp_block_combs failed\n");
768 rval = 1; goto CLEANUP;
769 }
770 z = CCutil_stop_timer (&lp->stats.cuts_blockcomb, 0);
771 if (!silent) {
772 printf ("Found %2d block_combs in %.2f seconds\n",
773 cutcount, z);
774 fflush (stdout);
775 }
776 if (cutcount) {
777 CCutil_start_timer (&lp->stats.cuts_blockcomb_opt);
778 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
779 &xlist, &x, &newval, sel->usetighten,
780 &istour, silent, rstate);
781 if (rval) {
782 fprintf (stderr, "call_add_cuts failed\n");
783 goto CLEANUP;
784 }
785 CCutil_stop_timer (&lp->stats.cuts_blockcomb_opt, 0);
786 if (istour) goto OUT_LOOP;
787 }
788 }
789
790 if (sel->growcombs) {
791 CCutil_start_timer (&lp->stats.cuts_growcomb);
792 rval = CCtsp_edge_comb_grower (&cuts, &cutcount,
793 lp->graph.ncount, xcount, xlist, x,
794 &lp->stats.extra_tighten_stats);
795 if (rval) {
796 fprintf (stderr, "CCtsp_block_combs failed\n");
797 rval = 1; goto CLEANUP;
798 }
799 z = CCutil_stop_timer (&lp->stats.cuts_growcomb, 0);
800 if (!silent) {
801 printf ("Found %2d grown combs in %.2f seconds\n",
802 cutcount, z);
803 fflush (stdout);
804 }
805 if (cutcount) {
806 CCutil_start_timer (&lp->stats.cuts_growcomb_opt);
807 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
808 &xlist, &x, &newval, sel->usetighten,
809 &istour, silent, rstate);
810 if (rval) {
811 fprintf (stderr, "call_add_cuts failed\n");
812 goto CLEANUP;
813 }
814 CCutil_stop_timer (&lp->stats.cuts_growcomb_opt, 0);
815 if (istour) goto OUT_LOOP;
816 }
817 }
818
819 if (sel->prclique) {
820 rval = CCtsp_pr_cliquetree (&cuts, &cutcount,
821 lp->graph.ncount, xcount, xlist, x,
822 &lp->stats.extra_tighten_stats);
823 if (rval) {
824 fprintf (stderr, "CCtsp_pr_cliquetree failed\n");
825 rval = 1; goto CLEANUP;
826 }
827 if (!silent) {
828 printf ("Found %2d PR cliquetrees\n", cutcount);
829 fflush (stdout);
830 }
831 if (cutcount) {
832 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
833 &xlist, &x, &newval, sel->usetighten,
834 &istour, silent, rstate);
835 if (rval) {
836 fprintf (stderr, "call_add_cuts failed\n");
837 goto CLEANUP;
838 }
839 if (istour) goto OUT_LOOP;
840 }
841 }
842
843 if (sel->exactsubtour) {
844 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
845 rval = CCtsp_exact_subtours (&cuts, &cutcount,
846 lp->graph.ncount, xcount, xlist, x);
847 if (rval) {
848 fprintf (stderr, "CCtsp_exact_subtours failed\n");
849 rval = 1; goto CLEANUP;
850 }
851 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
852 if (!silent) {
853 printf ("Found %2d exact subtours in %.2f seconds\n",
854 cutcount, z);
855 fflush (stdout);
856 }
857 if (cutcount) {
858 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
859 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
860 &xlist, &x, &newval, sel->usetighten,
861 &istour, silent, rstate);
862 if (rval) {
863 fprintf (stderr, "call_add_cuts failed\n");
864 goto CLEANUP;
865 }
866 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
867 if (istour) goto OUT_LOOP;
868 }
869 }
870
871 #ifdef CCtsp_USE_DOMINO_CUTS
872 if (sel->shrunk_dominos) {
873 do {
874 cut_added = 0;
875 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
876 rval = CCtsp_exact_subtours (&cuts, &cutcount,
877 lp->graph.ncount, xcount, xlist, x);
878 if (rval) {
879 fprintf (stderr, "CCtsp_exact_subtours failed\n");
880 rval = 1; goto CLEANUP;
881 }
882 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
883 if (!silent) {
884 printf ("Found %2d exact subtours in %.2f seconds\n",
885 cutcount, z);
886 fflush (stdout);
887 }
888 if (cutcount) {
889 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
890 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
891 &xlist, &x, &newval, sel->usetighten,
892 &istour, silent, rstate);
893 if (rval) {
894 fprintf (stderr, "call_add_cuts failed\n");
895 goto CLEANUP;
896 }
897 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
898 if (istour) goto OUT_LOOP;
899 }
900 } while (cut_added > 0);
901
902 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
903 rval = CCtsp_shrink_domino (&cuts, &cutcount, lp->graph.ncount,
904 xcount, xlist, x, 1, 5, rstate, sel->dombosshost);
905 CCcheck_rval (rval, "CCtsp_new_domino failed");
906
907 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
908 if (0 || !silent) {
909 printf ("Found %2d domino cuts in %.2f seconds\n",
910 cutcount, z);
911 fflush (stdout);
912 }
913 if (cutcount) {
914 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
915 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
916 &xlist, &x, &newval, 0,
917 &istour, 0 /* silent */, rstate);
918 if (rval) {
919 fprintf (stderr, "call_add_cuts failed\n");
920 goto CLEANUP;
921 }
922 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
923 if (istour) goto OUT_LOOP;
924 printf ("Added %d shrunk domino cuts\n", cut_added);
925 fflush (stdout);
926 }
927 }
928
929 if (sel->dominos) {
930 do {
931 cut_added = 0;
932 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
933 rval = CCtsp_exact_subtours (&cuts, &cutcount,
934 lp->graph.ncount, xcount, xlist, x);
935 if (rval) {
936 fprintf (stderr, "CCtsp_exact_subtours failed\n");
937 rval = 1; goto CLEANUP;
938 }
939 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
940 if (!silent) {
941 printf ("Found %2d exact subtours in %.2f seconds\n",
942 cutcount, z);
943 fflush (stdout);
944 }
945 if (cutcount) {
946 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
947 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
948 &xlist, &x, &newval, sel->usetighten,
949 &istour, silent, rstate);
950 if (rval) {
951 fprintf (stderr, "call_add_cuts failed\n");
952 goto CLEANUP;
953 }
954 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
955 if (istour) goto OUT_LOOP;
956 }
957 } while (cut_added > 0);
958
959 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
960 rval = CCtsp_new_domino (&cuts, &cutcount, lp->graph.ncount,
961 xcount, xlist, x, sel->dombosshost);
962 CCcheck_rval (rval, "CCtsp_new_domino failed");
963
964 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
965 if (0 || !silent) {
966 printf ("Found %2d domino cuts in %.2f seconds\n",
967 cutcount, z);
968 fflush (stdout);
969 }
970 if (cutcount) {
971 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
972 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
973 &xlist, &x, &newval, 0,
974 &istour, 0 /* silent */, rstate);
975 if (rval) {
976 fprintf (stderr, "call_add_cuts failed\n");
977 goto CLEANUP;
978 }
979 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
980 if (istour) goto OUT_LOOP;
981 printf ("Added %d domino cuts\n", cut_added);
982 fflush (stdout);
983 }
984 }
985 #endif
986
987 if (sel->exactblossom) {
988 CCutil_start_timer (&lp->stats.cuts_exactblossom);
989 rval = CCtsp_exactblossom (&cuts, &cutcount, lp->graph.ncount,
990 xcount, xlist, x, rstate);
991 if (rval) {
992 fprintf (stderr, "CCtsp_exactblossom failed\n");
993 rval = 1; goto CLEANUP;
994 }
995 z = CCutil_stop_timer (&lp->stats.cuts_exactblossom, 0);
996 if (!silent) {
997 printf ("Found %2d Exact Blossoms in %.2f seconds\n",
998 cutcount, z);
999 fflush (stdout);
1000 }
1001 if (cutcount) {
1002 CCutil_start_timer (&lp->stats.cuts_exactblossom_opt);
1003 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1004 &xlist, &x, &newval, sel->usetighten,
1005 &istour, silent, rstate);
1006 if (rval) {
1007 fprintf (stderr, "call_add_cuts failed\n");
1008 goto CLEANUP;
1009 }
1010 CCutil_stop_timer (&lp->stats.cuts_exactblossom_opt, 0);
1011 if (istour) goto OUT_LOOP;
1012 }
1013 }
1014
1015 if (sel->tighten_lp) {
1016 CCutil_start_timer (&lp->stats.cuts_tighten_lp);
1017 rval = CCtsp_tighten_lp (&lp->cuts,
1018 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1019 lp->graph.ncount, xcount, xlist, x, 0.5, 500, &maxviol,
1020 rstate);
1021 if (rval) {
1022 fprintf (stderr, "CCtsp_tighten_lp failed\n");
1023 rval = 1; goto CLEANUP;
1024 }
1025 z = CCutil_stop_timer (&lp->stats.cuts_tighten_lp, 0);
1026 if (!silent) {
1027 printf ("Found %2d tighten_lp cuts (viol %.4f) in %.2f seconds\n",
1028 cutcount, maxviol, z);
1029 fflush (stdout);
1030 }
1031 if (cutcount) {
1032 CCutil_start_timer (&lp->stats.cuts_tighten_lp_opt);
1033 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1034 &xlist, &x, &newval, sel->usetighten,
1035 &istour, silent, rstate);
1036 if (rval) {
1037 fprintf (stderr, "call_add_cuts failed\n");
1038 goto CLEANUP;
1039 }
1040 CCutil_stop_timer (&lp->stats.cuts_tighten_lp_opt, 0);
1041 if (istour) goto OUT_LOOP;
1042 }
1043 CCutil_start_timer (&lp->stats.cuts_tighten_lp_close);
1044 rval = grab_close_x (lp->graph.ncount, xcount, xlist, x,
1045 &closecount, &closelist, &closex, 0.5);
1046 if (rval) {
1047 fprintf (stderr, "grab_close_x failed\n");
1048 goto CLEANUP;
1049 }
1050 rval = CCtsp_tighten_lp (&lp->cuts,
1051 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1052 lp->graph.ncount, closecount, closelist, closex,
1053 0.5, 500, &maxviol, rstate);
1054 if (rval) {
1055 fprintf (stderr, "CCtsp_tighten_lp failed\n");
1056 rval = 1; goto CLEANUP;
1057 }
1058 z = CCutil_stop_timer (&lp->stats.cuts_tighten_lp_close, 0);
1059 if (!silent) {
1060 printf ("Found %2d CLOSE tighten_lp cuts (viol %.4f) in %.2f seconds\n",
1061 cutcount, maxviol, z);
1062 fflush (stdout);
1063 }
1064 if (cutcount) {
1065 CCutil_start_timer (&lp->stats.cuts_tighten_lp_close_opt);
1066 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1067 &xlist, &x, &newval, sel->usetighten,
1068 &istour, silent, rstate);
1069 if (rval) {
1070 fprintf (stderr, "call_add_cuts failed\n");
1071 goto CLEANUP;
1072 }
1073 CCutil_stop_timer (&lp->stats.cuts_tighten_lp_close_opt,
1074 0);
1075 if (istour) goto OUT_LOOP;
1076 }
1077 }
1078
1079 if (sel->decker_lp) {
1080 CCutil_start_timer (&lp->stats.cuts_decker_lp);
1081 rval = CCtsp_double_decker_lp (&lp->cuts,
1082 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1083 lp->graph.ncount, xcount, xlist, x, 10.0, 500,
1084 &maxviol, rstate);
1085 if (rval) {
1086 fprintf (stderr, "CCtsp_double_decker_lp failed\n");
1087 rval = 1; goto CLEANUP;
1088 }
1089 z = CCutil_stop_timer (&lp->stats.cuts_decker_lp, 0);
1090 if (!silent) {
1091 printf ("Found %2d double deckers (viol %.4f) in %.2f seconds\n",
1092 cutcount, maxviol, z);
1093 fflush (stdout);
1094 }
1095 if (cutcount) {
1096 CCutil_start_timer (&lp->stats.cuts_decker_lp_opt);
1097 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1098 &xlist, &x, &newval, sel->usetighten,
1099 &istour, silent, rstate);
1100 if (rval) {
1101 fprintf (stderr, "call_add_cuts failed\n");
1102 goto CLEANUP;
1103 }
1104 CCutil_stop_timer (&lp->stats.cuts_decker_lp_opt, 0);
1105 if (istour) goto OUT_LOOP;
1106 }
1107 CCutil_start_timer (&lp->stats.cuts_decker_lp_close);
1108 rval = grab_close_x (lp->graph.ncount, xcount, xlist, x,
1109 &closecount, &closelist, &closex, 0.5);
1110 if (rval) {
1111 fprintf (stderr, "grab_close_x failed\n");
1112 goto CLEANUP;
1113 }
1114 rval = CCtsp_double_decker_lp (&lp->cuts,
1115 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1116 lp->graph.ncount, closecount, closelist, closex,
1117 10.0, 500, &maxviol, rstate);
1118 if (rval) {
1119 fprintf (stderr, "CCtsp_double_decker_lp failed\n");
1120 rval = 1; goto CLEANUP;
1121 }
1122 z = CCutil_stop_timer (&lp->stats.cuts_decker_lp_close, 0);
1123 if (!silent) {
1124 printf ("Found %2d CLOSE double deckers (viol %.4f) in %.2f seconds\n",
1125 cutcount, maxviol, z);
1126 fflush (stdout);
1127 }
1128 if (cutcount) {
1129 CCutil_start_timer (&lp->stats.cuts_decker_lp_close_opt);
1130 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1131 &xlist, &x, &newval, sel->usetighten,
1132 &istour, silent, rstate);
1133 if (rval) {
1134 fprintf (stderr, "call_add_cuts failed\n");
1135 goto CLEANUP;
1136 }
1137 CCutil_stop_timer (&lp->stats.cuts_decker_lp_close_opt, 0);
1138 if (istour) goto OUT_LOOP;
1139 }
1140 }
1141
1142
1143 if (sel->star_lp) {
1144 CCutil_start_timer (&lp->stats.cuts_star_lp);
1145 rval = CCtsp_star_lp (&lp->cuts,
1146 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1147 lp->graph.ncount, xcount, xlist, x, 10.0, 500,
1148 &maxviol, rstate);
1149 if (rval) {
1150 fprintf (stderr, "CCtsp_star_lp failed\n");
1151 rval = 1; goto CLEANUP;
1152 }
1153 z = CCutil_stop_timer (&lp->stats.cuts_star_lp, 0);
1154 if (!silent) {
1155 printf ("Found %2d Star Inequalities (viol %.4f) in %.2f seconds\n",
1156 cutcount, maxviol, z);
1157 fflush (stdout);
1158 }
1159 if (cutcount) {
1160 CCutil_start_timer (&lp->stats.cuts_star_lp_opt);
1161 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1162 &xlist, &x, &newval, sel->usetighten, &istour,
1163 silent, rstate);
1164 if (rval) {
1165 fprintf (stderr, "call_add_cuts failed\n");
1166 goto CLEANUP;
1167 }
1168 CCutil_stop_timer (&lp->stats.cuts_star_lp_opt, 0);
1169 if (istour) goto OUT_LOOP;
1170 }
1171 }
1172
1173 if (sel->handling_lp) {
1174 rval = no_tighten (lp->graph.ncount, xcount, xlist, x, &ttest,
1175 0.20);
1176 if (rval) {
1177 fprintf (stderr, "no_tighten failed\n"); goto CLEANUP;
1178 }
1179 }
1180
1181 if (sel->handling_lp && ttest == 0) {
1182 CCutil_start_timer (&lp->stats.cuts_handling_lp);
1183 rval = CCtsp_handling_lp (&lp->cuts,
1184 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1185 lp->graph.ncount, xcount, xlist, x, 10.0, 500,
1186 &maxviol, rstate);
1187 if (rval) {
1188 fprintf (stderr, "CCtsp_handling_lp failed\n");
1189 rval = 1; goto CLEANUP;
1190 }
1191 z = CCutil_stop_timer (&lp->stats.cuts_handling_lp, 0);
1192 if (!silent) {
1193 printf ("Found %2d Handling Inequalities (viol %.4f) in %.2f seconds\n",
1194 cutcount, maxviol, z);
1195 fflush (stdout);
1196 }
1197 if (cutcount) {
1198 CCutil_start_timer (&lp->stats.cuts_handling_lp_opt);
1199 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1200 &xlist, &x, &newval, sel->usetighten, &istour,
1201 silent, rstate);
1202 if (rval) {
1203 fprintf (stderr, "call_add_cuts failed\n");
1204 goto CLEANUP;
1205 }
1206 CCutil_stop_timer (&lp->stats.cuts_handling_lp_opt, 0);
1207 if (istour) goto OUT_LOOP;
1208 }
1209 }
1210
1211 if (sel->cliquetree_lp) {
1212 CCutil_start_timer (&lp->stats.cuts_cliquetree_lp);
1213 rval = CCtsp_cliquetree_lp (&lp->cuts,
1214 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1215 lp->graph.ncount, xcount, xlist, x, 10.0, 500,
1216 &maxviol, rstate);
1217 if (rval) {
1218 fprintf (stderr, "CCtsp_cliqutree_lp failed\n");
1219 rval = 1; goto CLEANUP;
1220 }
1221 z = CCutil_stop_timer (&lp->stats.cuts_cliquetree_lp, 0);
1222 if (!silent) {
1223 printf ("Found %2d comb cliquetrees (viol %.4f) in %.2f seconds\n",
1224 cutcount, maxviol, z);
1225 fflush (stdout);
1226 }
1227 if (cutcount) {
1228 CCutil_start_timer (&lp->stats.cuts_cliquetree_lp_opt);
1229 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1230 &xlist, &x, &newval, sel->usetighten,
1231 &istour, silent, rstate);
1232 if (rval) {
1233 fprintf (stderr, "call_add_cuts failed\n");
1234 goto CLEANUP;
1235 }
1236 CCutil_stop_timer (&lp->stats.cuts_cliquetree_lp_opt, 0);
1237 if (istour) goto OUT_LOOP;
1238 }
1239 }
1240
1241 if (sel->teething_lp) {
1242 rval = no_tighten (lp->graph.ncount, xcount, xlist, x, &ttest,
1243 0.20);
1244 if (rval) {
1245 fprintf (stderr, "no_tighten failed\n"); goto CLEANUP;
1246 }
1247 }
1248
1249 if (sel->teething_lp && ttest == 0) {
1250 CCutil_start_timer (&lp->stats.cuts_teething_lp);
1251 rval = CCtsp_teething_lp (&lp->cuts,
1252 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1253 lp->graph.ncount, xcount, xlist, x, 10.0, 500,
1254 &maxviol, rstate);
1255 if (rval) {
1256 fprintf (stderr, "CCtsp_teething_lp failed\n");
1257 rval = 1; goto CLEANUP;
1258 }
1259 z = CCutil_stop_timer (&lp->stats.cuts_teething_lp, 0);
1260 if (!silent) {
1261 printf ("Found %2d teethed combs (viol %.4f) in %.2f seconds\n",
1262 cutcount, maxviol, z);
1263 fflush (stdout);
1264 }
1265 if (cutcount) {
1266 CCutil_start_timer (&lp->stats.cuts_teething_lp_opt);
1267 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1268 &xlist, &x, &newval, sel->usetighten,
1269 &istour, silent, rstate);
1270 if (rval) {
1271 fprintf (stderr, "call_add_cuts failed\n");
1272 goto CLEANUP;
1273 }
1274 CCutil_stop_timer (&lp->stats.cuts_teething_lp_opt, 0);
1275 if (istour) goto OUT_LOOP;
1276 }
1277 }
1278
1279 if (sel->tighten_pool) {
1280 rval = no_tighten (lp->graph.ncount, xcount, xlist, x, &ttest,
1281 0.2);
1282 if (rval) {
1283 fprintf (stderr, "no_tighten failed\n"); goto CLEANUP;
1284 }
1285 }
1286
1287 if (sel->tighten_pool && newval < oldval + sel->nexttol &&
1288 ttest == 0) {
1289 CCutil_start_timer (&lp->stats.cuts_tighten_pool);
1290 rval = CCtsp_tighten_lp (lp->pool,
1291 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1292 lp->graph.ncount, xcount, xlist, x, 0.1, 1000,
1293 &maxviol, rstate);
1294 if (rval) {
1295 fprintf (stderr, "CCtsp_tighten_lp failed\n");
1296 rval = 1; goto CLEANUP;
1297 }
1298 z = CCutil_stop_timer (&lp->stats.cuts_tighten_pool, 0);
1299 if (!silent) {
1300 printf ("Found %2d tighten pool cuts (viol %.4f) in %.2f seconds\n",
1301 cutcount, maxviol, z);
1302 fflush (stdout);
1303 }
1304 if (cutcount) {
1305 CCutil_start_timer (&lp->stats.cuts_tighten_pool_opt);
1306 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1307 &xlist, &x, &newval, sel->usetighten,
1308 &istour, silent, rstate);
1309 if (rval) {
1310 fprintf (stderr, "call_add_cuts failed\n");
1311 goto CLEANUP;
1312 }
1313 CCutil_stop_timer (&lp->stats.cuts_tighten_pool_opt, 0);
1314 if (istour) goto OUT_LOOP;
1315 }
1316 }
1317
1318 if (sel->decker_pool && newval < oldval + sel->nexttol) {
1319 CCutil_start_timer (&lp->stats.cuts_decker_pool);
1320 rval = CCtsp_double_decker_lp (lp->pool,
1321 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1322 lp->graph.ncount, xcount, xlist, x, 2.0, 1000,
1323 &maxviol, rstate);
1324 if (rval) {
1325 fprintf (stderr, "CCtsp_double_decker_lp failed\n");
1326 rval = 1; goto CLEANUP;
1327 }
1328 z = CCutil_stop_timer (&lp->stats.cuts_decker_pool, 0);
1329 if (!silent) {
1330 printf ("Found %2d pool double deckers (viol %.4f) in %.2f seconds\n",
1331 cutcount, maxviol, z);
1332 fflush (stdout);
1333 }
1334 if (cutcount) {
1335 CCutil_start_timer (&lp->stats.cuts_decker_pool_opt);
1336 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1337 &xlist, &x, &newval, sel->usetighten,
1338 &istour, silent, rstate);
1339 if (rval) {
1340 fprintf (stderr, "call_add_cuts failed\n");
1341 goto CLEANUP;
1342 }
1343 CCutil_stop_timer (&lp->stats.cuts_decker_pool_opt, 0);
1344 if (istour) goto OUT_LOOP;
1345 }
1346 }
1347
1348 if (sel->star_pool && newval < oldval + sel->nexttol) {
1349 CCutil_start_timer (&lp->stats.cuts_star_pool);
1350 rval = CCtsp_star_lp (lp->pool,
1351 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1352 lp->graph.ncount, xcount, xlist, x, 2.0, 1000,
1353 &maxviol, rstate);
1354 if (rval) {
1355 fprintf (stderr, "CCtsp_star_lp failed\n");
1356 rval = 1; goto CLEANUP;
1357 }
1358 z = CCutil_stop_timer (&lp->stats.cuts_star_pool, 0);
1359 if (!silent) {
1360 printf ("Found %2d Pool Star Inequalities (viol %.4f) in %.2f seconds\n",
1361 cutcount, maxviol, z);
1362 fflush (stdout);
1363 }
1364 if (cutcount) {
1365 CCutil_start_timer (&lp->stats.cuts_star_pool_opt);
1366 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1367 &xlist, &x, &newval, sel->usetighten, &istour,
1368 silent, rstate);
1369 if (rval) {
1370 fprintf (stderr, "call_add_cuts failed\n");
1371 goto CLEANUP;
1372 }
1373 CCutil_stop_timer (&lp->stats.cuts_star_pool_opt, 0);
1374 if (istour) goto OUT_LOOP;
1375 }
1376 }
1377
1378 if (sel->handling_pool && newval < oldval + sel->nexttol) {
1379 CCutil_start_timer (&lp->stats.cuts_handling_pool);
1380 rval = CCtsp_handling_lp (lp->pool,
1381 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1382 lp->graph.ncount, xcount, xlist, x, 2.0, 1000,
1383 &maxviol, rstate);
1384 if (rval) {
1385 fprintf (stderr, "CCtsp_handling_lp failed\n");
1386 rval = 1; goto CLEANUP;
1387 }
1388 z = CCutil_stop_timer (&lp->stats.cuts_handling_pool, 0);
1389 if (!silent) {
1390 printf ("Found %2d Pool Handling Inequalities (viol %.4f) in %.2f seconds\n",
1391 cutcount, maxviol, z);
1392 fflush (stdout);
1393 }
1394 if (cutcount) {
1395 CCutil_start_timer (&lp->stats.cuts_handling_pool_opt);
1396 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1397 &xlist, &x, &newval, sel->usetighten, &istour,
1398 silent, rstate);
1399 if (rval) {
1400 fprintf (stderr, "call_add_cuts failed\n");
1401 goto CLEANUP;
1402 }
1403 CCutil_stop_timer (&lp->stats.cuts_handling_pool_opt, 0);
1404 if (istour) goto OUT_LOOP;
1405 }
1406 }
1407
1408 if (sel->teething_pool && newval < oldval + sel->nexttol) {
1409 CCutil_start_timer (&lp->stats.cuts_teething_pool);
1410 rval = CCtsp_teething_lp (lp->pool,
1411 &lp->stats.extra_tighten_stats, &cuts, &cutcount,
1412 lp->graph.ncount, xcount, xlist, x, 0.5, 1000,
1413 &maxviol, rstate);
1414 if (rval) {
1415 fprintf (stderr, "CCtsp_teething_lp failed\n");
1416 rval = 1; goto CLEANUP;
1417 }
1418 z = CCutil_stop_timer (&lp->stats.cuts_teething_pool, 0);
1419 if (!silent) {
1420 printf ("Found %2d pool teething combs (viol %.4f) in %.2f seconds\n",
1421 cutcount, maxviol, z);
1422 fflush (stdout);
1423 }
1424 if (cutcount) {
1425 CCutil_start_timer (&lp->stats.cuts_teething_pool_opt);
1426 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1427 &xlist, &x, &newval, sel->usetighten,
1428 &istour, silent, rstate);
1429 if (rval) {
1430 fprintf (stderr, "call_add_cuts failed\n");
1431 goto CLEANUP;
1432 }
1433 CCutil_stop_timer (&lp->stats.cuts_teething_pool_opt, 0);
1434 if (istour) goto OUT_LOOP;
1435 }
1436 }
1437
1438 if (sel->consecutiveones && newval < oldval + sel->nexttol) {
1439 CCutil_start_timer (&lp->stats.cuts_consecutiveones);
1440 rval = CCpq_cuttree_improve_quick (&lp->tightcuts, lp->pool,
1441 xcount, xlist, x);
1442 if (rval) {
1443 fprintf (stderr, "CCpq_cuttree_improve_quick failed\n");
1444 rval = 1; goto CLEANUP;
1445 }
1446
1447 rval = CCpq_consecutiveones (&cuts, &cutcount, &lp->tightcuts,
1448 lp->pool, xcount, xlist, x);
1449 if (rval) {
1450 fprintf (stderr, "CCpq_consecutiveones failed\n");
1451 rval = 1; goto CLEANUP;
1452 }
1453 z = CCutil_stop_timer (&lp->stats.cuts_consecutiveones, 0);
1454 if (!silent) {
1455 printf ("Found %2d consecutiveones cuts in %.2f seconds\n",
1456 cutcount, z);
1457 fflush (stdout);
1458 }
1459 if (cutcount) {
1460 CCutil_start_timer (&lp->stats.cuts_consecutiveones_opt);
1461 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1462 &xlist, &x, &newval, sel->usetighten,
1463 &istour, silent, rstate);
1464 if (rval) {
1465 fprintf (stderr, "call_add_cuts failed\n");
1466 goto CLEANUP;
1467 }
1468 CCutil_stop_timer (&lp->stats.cuts_consecutiveones_opt, 0);
1469 if (istour) goto OUT_LOOP;
1470 }
1471 }
1472
1473 if (sel->necklace && newval < oldval + sel->nexttol) {
1474 CCutil_start_timer (&lp->stats.cuts_necklace);
1475 rval = CCpq_cuttree_improve_quick (&lp->tightcuts, lp->pool,
1476 xcount, xlist, x);
1477 if (rval) {
1478 fprintf (stderr, "CCpq_cuttree_improve_quick failed\n");
1479 rval = 1; goto CLEANUP;
1480 }
1481
1482 rval = CCpq_necklaces (&cuts, &cutcount, &lp->tightcuts,
1483 xcount, xlist, x, rstate);
1484 if (rval) {
1485 fprintf (stderr, "CCpq_necklaces failed\n");
1486 rval = 1; goto CLEANUP;
1487 }
1488 z = CCutil_stop_timer (&lp->stats.cuts_necklace, 0);
1489
1490 if (!silent) {
1491 printf ("Found %2d necklace cuts in %.2f seconds\n",
1492 cutcount, z);
1493 fflush (stdout);
1494 }
1495 if (cutcount) {
1496 CCutil_start_timer (&lp->stats.cuts_necklace_opt);
1497 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1498 &xlist, &x, &newval, sel->usetighten,
1499 &istour, silent, rstate);
1500 if (rval) {
1501 fprintf (stderr, "call_add_cuts failed\n");
1502 goto CLEANUP;
1503 }
1504 CCutil_stop_timer (&lp->stats.cuts_necklace_opt, 0);
1505 if (istour) goto OUT_LOOP;
1506 }
1507 }
1508
1509 #ifdef DAVE_CHUNKS
1510 otherimprove = newval - oldval;
1511 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol &&
1512 otherimprove < 0.5 * lcimprove) {
1513 CCchunk_flag flags;
1514
1515 flags.uncivilized = 0;
1516 flags.noshrink = 0;
1517 flags.nolift = 0;
1518 flags.maxchunksize = sel->maxchunksize;
1519
1520 CCutil_start_timer (&lp->stats.cuts_localcut);
1521 rval = CCchunk_localcuts (&cuts, &cutcount, lp->graph.ncount,
1522 xcount, xlist, x, 0.0, flags, &lc_timer, silent,
1523 rstate);
1524 if (rval) {
1525 fprintf (stderr, "LocalCuts failed\n");
1526 rval = 1; goto CLEANUP;
1527 }
1528 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1529 if (cutcount) {
1530 if (!silent) {
1531 printf ("Found %2d LocalCuts in %.2f seconds\n",
1532 cutcount, z);
1533 fflush (stdout);
1534 }
1535 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1536 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1537 &xlist, &x, &newval, sel->usetighten,
1538 &istour, silent, rstate);
1539 if (rval) {
1540 fprintf (stderr, "call_add_cuts failed\n");
1541 goto CLEANUP;
1542 }
1543 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1544 if (istour) goto OUT_LOOP;
1545 }
1546 }
1547 #endif /* DAVE_CHUNKS */
1548
1549 #ifdef BIX_CHUNKS
1550 otherimprove = newval - oldval;
1551 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol &&
1552 otherimprove < 0.5 * lcimprove) {
1553 int maxchunksize, firstsize;
1554 CCchunk_flag flags;
1555
1556 flags.dummy = 0;
1557 flags.permute = 0;
1558 flags.weighted = 0;
1559 flags.spheres = 0;
1560 flags.uncivilized = 0;
1561 flags.noshrink = 0;
1562 flags.nolift = 0;
1563
1564 if (sel->maxchunksize < 8) firstsize = sel->maxchunksize;
1565 else firstsize = 8;
1566 for (maxchunksize = firstsize;
1567 maxchunksize <= sel->maxchunksize;
1568 maxchunksize++) {
1569 flags.maxchunksize = maxchunksize;
1570 flags.spheresize = maxchunksize - 2;
1571
1572 CCutil_start_timer (&lp->stats.cuts_localcut);
1573 rval = CCchunk_localcuts (&cuts, &cutcount,
1574 lp->graph.ncount, xcount, xlist, x, 0.0, flags,
1575 &lc_timer, silent, rstate);
1576 if (rval) {
1577 fprintf (stderr, "LocalCuts failed\n");
1578 rval = 1; goto CLEANUP;
1579 }
1580 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1581 if (!silent) {
1582 printf ("Found %2d LocalCuts in %.2f seconds\n",
1583 cutcount, z);
1584 fflush (stdout);
1585 }
1586 if (cutcount) {
1587 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1588 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1589 &xlist, &x, &newval, sel->usetighten,
1590 &istour, silent, rstate);
1591 if (rval) {
1592 fprintf (stderr, "call_add_cuts failed\n");
1593 goto CLEANUP;
1594 }
1595 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1596 if (istour) goto OUT_LOOP;
1597 }
1598 if (newval >= oldval + sel->nexttol) break;
1599 }
1600 }
1601
1602 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol) {
1603 int maxchunksize, firstsize;
1604 CCchunk_flag flags;
1605 double beforeval = newval;
1606
1607 flags.dummy = 0;
1608 flags.permute = 0;
1609 flags.weighted = 0;
1610 flags.spheres = 1;
1611 flags.uncivilized = 0;
1612 flags.noshrink = 0;
1613 flags.nolift = 0;
1614
1615 if (sel->maxchunksize < 8) firstsize = sel->maxchunksize;
1616 else firstsize = 8;
1617 for (maxchunksize = firstsize;
1618 maxchunksize <= sel->maxchunksize;
1619 maxchunksize++) {
1620 flags.maxchunksize = maxchunksize;
1621 flags.spheresize = maxchunksize - 2;
1622
1623 CCutil_start_timer (&lp->stats.cuts_localcut);
1624 rval = CCchunk_localcuts (&cuts, &cutcount,
1625 lp->graph.ncount, xcount, xlist, x, 0.0, flags,
1626 &lc_timer, silent, rstate);
1627 if (rval) {
1628 fprintf (stderr, "LocalCuts failed\n");
1629 rval = 1; goto CLEANUP;
1630 }
1631 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1632 if (!silent) {
1633 printf ("Found %2d LocalCuts in %.2f seconds\n",
1634 cutcount, z);
1635 fflush (stdout);
1636 }
1637 if (cutcount) {
1638 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1639 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1640 &xlist, &x, &newval, sel->usetighten,
1641 &istour, silent, rstate);
1642 if (rval) {
1643 fprintf (stderr, "call_add_cuts failed\n");
1644 goto CLEANUP;
1645 }
1646 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1647 if (istour) goto OUT_LOOP;
1648 }
1649 if (newval >= oldval + sel->nexttol) break;
1650 }
1651 lcimprove = newval - beforeval;
1652 }
1653 #if 0
1654 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol) {
1655 int i;
1656 for (i = 0; i < 3; i++) {
1657 int maxchunksize, firstsize;
1658 CCchunk_flag flags;
1659 double beforeval = newval;
1660
1661 flags.dummy = 0;
1662 flags.permute = 0;
1663 flags.weighted = 0;
1664 flags.spheres = 0;
1665 flags.uncivilized = 0;
1666 flags.noshrink = 0;
1667 flags.nolift = 0;
1668
1669 if (i == 0) flags.dummy = 1;
1670 else if (i == 1) flags.permute = 1;
1671 else if (i == 2) flags.weighted = 1;
1672
1673
1674 if (sel->maxchunksize < 8) firstsize = sel->maxchunksize;
1675 else firstsize = 8;
1676 for (maxchunksize = firstsize;
1677 maxchunksize <= sel->maxchunksize;
1678 maxchunksize++) {
1679 flags.maxchunksize = maxchunksize;
1680 flags.spheresize = maxchunksize - 2;
1681
1682 CCutil_start_timer (&lp->stats.cuts_localcut);
1683 rval = CCchunk_localcuts (&cuts, &cutcount,
1684 lp->graph.ncount, xcount, xlist, x, 0.0,
1685 flags, &lc_timer, silent, rstate);
1686 if (rval) {
1687 fprintf (stderr, "LocalCuts failed\n");
1688 rval = 1; goto CLEANUP;
1689 }
1690 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1691 if (!silent) {
1692 printf ("Found %2d LocalCuts in %.2f seconds\n",
1693 cutcount, z);
1694 fflush (stdout);
1695 }
1696 if (cutcount) {
1697 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1698 rval = call_add_cuts (lp, &cuts, &cut_added,
1699 &xcount, &xlist, &x, &newval,
1700 sel->usetighten, &istour, silent,
1701 rstate);
1702 if (rval) {
1703 fprintf (stderr, "call_add_cuts failed\n");
1704 goto CLEANUP;
1705 }
1706 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1707 if (istour) goto OUT_LOOP;
1708 }
1709 if (newval >= oldval + sel->nexttol) break;
1710 }
1711 lcimprove = newval - beforeval;
1712 }
1713 }
1714 #endif
1715 #endif /* BIX_CHUNKS */
1716 #ifdef OLD_CHUNKS
1717 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol) {
1718 CCchunk_flag flags;
1719
1720 flags.dummy = 0;
1721 flags.permute = 0;
1722 flags.weighted = 0;
1723 flags.spheres = 0;
1724 flags.uncivilized = 0;
1725 flags.noshrink = 0;
1726 flags.nolift = 0;
1727
1728 flags.maxchunksize = sel->maxchunksize;
1729 flags.spheresize = flags.maxchunksize - 2;
1730 CCutil_start_timer (&lp->stats.cuts_localcut);
1731 rval = CCchunk_localcuts (&cuts, &cutcount, lp->graph.ncount,
1732 xcount, xlist, x, 0.0, flags, &lc_timer, silent,
1733 rstate);
1734 if (rval) {
1735 fprintf (stderr, "LocalCuts failed\n");
1736 rval = 1; goto CLEANUP;
1737 }
1738 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1739 if (!silent) {
1740 printf ("Found %2d LocalCuts in %.2f seconds\n",
1741 cutcount, z);
1742 fflush (stdout);
1743 }
1744 if (cutcount) {
1745 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1746 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1747 &xlist, &x, &newval, sel->usetighten,
1748 &istour, silent, rstate);
1749 if (rval) {
1750 fprintf (stderr, "call_add_cuts failed\n");
1751 goto CLEANUP;
1752 }
1753 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1754 if (istour) goto OUT_LOOP;
1755 }
1756 }
1757
1758 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol) {
1759 CCchunk_flag flags;
1760
1761 flags.dummy = 0;
1762 flags.permute = 0;
1763 flags.weighted = 0;
1764 flags.spheres = 1;
1765 flags.uncivilized = 0;
1766 flags.noshrink = 0;
1767 flags.nolift = 0;
1768
1769 flags.maxchunksize = sel->maxchunksize;
1770 flags.spheresize = flags.maxchunksize - 2;
1771 CCutil_start_timer (&lp->stats.cuts_localcut);
1772 rval = CCchunk_localcuts (&cuts, &cutcount, lp->graph.ncount,
1773 xcount, xlist, x, 0.0, flags, &lc_timer, silent,
1774 rstate);
1775 if (rval) {
1776 fprintf (stderr, "LocalCuts failed\n");
1777 rval = 1; goto CLEANUP;
1778 }
1779 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1780 if (!silent) {
1781 printf ("Found %2d LocalCuts in %.2f seconds\n",
1782 cutcount, z);
1783 fflush (stdout);
1784 }
1785 if (cutcount) {
1786 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1787 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1788 &xlist, &x, &newval, sel->usetighten,
1789 &istour, silent, rstate);
1790 if (rval) {
1791 fprintf (stderr, "call_add_cuts failed\n");
1792 goto CLEANUP;
1793 }
1794 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1795 if (istour) goto OUT_LOOP;
1796 }
1797 }
1798 #endif /* OLD_CHUNKS */
1799
1800 #ifdef POLISHED_CHUNKS
1801 /* polished localcuts */
1802 rval = grab_polished2_x (lp, 0.001,
1803 &closecount, &closelist, &closex);
1804 if (rval) {
1805 fprintf (stderr, "grab_polished_x failed\n");
1806 goto CLEANUP;
1807 }
1808
1809 {
1810 static int zzy = 1;
1811 char nbuf[1024];
1812 FILE *fout;
1813 int zzz;
1814 sprintf (nbuf, "x.polished.%d", zzy);
1815 fout = fopen (nbuf,"w");
1816 fprintf (fout, "%d %d\n", lp->graph.ncount, closecount);
1817 for (zzz = 0; zzz < closecount; zzz++) {
1818 fprintf (fout, "%d %d %.6f\n", closelist[2*zzz],
1819 closelist[2*zzz+1], closex[zzz]);
1820 }
1821 fclose (fout);
1822 sprintf (nbuf, "x.dusty.%d", zzy);
1823 fout = fopen (nbuf, "w");
1824 fprintf (fout, "%d %d\n", lp->graph.ncount, xcount);
1825 for (zzz = 0; zzz < xcount; zzz++) {
1826 fprintf (fout, "%d %d %.6f\n", xlist[2*zzz],
1827 xlist[2*zzz+1], x[zzz]);
1828 }
1829 fclose (fout);
1830 zzy++;
1831 }
1832
1833 otherimprove = newval - oldval;
1834 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol &&
1835 otherimprove < 0.5 * lcimprove) {
1836 int maxchunksize, firstsize;
1837 CCchunk_flag flags;
1838
1839 flags.dummy = 0;
1840 flags.permute = 0;
1841 flags.weighted = 0;
1842 flags.spheres = 0;
1843 flags.uncivilized = 0;
1844 flags.noshrink = 0;
1845 flags.nolift = 0;
1846
1847 if (sel->maxchunksize < 8) firstsize = sel->maxchunksize;
1848 else firstsize = 8;
1849 for (maxchunksize = firstsize;
1850 maxchunksize <= sel->maxchunksize;
1851 maxchunksize++) {
1852 flags.maxchunksize = maxchunksize;
1853 flags.spheresize = maxchunksize - 2;
1854
1855 CCutil_start_timer (&lp->stats.cuts_localcut);
1856 rval = CCchunk_localcuts (&cuts, &cutcount,
1857 lp->graph.ncount, closecount, closelist, closex,
1858 0.0, flags, &lc_timer, silent, rstate);
1859 if (rval) {
1860 fprintf (stderr, "LocalCuts failed\n");
1861 rval = 1; goto CLEANUP;
1862 }
1863 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1864 if (!silent) {
1865 printf ("Found %2d POLISHED LocalCuts in %.2f seconds\n",
1866 cutcount, z);
1867 fflush (stdout);
1868 }
1869 if (cutcount) {
1870 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1871 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1872 &xlist, &x, &newval, sel->usetighten,
1873 &istour, silent, rstate);
1874 if (rval) {
1875 fprintf (stderr, "call_add_cuts failed\n");
1876 goto CLEANUP;
1877 }
1878 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1879 if (istour) goto OUT_LOOP;
1880 }
1881 if (newval >= oldval + sel->nexttol) break;
1882 }
1883 }
1884
1885 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol) {
1886 int maxchunksize, firstsize;
1887 CCchunk_flag flags;
1888 double beforeval = newval;
1889
1890 flags.dummy = 0;
1891 flags.permute = 0;
1892 flags.weighted = 0;
1893 flags.spheres = 1;
1894 flags.uncivilized = 0;
1895 flags.noshrink = 0;
1896 flags.nolift = 0;
1897
1898 if (sel->maxchunksize < 8) firstsize = sel->maxchunksize;
1899 else firstsize = 8;
1900 for (maxchunksize = firstsize;
1901 maxchunksize <= sel->maxchunksize;
1902 maxchunksize++) {
1903 flags.maxchunksize = maxchunksize;
1904 flags.spheresize = maxchunksize - 2;
1905
1906 CCutil_start_timer (&lp->stats.cuts_localcut);
1907 rval = CCchunk_localcuts (&cuts, &cutcount,
1908 lp->graph.ncount, closecount, closelist, closex,
1909 0.0, flags, &lc_timer, silent, rstate);
1910 if (rval) {
1911 fprintf (stderr, "LocalCuts failed\n");
1912 rval = 1; goto CLEANUP;
1913 }
1914 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1915 if (!silent) {
1916 printf ("Found %2d POLISHED LocalCuts in %.2f seconds\n",
1917 cutcount, z);
1918 fflush (stdout);
1919 }
1920 if (cutcount) {
1921 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1922 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
1923 &xlist, &x, &newval, sel->usetighten,
1924 &istour, silent, rstate);
1925 if (rval) {
1926 fprintf (stderr, "call_add_cuts failed\n");
1927 goto CLEANUP;
1928 }
1929 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1930 if (istour) goto OUT_LOOP;
1931 }
1932 if (newval >= oldval + sel->nexttol) break;
1933 }
1934 lcimprove = newval - beforeval;
1935 }
1936 if (sel->maxchunksize > 0 && newval < oldval + sel->nexttol) {
1937 for (i = 0; i < 3; i++) {
1938 int maxchunksize, firstsize;
1939 CCchunk_flag flags;
1940 double beforeval = newval;
1941
1942 flags.dummy = 0;
1943 flags.permute = 0;
1944 flags.weighted = 0;
1945 flags.spheres = 0;
1946 flags.uncivilized = 0;
1947 flags.noshrink = 0;
1948 flags.nolift = 0;
1949
1950 if (i == 0) flags.dummy = 1;
1951 else if (i == 1) flags.permute = 1;
1952 else if (i == 2) flags.weighted = 1;
1953
1954
1955 if (sel->maxchunksize < 8) firstsize = sel->maxchunksize;
1956 else firstsize = 8;
1957 for (maxchunksize = firstsize;
1958 maxchunksize <= sel->maxchunksize;
1959 maxchunksize++) {
1960 flags.maxchunksize = maxchunksize;
1961 flags.spheresize = maxchunksize - 2;
1962
1963 CCutil_start_timer (&lp->stats.cuts_localcut);
1964 rval = CCchunk_localcuts (&cuts, &cutcount,
1965 lp->graph.ncount, closecount, closelist,
1966 closex, 0.0, flags, &lc_timer, silent,
1967 rstate);
1968 if (rval) {
1969 fprintf (stderr, "LocalCuts failed\n");
1970 rval = 1; goto CLEANUP;
1971 }
1972 z = CCutil_stop_timer (&lp->stats.cuts_localcut, 0);
1973 if (!silent) {
1974 printf ("Found %2d POLISHED LocalCuts in %.2f seconds\n",
1975 cutcount, z);
1976 fflush (stdout);
1977 }
1978 if (cutcount) {
1979 CCutil_start_timer (&lp->stats.cuts_localcut_opt);
1980 rval = call_add_cuts (lp, &cuts, &cut_added,
1981 &xcount, &xlist, &x, &newval,
1982 sel->usetighten, &istour, silent,
1983 rstate);
1984 if (rval) {
1985 fprintf (stderr, "call_add_cuts failed\n");
1986 goto CLEANUP;
1987 }
1988 CCutil_stop_timer (&lp->stats.cuts_localcut_opt, 0);
1989 if (istour) goto OUT_LOOP;
1990 }
1991 if (newval >= oldval + sel->nexttol) break;
1992 }
1993 lcimprove = newval - beforeval;
1994 }
1995 }
1996 #endif /* POLISHED_CHUNKS */
1997
1998 OUT_LOOP:
1999
2000 CC_IFFREE (xlist, int);
2001 CC_IFFREE (x, double);
2002
2003 CCutil_start_timer (&lp->stats.sparse_edge_check);
2004 rval = sparse_edge_check (lp, &eginside, &edge_added,
2005 (double *) NULL, silent, rstate);
2006 if (rval) {
2007 fprintf (stderr, "sparse_edge_check failed\n");
2008 rval = 1; goto CLEANUP;
2009 }
2010 if (!silent) {
2011 CCutil_stop_timer (&lp->stats.sparse_edge_check, 1);
2012 } else {
2013 CCutil_stop_timer (&lp->stats.sparse_edge_check, 0);
2014 }
2015
2016 if (savelp) {
2017 rval = CCtsp_write_probfile_sav (lp);
2018 if (rval) {
2019 fprintf (stderr, "CCtsp_write_probfile_sav failed\n");
2020 rval = 1; goto CLEANUP;
2021 }
2022 }
2023 if (lp->pool && savelp) {
2024 char buf[1024];
2025 if (!silent) {
2026 printf ("Write Pool: %d cuts\n", lp->pool->cutcount);
2027 fflush (stdout);
2028 }
2029 sprintf (buf, "%s.pul", lp->problabel);
2030 rval = CCtsp_write_cutpool (lp->graph.ncount, buf, lp->pool);
2031 if (rval) {
2032 fprintf (stderr, "CCtsp_write_cutpool failed\n");
2033 rval = 1; goto CLEANUP;
2034 }
2035 }
2036 if (lp->pool && sel->remotepool &&
2037 lp->pool->cutcount > lp->pool->savecount) {
2038 rval = CCtsp_send_newcuts (lp->graph.ncount, lp->pool,
2039 sel->remotehost, sel->remoteport);
2040 if (rval) {
2041 fprintf (stderr, "CCtsp_send_newcuts failed\n");
2042 rval = 0;
2043 }
2044 }
2045 if (!silent) {
2046 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 1);
2047 } else {
2048 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 0);
2049 }
2050
2051 rval = lp_value (lp, &priceval);
2052 if (rval) {rval = 1; goto CLEANUP;}
2053
2054 if (lp->lowerbound >= lp->upperbound - 0.9) {
2055 if (!silent) {
2056 printf ("Stop cutting, lp bound is within 0.9 of upperbound\n");
2057 fflush (stdout);
2058 }
2059 goto CLEANUP;
2060 }
2061 loopcount++;
2062 if (silent && !lp->full_edges_valid) {
2063 printf (" LP Value %2d: %f (%.2f seconds)\n", loopcount,
2064 priceval, CCutil_zeit () - szeit);
2065 fflush (stdout);
2066 }
2067 } while ((newval > oldval + sel->roundtol ||
2068 priceval < newval - sel->roundtol) &&
2069 loopcount < LOOP_FULL &&
2070 (lp->full_edges_valid || priceval < lp->upperbound));
2071
2072 CCutil_start_timer (&lp->stats.full_edge_check);
2073 rval = full_edge_check (lp, &edge_added, silent, rstate);
2074 if (rval) {
2075 fprintf (stderr, "full_edge_check failed\n");
2076 rval = 1; goto CLEANUP;
2077 }
2078 if (!silent) {
2079 CCutil_stop_timer (&lp->stats.full_edge_check, 1);
2080 } else {
2081 CCutil_stop_timer (&lp->stats.full_edge_check, 0);
2082 }
2083 if (savelp) {
2084 rval = CCtsp_write_probfile_sav (lp);
2085 if (rval) {
2086 fprintf (stderr, "CCtsp_write_probfile_sav failed\n");
2087 rval = 1; goto CLEANUP;
2088 }
2089 }
2090 rval = lp_value (lp, &priceval);
2091 if (rval) {rval = 1; goto CLEANUP;}
2092
2093 if (sel->extra_connect && priceval >= newval - sel->roundtol &&
2094 loopcount != LOOP_FULL) {
2095 if (!silent) {
2096 printf ("Check connectivity before exiting cutting_loop\n");
2097 fflush (stdout);
2098 }
2099
2100 CCutil_start_timer (&lp->stats.cuts_extraconnect);
2101
2102 rval = lp_x (lp, &xcount, &xlist, &x);
2103 if (rval) {rval = 1; goto CLEANUP;}
2104
2105 rval = CCtsp_connect_cuts (&cuts, &cutcount_connect,
2106 lp->graph.ncount, xcount, xlist, x);
2107 if (rval) {
2108 fprintf (stderr, "CCtsp_connect_cuts failed\n");
2109 rval = 1; goto CLEANUP;
2110 }
2111 z = CCutil_stop_timer (&lp->stats.cuts_extraconnect, 0);
2112 if (!silent) {
2113 printf ("Found %2d extra connect cuts in %.2f seconds\n",
2114 cutcount_connect, z);
2115 fflush (stdout);
2116 }
2117 if (cutcount_connect) {
2118 CCutil_start_timer (&lp->stats.cuts_extraconnect_opt);
2119 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2120 &xlist, &x, &newval, sel->usetighten,
2121 (int *) NULL, silent, rstate);
2122 if (rval) {
2123 fprintf (stderr, "call_add_cuts failed\n");
2124 goto CLEANUP;
2125 }
2126 CCutil_stop_timer (&lp->stats.cuts_extraconnect_opt, 0);
2127 }
2128
2129 CC_FREE (xlist, int);
2130 CC_FREE (x, double);
2131 }
2132 outside++;
2133
2134 /* This last bit will cause a second pass for large probs, with */
2135 /* an updated tolerance. */
2136
2137 if (!sel->fastcuts && lp->full_edges_valid == 0 && outside == 1 &&
2138 lp->graph.ncount >= 400 &&
2139 lp->lowerbound < lp->upperbound - 0.9) {
2140 rval = CCtsp_cutselect_set_tols (sel, lp, 1, silent);
2141 if (rval) {
2142 fprintf (stderr, "CCtsp_cutselect_set_tols failed\n");
2143 rval = 1; goto CLEANUP;
2144 }
2145 loopcount = LOOP_FULL; /* to run again */
2146 }
2147 } while (priceval < newval - sel->roundtol || loopcount == LOOP_FULL ||
2148 cutcount_connect);
2149
2150 CLEANUP:
2151
2152 if (rval == 2) {
2153 printf ("LP is infeasible in cutting_loop\n");
2154 fflush (stdout);
2155 } else if (rval) {
2156 fprintf (stderr, "failure in cutting_loop\n");
2157 }
2158 if (!silent) {
2159 CCutil_stop_timer (&lp->stats.cutting_loop, 1);
2160 printf ("Number of outside rounds: %d\n", outside);
2161 fflush (stdout);
2162 } else {
2163 CCutil_stop_timer (&lp->stats.cutting_loop, 0);
2164 }
2165
2166 if (eginside.ncount)
2167 CCtsp_free_edgegenerator (&eginside);
2168 CC_IFFREE (xlist, int);
2169 CC_IFFREE (x, double);
2170 CC_IFFREE (closelist, int);
2171 CC_IFFREE (closex, double);
2172
2173 sel->nexttol = save_nexttol;
2174 sel->roundtol = save_roundtol;
2175
2176 return rval;
2177 }
2178
2179 #define CC_NO_NEAREST_SUBTOUR 50
2180 #define CC_SUBTOUR_ROUNDS 5
2181
CCtsp_subtour_loop(CCtsp_lp * lp,int silent,CCrandstate * rstate)2182 int CCtsp_subtour_loop (CCtsp_lp *lp, int silent, CCrandstate *rstate)
2183 {
2184 int rval = 0;
2185 int xcount, cutcount, cut_added, edge_added;
2186 int outside = 0;
2187 int inside = 0;
2188 int tighten = 0;
2189 double newval, priceval;
2190 int *xlist = (int *) NULL;
2191 double *x = (double *) NULL;
2192 CCtsp_lpcut_in *cuts = (CCtsp_lpcut_in *) NULL;
2193 CCtsp_edgegenerator eginside;
2194 double z;
2195
2196 CCutil_start_timer (&lp->stats.cutting_loop);
2197 eginside.ncount = 0;
2198 if (lp->fulladj) {
2199 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
2200 lp->fulladj, 0, silent, rstate);
2201 if (rval) {
2202 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
2203 rval = 1; goto CLEANUP;
2204 }
2205 } else if (lp->dat) {
2206 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
2207 (CCtsp_genadj *) NULL, CC_NO_NEAREST_SUBTOUR, silent, rstate);
2208 if (rval) {
2209 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
2210 rval = 1; goto CLEANUP;
2211 }
2212 }
2213
2214 rval = CCtsp_get_lp_result (lp, (double *) NULL, (double *) NULL,
2215 (int *) NULL, (int **) NULL, (double **) NULL, (double **) NULL,
2216 (double **) NULL, (double **) NULL);
2217 if (rval) {
2218 fprintf (stderr, "CCtsp_get_lp_result failed\n");
2219 rval = 1; goto CLEANUP;
2220 }
2221
2222 do {
2223 do {
2224 cut_added = 0;
2225
2226 CCutil_start_timer (&lp->stats.cutting_inner_loop);
2227
2228 rval = lp_x (lp, &xcount, &xlist, &x);
2229 if (rval) {rval = 1; goto CLEANUP;}
2230
2231 /**** Connect Cuts ****/
2232
2233 CCutil_start_timer (&lp->stats.cuts_connect);
2234 rval = CCtsp_connect_cuts (&cuts, &cutcount, lp->graph.ncount,
2235 xcount, xlist, x);
2236 if (rval) {
2237 fprintf (stderr, "CCtsp_connect_cuts failed\n");
2238 rval = 1; goto CLEANUP;
2239 }
2240 z = CCutil_stop_timer (&lp->stats.cuts_connect, 0);
2241 if (!silent) {
2242 printf ("Found %2d connect cuts in %.2f seconds\n",
2243 cutcount, z);
2244 fflush (stdout);
2245 }
2246 if (cutcount) {
2247 CCutil_start_timer (&lp->stats.cuts_connect_opt);
2248 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2249 &xlist, &x, &newval, tighten, (int *) NULL,
2250 silent, rstate);
2251 if (rval) {
2252 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2253 }
2254 CCutil_stop_timer (&lp->stats.cuts_connect_opt, 0);
2255 }
2256
2257 /**** Shrink Cuts ****/
2258
2259 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
2260 rval = CCtsp_shrink_subtours (&cuts, &cutcount, lp->graph.ncount,
2261 xcount, xlist, x);
2262 if (rval) {
2263 fprintf (stderr, "CCtsp_shrink_subtours failed\n");
2264 rval = 1; goto CLEANUP;
2265 }
2266 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
2267 if (!silent) {
2268 printf ("Found %2d shrink subtours in %.2f seconds\n",
2269 cutcount, z);
2270 fflush (stdout);
2271 }
2272 if (cutcount) {
2273 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
2274 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2275 &xlist, &x, &newval, tighten, (int *) NULL,
2276 silent, rstate);
2277 if (rval) {
2278 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2279 }
2280 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
2281 }
2282
2283
2284 /**** Linear Cuts ****/
2285
2286 CCutil_start_timer (&lp->stats.cuts_segment);
2287 rval = CCtsp_segment_cuts (&cuts, &cutcount, lp->graph.ncount,
2288 xcount, xlist, x);
2289 if (rval) {
2290 fprintf (stderr, "CCtsp_segment_cuts failed\n");
2291 rval = 1; goto CLEANUP;
2292 }
2293 z = CCutil_stop_timer (&lp->stats.cuts_segment, 0);
2294 if (!silent) {
2295 printf ("Found %2d segment cuts in %.2f seconds\n",
2296 cutcount, z);
2297 fflush (stdout);
2298 }
2299 if (cutcount) {
2300 CCutil_start_timer (&lp->stats.cuts_segment_opt);
2301 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2302 &xlist, &x, &newval, tighten, (int *) NULL,
2303 silent, rstate);
2304 if (rval) {
2305 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2306 }
2307 CCutil_stop_timer (&lp->stats.cuts_segment_opt, 0);
2308 }
2309
2310
2311 /**** Exact Cuts ****/
2312
2313 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
2314 rval = CCtsp_exact_subtours (&cuts, &cutcount, lp->graph.ncount,
2315 xcount, xlist, x);
2316 if (rval) {
2317 fprintf (stderr, "CCtsp_exact_subtours failed\n");
2318 rval = 1; goto CLEANUP;
2319 }
2320 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
2321 if (!silent) {
2322 printf ("Found %2d exact subtours in %.2f seconds\n",
2323 cutcount, z);
2324 fflush (stdout);
2325 }
2326 if (cutcount) {
2327 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
2328 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2329 &xlist, &x, &newval, tighten, (int *) NULL,
2330 silent, rstate);
2331 if (rval) {
2332 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2333 }
2334 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
2335 }
2336
2337 CC_FREE (xlist, int);
2338 CC_FREE (x, double);
2339
2340 if (!cut_added || (inside % CC_SUBTOUR_ROUNDS) == 0) {
2341 CCutil_start_timer (&lp->stats.sparse_edge_check);
2342 rval = sparse_edge_check (lp, &eginside, &edge_added,
2343 (double *) NULL, silent, rstate);
2344 if (rval) {
2345 fprintf (stderr, "sparse_edge_check failed\n");
2346 rval = 1; goto CLEANUP;
2347 }
2348 if (!silent) {
2349 CCutil_stop_timer (&lp->stats.sparse_edge_check, 1);
2350 } else {
2351 CCutil_stop_timer (&lp->stats.sparse_edge_check, 0);
2352 }
2353 }
2354 if (!silent) {
2355 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 1);
2356 } else {
2357 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 0);
2358 }
2359 inside++;
2360 if (silent) {
2361 rval = lp_value (lp, &priceval);
2362 if (rval) {rval = 1; goto CLEANUP;}
2363 printf (" LP Value %2d: %f\n", inside, priceval);
2364 fflush (stdout);
2365 }
2366 } while (edge_added || cut_added);
2367
2368 CCutil_start_timer (&lp->stats.full_edge_check);
2369 rval = full_edge_check (lp, &edge_added, silent, rstate);
2370 if (rval) {
2371 fprintf (stderr, "full_edge_check failed\n");
2372 rval = 1; goto CLEANUP;
2373 }
2374 if (!silent) {
2375 CCutil_stop_timer (&lp->stats.full_edge_check, 1);
2376 } else {
2377 CCutil_stop_timer (&lp->stats.full_edge_check, 0);
2378 }
2379 outside++;
2380 } while (edge_added);
2381
2382 CLEANUP:
2383
2384 if (rval == 2) {
2385 printf ("LP is infeasible in subtour_loop\n");
2386 fflush (stdout);
2387 } else if (rval) {
2388 fprintf (stderr, "failure in subtour_loop\n");
2389 }
2390 z = CCutil_stop_timer (&lp->stats.cutting_loop, 1);
2391 printf ("Time in cutting routine: %.2f\n", z);
2392 CCutil_total_timer (&lp->stats.cuts_connect, 1);
2393 CCutil_total_timer (&lp->stats.cuts_segment, 1);
2394 CCutil_total_timer (&lp->stats.cuts_exactsubtour, 1);
2395
2396 printf ("Number of outside rounds: %d (%d inside)\n", outside, inside);
2397 fflush (stdout);
2398
2399 if (eginside.ncount)
2400 CCtsp_free_edgegenerator (&eginside);
2401 CC_IFFREE (xlist, int);
2402 CC_IFFREE (x, double);
2403
2404 return rval;
2405 }
2406
CCtsp_blossom_loop(CCtsp_lp * lp,int silent,CCrandstate * rstate)2407 int CCtsp_blossom_loop (CCtsp_lp *lp, int silent, CCrandstate *rstate)
2408 {
2409 int rval = 0;
2410 int xcount, cutcount, cut_added, edge_added;
2411 int outside = 0;
2412 int inside = 0;
2413 int tighten = 0;
2414 double newval, priceval;
2415 int *xlist = (int *) NULL;
2416 double *x = (double *) NULL;
2417 CCtsp_lpcut_in *cuts = (CCtsp_lpcut_in *) NULL;
2418 CCtsp_edgegenerator eginside;
2419 double z;
2420
2421 CCutil_start_timer (&lp->stats.cutting_loop);
2422 eginside.ncount = 0;
2423 if (lp->fulladj) {
2424 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
2425 lp->fulladj, 0, silent, rstate);
2426 if (rval) {
2427 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
2428 rval = 1; goto CLEANUP;
2429 }
2430 } else if (lp->dat) {
2431 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
2432 (CCtsp_genadj *) NULL, CC_NO_NEAREST_SUBTOUR, silent, rstate);
2433 if (rval) {
2434 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
2435 rval = 1; goto CLEANUP;
2436 }
2437 }
2438
2439 rval = CCtsp_get_lp_result (lp, (double *) NULL, (double *) NULL,
2440 (int *) NULL, (int **) NULL, (double **) NULL, (double **) NULL,
2441 (double **) NULL, (double **) NULL);
2442 if (rval) {
2443 fprintf (stderr, "CCtsp_get_lp_result failed\n");
2444 rval = 1; goto CLEANUP;
2445 }
2446
2447 do {
2448 do {
2449 cut_added = 0;
2450
2451 CCutil_start_timer (&lp->stats.cutting_inner_loop);
2452
2453 rval = lp_x (lp, &xcount, &xlist, &x);
2454 if (rval) {rval = 1; goto CLEANUP;}
2455
2456
2457 /**** Fast Blossoms ****/
2458
2459 CCutil_start_timer (&lp->stats.cuts_fastblossom);
2460 rval = CCtsp_fastblossom (&cuts, &cutcount, lp->graph.ncount,
2461 xcount, xlist, x);
2462 if (rval) {
2463 fprintf (stderr, "CCtsp_fastblossom failed\n");
2464 rval = 1; goto CLEANUP;
2465 }
2466 z = CCutil_stop_timer (&lp->stats.cuts_fastblossom, 0);
2467 if (!silent) {
2468 printf ("Found %2d Fast Blossoms in %.2f seconds\n",
2469 cutcount, z);
2470 fflush (stdout);
2471 }
2472 if (cutcount) {
2473 CCutil_start_timer (&lp->stats.cuts_fastblossom_opt);
2474 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2475 &xlist, &x, &newval, tighten, (int *) NULL,
2476 silent, rstate);
2477 if (rval) {
2478 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2479 }
2480 CCutil_stop_timer (&lp->stats.cuts_fastblossom_opt, 0);
2481 }
2482
2483
2484 /**** Groetschel-Holland Fast Blossoms ****/
2485
2486 CCutil_start_timer (&lp->stats.cuts_ghfastblossom);
2487 rval = CCtsp_ghfastblossom (&cuts, &cutcount, lp->graph.ncount,
2488 xcount, xlist, x);
2489 if (rval) {
2490 fprintf (stderr, "CCtsp_ghfastblossom failed\n");
2491 rval = 1; goto CLEANUP;
2492 }
2493 z = CCutil_stop_timer (&lp->stats.cuts_ghfastblossom, 0);
2494 if (!silent) {
2495 printf ("Found %2d Groetschel-Holland Blossoms in %.2f seconds\n",
2496 cutcount, z);
2497 fflush (stdout);
2498 }
2499 if (cutcount) {
2500 CCutil_start_timer (&lp->stats.cuts_ghfastblossom_opt);
2501 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2502 &xlist, &x, &newval, tighten, (int *) NULL,
2503 silent, rstate);
2504 if (rval) {
2505 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2506 }
2507 CCutil_stop_timer (&lp->stats.cuts_ghfastblossom_opt, 0);
2508 }
2509
2510
2511 /**** Exact Blossoms ****/
2512
2513 CCutil_start_timer (&lp->stats.cuts_exactblossom);
2514 rval = CCtsp_exactblossom (&cuts, &cutcount, lp->graph.ncount,
2515 xcount, xlist, x, rstate);
2516 if (rval) {
2517 fprintf (stderr, "CCtsp_exactblossom failed\n");
2518 rval = 1; goto CLEANUP;
2519 }
2520 z = CCutil_stop_timer (&lp->stats.cuts_exactblossom, 0);
2521 if (!silent) {
2522 printf ("Found %2d Exact Blossoms in %.2f seconds\n",
2523 cutcount, z);
2524 fflush (stdout);
2525 }
2526 if (cutcount) {
2527 CCutil_start_timer (&lp->stats.cuts_exactblossom_opt);
2528 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2529 &xlist, &x, &newval, tighten, (int *) NULL,
2530 silent, rstate);
2531 if (rval) {
2532 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2533 }
2534 CCutil_stop_timer (&lp->stats.cuts_exactblossom_opt, 0);
2535 }
2536
2537 CC_FREE (xlist, int);
2538 CC_FREE (x, double);
2539
2540 if (!cut_added || (inside % CC_SUBTOUR_ROUNDS) == 0) {
2541 CCutil_start_timer (&lp->stats.sparse_edge_check);
2542 rval = sparse_edge_check (lp, &eginside, &edge_added,
2543 (double *) NULL, silent, rstate);
2544 if (rval) {
2545 fprintf (stderr, "sparse_edge_check failed\n");
2546 rval = 1; goto CLEANUP;
2547 }
2548 if (!silent) {
2549 CCutil_stop_timer (&lp->stats.sparse_edge_check, 1);
2550 } else {
2551 CCutil_stop_timer (&lp->stats.sparse_edge_check, 0);
2552 }
2553 }
2554 if (!silent) {
2555 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 1);
2556 } else {
2557 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 0);
2558 }
2559 inside++;
2560 if (silent) {
2561 rval = lp_value (lp, &priceval);
2562 if (rval) {rval = 1; goto CLEANUP;}
2563 printf (" LP Value %2d: %f\n", inside, priceval);
2564 fflush (stdout);
2565 }
2566 } while (edge_added || cut_added);
2567
2568 CCutil_start_timer (&lp->stats.full_edge_check);
2569 rval = full_edge_check (lp, &edge_added, silent, rstate);
2570 if (rval) {
2571 fprintf (stderr, "full_edge_check failed\n");
2572 rval = 1; goto CLEANUP;
2573 }
2574 if (!silent) {
2575 CCutil_stop_timer (&lp->stats.full_edge_check, 1);
2576 } else {
2577 CCutil_stop_timer (&lp->stats.full_edge_check, 0);
2578 }
2579 outside++;
2580 } while (edge_added);
2581
2582 CLEANUP:
2583
2584 if (rval == 2) {
2585 printf ("LP is infeasible in blossom_loop\n");
2586 fflush (stdout);
2587 } else if (rval) {
2588 fprintf (stderr, "failure in blossom_loop\n");
2589 }
2590 z = CCutil_stop_timer (&lp->stats.cutting_loop, 1);
2591 printf ("Time in cutting routine: %.2f\n", z);
2592 CCutil_total_timer (&lp->stats.cuts_fastblossom, 1);
2593 CCutil_total_timer (&lp->stats.cuts_exactblossom, 1);
2594
2595 printf ("Number of outside rounds: %d (%d inside)\n", outside, inside);
2596 fflush (stdout);
2597
2598 if (eginside.ncount)
2599 CCtsp_free_edgegenerator (&eginside);
2600 CC_IFFREE (xlist, int);
2601 CC_IFFREE (x, double);
2602
2603 return rval;
2604 }
2605
CCtsp_subtour_and_blossom_loop(CCtsp_lp * lp,int silent,CCrandstate * rstate)2606 int CCtsp_subtour_and_blossom_loop (CCtsp_lp *lp, int silent,
2607 CCrandstate *rstate)
2608 {
2609 int rval = 0;
2610 int xcount, cutcount, cut_added, edge_added, blossom_added;
2611 int outside = 0;
2612 int inside = 0;
2613 int tighten = 0;
2614 double newval, priceval;
2615 int *xlist = (int *) NULL;
2616 double *x = (double *) NULL;
2617 CCtsp_lpcut_in *cuts = (CCtsp_lpcut_in *) NULL;
2618 CCtsp_edgegenerator eginside;
2619 double z;
2620
2621 CCutil_start_timer (&lp->stats.cutting_loop);
2622 eginside.ncount = 0;
2623 if (lp->fulladj) {
2624 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
2625 lp->fulladj, 0, silent, rstate);
2626 if (rval) {
2627 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
2628 rval = 1; goto CLEANUP;
2629 }
2630 } else if (lp->dat) {
2631 rval = CCtsp_init_edgegenerator (&eginside, lp->graph.ncount, lp->dat,
2632 (CCtsp_genadj *) NULL, CC_NO_NEAREST_SUBTOUR, silent, rstate);
2633 if (rval) {
2634 fprintf (stderr, "CCtsp_init_edgegenerator (sparse) failed\n");
2635 rval = 1; goto CLEANUP;
2636 }
2637 }
2638
2639 rval = CCtsp_get_lp_result (lp, (double *) NULL, (double *) NULL,
2640 (int *) NULL, (int **) NULL, (double **) NULL, (double **) NULL,
2641 (double **) NULL, (double **) NULL);
2642 if (rval) {
2643 fprintf (stderr, "CCtsp_get_lp_result failed\n");
2644 rval = 1; goto CLEANUP;
2645 }
2646
2647 do {
2648 do {
2649 cut_added = blossom_added = 0;
2650
2651 CCutil_start_timer (&lp->stats.cutting_inner_loop);
2652
2653 rval = lp_x (lp, &xcount, &xlist, &x);
2654 if (rval) {rval = 1; goto CLEANUP;}
2655
2656
2657 /**** Connect Cuts ****/
2658
2659 CCutil_start_timer (&lp->stats.cuts_connect);
2660 rval = CCtsp_connect_cuts (&cuts, &cutcount, lp->graph.ncount,
2661 xcount, xlist, x);
2662 if (rval) {
2663 fprintf (stderr, "CCtsp_connect_cuts failed\n");
2664 rval = 1; goto CLEANUP;
2665 }
2666 z = CCutil_stop_timer (&lp->stats.cuts_connect, 0);
2667 if (!silent) {
2668 printf ("Found %2d connect cuts in %.2f seconds\n",
2669 cutcount, z);
2670 fflush (stdout);
2671 }
2672 if (cutcount) {
2673 CCutil_start_timer (&lp->stats.cuts_connect_opt);
2674 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2675 &xlist, &x, &newval, tighten, (int *) NULL,
2676 silent, rstate);
2677 if (rval) {
2678 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2679 }
2680 CCutil_stop_timer (&lp->stats.cuts_connect_opt, 0);
2681 }
2682
2683
2684 /**** Linear Cuts ****/
2685
2686 CCutil_start_timer (&lp->stats.cuts_segment);
2687 rval = CCtsp_segment_cuts (&cuts, &cutcount, lp->graph.ncount,
2688 xcount, xlist, x);
2689 if (rval) {
2690 fprintf (stderr, "CCtsp_segment_cuts failed\n");
2691 rval = 1; goto CLEANUP;
2692 }
2693 z = CCutil_stop_timer (&lp->stats.cuts_segment, 0);
2694 if (!silent) {
2695 printf ("Found %2d segment cuts in %.2f seconds\n",
2696 cutcount, z);
2697 fflush (stdout);
2698 }
2699 if (cutcount) {
2700 CCutil_start_timer (&lp->stats.cuts_segment_opt);
2701 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2702 &xlist, &x, &newval, tighten, (int *) NULL,
2703 silent,rstate);
2704 if (rval) {
2705 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2706 }
2707 CCutil_stop_timer (&lp->stats.cuts_segment_opt, 0);
2708 }
2709
2710
2711 /**** Exact Cuts ****/
2712
2713 CCutil_start_timer (&lp->stats.cuts_exactsubtour);
2714 rval = CCtsp_exact_subtours (&cuts, &cutcount, lp->graph.ncount,
2715 xcount, xlist, x);
2716 if (rval) {
2717 fprintf (stderr, "CCtsp_exact_subtours failed\n");
2718 rval = 1; goto CLEANUP;
2719 }
2720 z = CCutil_stop_timer (&lp->stats.cuts_exactsubtour, 0);
2721 if (!silent) {
2722 printf ("Found %2d exact subtours in %.2f seconds\n",
2723 cutcount, z);
2724 fflush (stdout);
2725 }
2726 if (cutcount) {
2727 CCutil_start_timer (&lp->stats.cuts_exactsubtour_opt);
2728 rval = call_add_cuts (lp, &cuts, &cut_added, &xcount,
2729 &xlist, &x, &newval, tighten, (int *) NULL,
2730 silent, rstate);
2731 if (rval) {
2732 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2733 }
2734 CCutil_stop_timer (&lp->stats.cuts_exactsubtour_opt, 0);
2735 }
2736
2737 /**** Fast Blossoms ****/
2738
2739 CCutil_start_timer (&lp->stats.cuts_fastblossom);
2740 rval = CCtsp_fastblossom (&cuts, &cutcount, lp->graph.ncount,
2741 xcount, xlist, x);
2742 if (rval) {
2743 fprintf (stderr, "CCtsp_fastblossom failed\n");
2744 rval = 1; goto CLEANUP;
2745 }
2746 z = CCutil_stop_timer (&lp->stats.cuts_fastblossom, 0);
2747 if (!silent) {
2748 printf ("Found %2d Fast Blossoms in %.2f seconds\n",
2749 cutcount, z);
2750 fflush (stdout);
2751 }
2752 if (cutcount) {
2753 CCutil_start_timer (&lp->stats.cuts_fastblossom_opt);
2754 rval = call_add_cuts (lp, &cuts, &blossom_added, &xcount,
2755 &xlist, &x, &newval, tighten, (int *) NULL,
2756 silent, rstate);
2757 if (rval) {
2758 fprintf (stderr, "call_add_cuts failed\n"); goto CLEANUP;
2759 }
2760 CCutil_stop_timer (&lp->stats.cuts_fastblossom_opt, 0);
2761 }
2762
2763
2764 CC_FREE (xlist, int);
2765 CC_FREE (x, double);
2766
2767 if (!cut_added || (inside % CC_SUBTOUR_ROUNDS) == 0) {
2768 CCutil_start_timer (&lp->stats.sparse_edge_check);
2769 rval = sparse_edge_check (lp, &eginside, &edge_added,
2770 (double *) NULL, silent, rstate);
2771 if (rval) {
2772 fprintf (stderr, "sparse_edge_check failed\n");
2773 rval = 1; goto CLEANUP;
2774 }
2775 if (!silent) {
2776 CCutil_stop_timer (&lp->stats.sparse_edge_check, 1);
2777 } else {
2778 CCutil_stop_timer (&lp->stats.sparse_edge_check, 0);
2779 }
2780 }
2781 if (!silent) {
2782 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 1);
2783 } else {
2784 CCutil_stop_timer (&lp->stats.cutting_inner_loop, 0);
2785 }
2786 inside++;
2787 if (silent) {
2788 rval = lp_value (lp, &priceval);
2789 if (rval) {rval = 1; goto CLEANUP;}
2790 printf (" LP Value %2d: %f\n", inside, priceval);
2791 fflush (stdout);
2792 }
2793 } while (edge_added || cut_added || blossom_added);
2794
2795 CCutil_start_timer (&lp->stats.full_edge_check);
2796 rval = full_edge_check (lp, &edge_added, silent, rstate);
2797 if (rval) {
2798 fprintf (stderr, "full_edge_check failed\n");
2799 rval = 1; goto CLEANUP;
2800 }
2801 if (!silent) {
2802 CCutil_stop_timer (&lp->stats.full_edge_check, 1);
2803 } else {
2804 CCutil_stop_timer (&lp->stats.full_edge_check, 0);
2805 }
2806 outside++;
2807
2808 } while (edge_added);
2809
2810 CLEANUP:
2811
2812 if (rval == 2) {
2813 printf ("LP is infeasible in subtour_and_blossom_loop\n");
2814 fflush (stdout);
2815 } else if (rval) {
2816 fprintf (stderr, "failure in subtour_and_blossom_loop\n");
2817 }
2818 z = CCutil_stop_timer (&lp->stats.cutting_loop, 1);
2819 printf ("Time in cutting routine: %.2f\n", z);
2820 CCutil_total_timer (&lp->stats.cuts_connect, 1);
2821 CCutil_total_timer (&lp->stats.cuts_segment, 1);
2822 CCutil_total_timer (&lp->stats.cuts_exactsubtour, 1);
2823 CCutil_total_timer (&lp->stats.cuts_fastblossom, 1);
2824
2825
2826 printf ("Number of outside rounds: %d (%d inside)\n", outside, inside);
2827 fflush (stdout);
2828
2829 if (eginside.ncount)
2830 CCtsp_free_edgegenerator (&eginside);
2831 CC_IFFREE (xlist, int);
2832 CC_IFFREE (x, double);
2833
2834 return rval;
2835 }
2836
call_add_cuts(CCtsp_lp * lp,CCtsp_lpcut_in ** cuts,int * cut_added,int * xcount,int ** xlist,double ** x,double * val,int tighten,int * istour,int silent,CCrandstate * rstate)2837 static int call_add_cuts (CCtsp_lp *lp, CCtsp_lpcut_in **cuts, int *cut_added,
2838 int *xcount, int **xlist, double **x, double *val, int tighten,
2839 int *istour, int silent, CCrandstate *rstate)
2840 {
2841 int rval = 0;
2842 double dval;
2843 double szeit = CCutil_zeit ();
2844
2845 if (istour) *istour = 0;
2846
2847 CC_IFFREE (*xlist, int);
2848 CC_IFFREE (*x, double);
2849
2850 CCtsp_add_cuts_to_queue (lp, cuts);
2851 rval = CCtsp_process_cuts (lp, cut_added, tighten, silent, rstate);
2852 if (rval) {
2853 fprintf (stderr, "process_cuts failed\n"); goto CLEANUP;
2854 }
2855
2856 rval = lp_value (lp, val);
2857 if (rval) {
2858 fprintf (stderr, "lp_value failed\n"); rval = 1; goto CLEANUP;
2859 }
2860 if (!silent) {
2861 printf (" Add %2d cuts (Total %d), LP: %f (%.2f seconds)\n",
2862 *cut_added, lp->cuts.cutcount, *val,
2863 CCutil_zeit () - szeit);
2864 fflush (stdout);
2865 }
2866
2867 rval = lp_x (lp, xcount, xlist, x);
2868 if (rval) {
2869 fprintf (stderr, "lp_x failed\n"); rval = 1; goto CLEANUP;
2870 }
2871
2872 if (istour) {
2873 rval = CCtsp_check_integral (lp, &dval, (int **) NULL, istour,
2874 silent);
2875 if (rval) {
2876 fprintf (stderr, "CCtsp_check_integral failed\n"); goto CLEANUP;
2877 }
2878 }
2879
2880 CLEANUP:
2881
2882 return rval;
2883 }
2884
lp_value(CCtsp_lp * lp,double * val)2885 static int lp_value (CCtsp_lp *lp, double *val)
2886 {
2887 int rval;
2888
2889 rval = CCtsp_get_lp_result (lp, val, (double *) NULL, (int *) NULL,
2890 (int **) NULL, (double **) NULL, (double **) NULL,
2891 (double **) NULL, (double **) NULL);
2892 if (rval) fprintf (stderr, "CCtsp_get_lp_result failed\n");
2893 return rval;
2894 }
2895
lp_x(CCtsp_lp * lp,int * xcount,int ** xlist,double ** x)2896 static int lp_x (CCtsp_lp *lp, int *xcount, int **xlist, double **x)
2897 {
2898 int rval;
2899
2900 rval = CCtsp_get_lp_result (lp, (double *) NULL, (double *) NULL, xcount,
2901 xlist, x, (double **) NULL, (double **) NULL,
2902 (double **) NULL);
2903 if (rval) fprintf (stderr, "CCtsp_get_lp_result failed\n");
2904 return rval;
2905 }
2906
CCtsp_pricing_loop(CCtsp_lp * lp,double * bnd,int silent,CCrandstate * rstate)2907 int CCtsp_pricing_loop (CCtsp_lp *lp, double *bnd, int silent,
2908 CCrandstate *rstate)
2909 {
2910 CCtsp_edgegenerator eg;
2911 int nadded;
2912 int rval = 0;
2913
2914 eg.ncount = 0;
2915 if (!lp->full_edges_valid) {
2916 fprintf (stderr, "CCtsp_pricing_loop called without valid edges\n");
2917 rval = 1; goto CLEANUP;
2918 }
2919
2920
2921 rval = CCtsp_init_edgegenerator (&eg, lp->graph.ncount, lp->dat,
2922 lp->fulladj, 0, silent, rstate);
2923 if (rval) {
2924 fprintf (stderr, "CCtsp_init_edgegenerator failed\n"); goto CLEANUP;
2925 }
2926 rval = sparse_edge_check (lp, &eg, &nadded, bnd, silent, rstate);
2927 if (rval) {
2928 fprintf (stderr, "sparse_edge_check failed\n"); goto CLEANUP;
2929 }
2930
2931 CLEANUP:
2932
2933 if (eg.ncount) {
2934 CCtsp_free_edgegenerator (&eg);
2935 }
2936 return rval;
2937 }
2938
full_edge_check(CCtsp_lp * lp,int * nadded,int silent,CCrandstate * rstate)2939 static int full_edge_check (CCtsp_lp *lp, int *nadded, int silent,
2940 CCrandstate *rstate)
2941 {
2942 int rval;
2943 CCtsp_edgegenerator eg;
2944 double val, penalty;
2945
2946 if (lp->dat && (!lp->full_edges_valid)) {
2947 rval = CCtsp_init_edgegenerator (&eg, lp->graph.ncount, lp->dat,
2948 (CCtsp_genadj *) NULL, CCtsp_PRICE_COMPLETE_GRAPH, silent,
2949 rstate);
2950 if (rval) {
2951 fprintf (stderr, "CCtsp_init_edgegenerator failed\n"); return rval;
2952 }
2953
2954 rval = CCtsp_addbad_variables (lp, &eg, &penalty, nadded,
2955 CCtsp_PRICE_RCTHRESH, CCtsp_PRICE_MAXPENALTY, 0,
2956 (int *) NULL, silent, rstate);
2957 if (rval) {
2958 fprintf (stderr, "CCtsp_addbad_variables failed\n");
2959 CCtsp_free_edgegenerator (&eg);
2960 return rval;
2961 }
2962 CCtsp_free_edgegenerator (&eg);
2963 if (!silent) {
2964 printf ("%d edges added, penalty %f\n", *nadded, penalty);
2965 fflush (stdout);
2966 }
2967
2968 rval = lp_value (lp, &val);
2969 if (rval) return rval;
2970
2971 if (val + penalty > lp->lowerbound) {
2972 printf ("New lower bound: %f\n", val+ penalty);
2973 fflush (stdout);
2974 lp->lowerbound = val + penalty;
2975 }
2976 } else {
2977 *nadded = 0;
2978 }
2979 return 0;
2980 }
2981
sparse_edge_check(CCtsp_lp * lp,CCtsp_edgegenerator * eg,int * nadded,double * bnd,int silent,CCrandstate * rstate)2982 static int sparse_edge_check (CCtsp_lp *lp, CCtsp_edgegenerator *eg,
2983 int *nadded, double *bnd, int silent, CCrandstate *rstate)
2984 {
2985 double val, penalty;
2986 int rval;
2987
2988 if (bnd) *bnd = -CCtsp_LP_MAXDOUBLE;
2989
2990 if (eg->ncount > 0) {
2991 rval = CCtsp_addbad_variables (lp, eg, &penalty, nadded,
2992 CCtsp_PRICE_RCTHRESH, CCtsp_PRICE_MAXPENALTY, 0,
2993 (int *) NULL, silent, rstate);
2994 if (rval) {
2995 fprintf (stderr, "CCtsp_addbad_variables failed\n"); return rval;
2996 }
2997
2998 rval = lp_value (lp, &val);
2999 if (rval) { fprintf (stderr, "lp_value failed\n"); return rval; }
3000
3001 if (!silent) {
3002 printf ("(SPARSE) %d edges added, penalty %f, val %f\n",
3003 *nadded, penalty, val);
3004 fflush (stdout);
3005 }
3006
3007 if (lp->full_edges_valid) {
3008 if (val + penalty > lp->lowerbound) {
3009 if (!silent) {
3010 printf ("New (node) lower bound: %f\n", val + penalty);
3011 fflush (stdout);
3012 }
3013 lp->lowerbound = val + penalty;
3014 }
3015 if (bnd) *bnd = val + penalty;
3016 }
3017 } else {
3018 *nadded = 0;
3019 }
3020 return 0;
3021 }
3022
CCtsp_bb_cutting(char * probname,int probnum,int prob_newnum,int ncount,CCdatagroup * dat,int * ptour,double * upbound,CCtsp_lpcuts * pool,CCtsp_cutselect * sel,double * val,int * prune,int * foundtour,int * besttour,int level,int silent,CCrandstate * rstate)3023 int CCtsp_bb_cutting (char *probname, int probnum, int prob_newnum, int ncount,
3024 CCdatagroup *dat, int *ptour, double *upbound, CCtsp_lpcuts *pool,
3025 CCtsp_cutselect *sel, double *val, int *prune, int *foundtour,
3026 int *besttour, int level, int silent, CCrandstate *rstate)
3027 {
3028 int rval = 0;
3029 CCtsp_lp *lp = (CCtsp_lp *) NULL;
3030 double cval, tourval;
3031 int test;
3032
3033 *val = 0.0;
3034 *prune = 0;
3035 *foundtour = 0;
3036
3037 rval = bb_cutting_work (&lp, probname, probnum, ncount, dat, ptour,
3038 *upbound, pool, sel, &cval, level, silent, rstate);
3039 if (rval) {
3040 fprintf (stderr, "bb_cutting_work failed\n"); fflush (stdout);
3041 goto CLEANUP;
3042 }
3043
3044 if (lp != (CCtsp_lp *) NULL) {
3045 lp->id = prob_newnum;
3046 }
3047
3048 if (cval == CCtsp_LP_MAXDOUBLE) {
3049 rval = CCtsp_verify_infeasible_lp (lp, &test, silent);
3050 if (rval) {
3051 fprintf (stderr, "CCtsp_verify_infeasible_lp failed\n");
3052 goto CLEANUP;
3053 }
3054 if (test) {
3055 printf ("verified infeasible LP\n"); fflush (stdout);
3056 *val = CCtsp_LP_MAXDOUBLE;
3057 *prune = 1;
3058 rval = CCtsp_write_probleaf_id (lp);
3059 if (rval) {
3060 fprintf (stderr, "CCtsp_write_probleaf_id failed\n");
3061 goto CLEANUP;
3062 }
3063 rval = 0;
3064 } else {
3065 fprintf (stderr, "did not verify an infeasible LP\n");
3066 rval = 1; goto CLEANUP;
3067 }
3068 } else {
3069 rval = CCtsp_pricing_loop (lp, val, silent, rstate);
3070 if (rval) {
3071 fprintf (stderr, "CCtsp_pricing_loop failed\n");
3072 rval = 1; goto CLEANUP;
3073 }
3074 lp->lowerbound = *val;
3075 if (lp->upperbound < *upbound) *upbound = lp->upperbound;
3076
3077 if (lp->lowerbound < lp->upperbound - 0.9) {
3078 CCutil_start_timer (&lp->stats.linkern);
3079 rval = CCtsp_call_x_heuristic (lp, &tourval, besttour, silent,
3080 rstate);
3081 if (rval) {
3082 fprintf (stderr, "CCtsp_call_x_heuristic failed\n");
3083 goto CLEANUP;
3084 }
3085 if (!silent) {
3086 CCutil_stop_timer (&lp->stats.linkern, 1);
3087 } else {
3088 CCutil_stop_timer (&lp->stats.linkern, 0);
3089 }
3090 if (tourval < lp->upperbound) {
3091 printf ("New upperbound from x-heuristic: %.2f\n", tourval);
3092 lp->upperbound = tourval;
3093 *upbound = tourval;
3094 *foundtour = 1;
3095 }
3096 }
3097
3098 if (lp->lowerbound >= lp->upperbound - 0.9) {
3099 rval = CCtsp_verify_lp_prune (lp, &test, silent);
3100 if (rval) {
3101 fprintf (stderr, "CCtsp_verify_lp_prune failed\n");
3102 goto CLEANUP;
3103 }
3104 if (test) {
3105 if (!silent) {
3106 printf ("verified that LP can be pruned\n");
3107 fflush (stdout);
3108 }
3109 *prune = 1;
3110 rval = CCtsp_write_probleaf_id (lp);
3111 if (rval) {
3112 fprintf (stderr, "CCtsp_write_probleaf_id failed\n");
3113 goto CLEANUP;
3114 }
3115 } else {
3116 printf ("exact pricing could not prune the search\n");
3117 fflush (stdout);
3118 rval = CCtsp_write_probfile_id (lp);
3119 CCcheck_rval (rval, "CCtsp_write_probfile_id failed");
3120 }
3121 } else {
3122 rval = CCtsp_write_probfile_id (lp);
3123 CCcheck_rval (rval, "CCtsp_write_probfile_id failed");
3124 }
3125 }
3126
3127 CLEANUP:
3128
3129 if (lp) CCtsp_free_tsp_lp_struct (&lp);
3130 return rval;
3131 }
3132
CCtsp_call_x_heuristic(CCtsp_lp * lp,double * val,int * outcyc,int silent,CCrandstate * rstate)3133 int CCtsp_call_x_heuristic (CCtsp_lp *lp, double *val, int *outcyc,
3134 int silent, CCrandstate *rstate)
3135 {
3136 int rval = 0;
3137 int *cyc = (int *) NULL;
3138 int *xlist = (int *) NULL;
3139 double *x = (double *) NULL;
3140 int ncount = lp->graph.ncount;
3141 int xcount, i;
3142
3143 *val = CCtsp_LP_MAXDOUBLE;
3144
3145 if (!lp->dat) goto CLEANUP;
3146
3147 cyc = CC_SAFE_MALLOC (ncount, int);
3148 if (!cyc) {
3149 fprintf (stderr, "out of memory for cycle\n");
3150 rval = 1; goto CLEANUP;
3151 }
3152 rval = CCtsp_get_lp_result (lp, (double *) NULL, (double *) NULL,
3153 &xcount, &xlist, &x, (double **) NULL, (double **) NULL,
3154 (double **) NULL);
3155 if (rval) {
3156 fprintf (stderr, "CCtsp_get_lp_result failed\n");
3157 goto CLEANUP;
3158 }
3159
3160 rval = CCtsp_x_greedy_tour_lk (lp->dat, ncount, xcount, xlist, x,
3161 cyc, val, silent, rstate);
3162 if (rval) {
3163 fprintf (stderr, "CCtsp_x_greedy_tour_lk failed\n"); goto CLEANUP;
3164 }
3165 if (!silent) {
3166 printf ("x-heuristic lk gives: %.2f\n", *val); fflush (stdout);
3167 }
3168 if (*val < lp->upperbound) {
3169 if (outcyc) {
3170 for (i = 0; i < ncount; i++) {
3171 outcyc[i] = cyc[i];
3172 }
3173 }
3174 }
3175
3176 CLEANUP:
3177
3178 CC_IFFREE (cyc, int);
3179 CC_IFFREE (xlist, int);
3180 CC_IFFREE (x, double);
3181 return rval;
3182 }
3183
bb_cutting_work(CCtsp_lp ** lp,char * probname,int probnum,int ncount,CCdatagroup * dat,int * ptour,double initial_ub,CCtsp_lpcuts * pool,CCtsp_cutselect * sel,double * val,int level,int silent,CCrandstate * rstate)3184 static int bb_cutting_work (CCtsp_lp **lp, char *probname, int probnum,
3185 int ncount, CCdatagroup *dat, int *ptour, double initial_ub,
3186 CCtsp_lpcuts *pool, CCtsp_cutselect *sel, double *val, int level,
3187 int silent, CCrandstate *rstate)
3188 {
3189 int rval = 0;
3190
3191 *lp = (CCtsp_lp *) NULL;
3192 *val = 0.0;
3193
3194 rval = CCtsp_bb_init_lp (lp, probname, probnum, ncount, dat, ptour,
3195 initial_ub, pool, silent, rstate);
3196 if (rval == 2) {
3197 printf ("LP is reported to be infeasible\n"); fflush (stdout);
3198 *val = CCtsp_LP_MAXDOUBLE;
3199 rval = 0; goto CLEANUP;
3200 } else if (rval) {
3201 fprintf (stderr, "CCtsp_bb_init_lp failed\n"); goto CLEANUP;
3202 }
3203 CCutil_start_timer (&(*lp)->stats.total);
3204
3205 if ((*lp)->lowerbound >= (*lp)->upperbound - 0.9) {
3206 printf ("Do not cut, the lp is within 1.0 of the upperbound\n");
3207 fflush (stdout);
3208 *val = (*lp)->lowerbound;
3209 goto CLEANUP;
3210 } else {
3211 rval = CCtsp_cutselect_set_tols (sel, *lp, level, silent);
3212 if (rval) {
3213 fprintf (stderr, "CCtsp_cutselect_set_tols failed\n");
3214 goto CLEANUP;
3215 }
3216
3217 rval = CCtsp_cutting_loop (*lp, sel, 0, silent, rstate);
3218 if (rval == 2) {
3219 printf ("Cut LP is reported to be infeasible\n"); fflush (stdout);
3220 *val = CCtsp_LP_MAXDOUBLE;
3221 rval = 0;
3222 } else if (rval) {
3223 fprintf (stderr, "CCtsp_cutting_loop failed\n"); goto CLEANUP;
3224 } else {
3225 *val = (*lp)->lowerbound;
3226 }
3227 }
3228
3229 CLEANUP:
3230
3231 if (!silent) {
3232 CCutil_stop_timer (&(*lp)->stats.total, 1);
3233 } else {
3234 CCutil_stop_timer (&(*lp)->stats.total, 0);
3235 }
3236 /* CCtsp_output_statistics (&(*lp)->stats); */
3237
3238 if (!silent) {
3239 printf ("Final LP has %d rows, %d columns, %d nonzeros\n",
3240 CClp_nrows ((*lp)->lp), CClp_ncols ((*lp)->lp),
3241 CClp_nnonzeros ((*lp)->lp));
3242 fflush (stdout);
3243 }
3244
3245 return rval;
3246 }
3247
grab_close_x(int ncount,int xcount,int * xlist,double * x,int * newcount,int ** newlist,double ** newx,double mult)3248 static int grab_close_x (int ncount, int xcount, int *xlist, double *x,
3249 int *newcount, int **newlist, double **newx, double mult)
3250 {
3251 int rval = 0;
3252 char *marks = (char *) NULL;
3253 int i, k, tmp, n1, n2;
3254
3255 CC_IFFREE (*newlist, int);
3256 CC_IFFREE (*newx, double);
3257
3258 *newx = CC_SAFE_MALLOC (xcount + ncount, double);
3259 *newlist = CC_SAFE_MALLOC (2 * (xcount + ncount), int);
3260 marks = CC_SAFE_MALLOC (ncount, char);
3261 if (!(*newx) || !(*newlist) || !marks) {
3262 fprintf (stderr, "out of memory in grab_close_x\n");
3263 CC_IFFREE (*newx, double);
3264 CC_IFFREE (*newlist, int);
3265 rval = 1; goto CLEANUP;
3266 }
3267 for (i = 0; i < ncount; i++) {
3268 marks[i] = 0;
3269 }
3270 k = 0;
3271 for (i = 0; i < xcount; i++) {
3272 n1 = xlist[2*i];
3273 n2 = xlist[2*i+1];
3274 if (n2 < n1) {
3275 tmp = n1; n1 = n2; n2 = tmp;
3276 }
3277 if (n1 == (n2 - 1)) {
3278 (*newx)[i] = mult * x[i] + (1.0 - mult);
3279 marks[n1] = 1;
3280 } else if (n1 == 0 && n2 == ncount - 1) {
3281 (*newx)[i] = mult * x[i] + (1.0 - mult);
3282 marks[n2] = 1;
3283 } else {
3284 (*newx)[i] = mult * x[i];
3285 }
3286 (*newlist)[k++] = n1;
3287 (*newlist)[k++] = n2;
3288 }
3289 *newcount = xcount;
3290 for (i = 0; i < ncount; i++) {
3291 if (marks[i] == 0) {
3292 (*newx)[(*newcount)++] = 1.0 - mult;
3293 (*newlist)[k++] = i;
3294 (*newlist)[k++] = (i + 1) % ncount;
3295 }
3296 }
3297
3298 CLEANUP:
3299
3300 CC_IFFREE (marks, char);
3301 return rval;
3302 }
3303
grab_polished_x(CCtsp_lp * lp,double dust_val,int * newcount,int ** newlist,double ** newx)3304 static int CC_UNUSED grab_polished_x (CCtsp_lp *lp, double dust_val,
3305 int *newcount, int **newlist, double **newx)
3306 {
3307 int rval = 0;
3308 CClp_warmstart *warmstart = (CClp_warmstart *) NULL;
3309 double *x = (double *) NULL;
3310 char *marks = (char *) NULL;
3311 int i;
3312 int nset;
3313 int ncols;
3314 double szeit;
3315 double objval;
3316 double origval;
3317
3318 CC_IFFREE (*newlist, int);
3319 CC_IFFREE (*newx, double);
3320
3321 ncols = CClp_ncols (lp->lp);
3322
3323 x = CC_SAFE_MALLOC (ncols, double);
3324 marks = CC_SAFE_MALLOC (ncols, char);
3325 if (x == (double *) NULL || marks == (char *) NULL) {
3326 fprintf (stderr, "Out of memory in grab_polished_x\n");
3327 rval = 1; goto CLEANUP;
3328 }
3329
3330 for (i=0; i<ncols; i++) {
3331 if (lp->graph.edges[i].fixed || lp->graph.edges[i].branch) {
3332 marks[i] = -1;
3333 } else {
3334 marks[i] = 0;
3335 }
3336 }
3337
3338 rval = CClp_get_warmstart (lp->lp, &warmstart);
3339 if (rval) {
3340 fprintf (stderr, "CClp_get_warmstart failed\n"); goto CLEANUP;
3341 }
3342
3343 rval = CClp_objval (lp->lp, &origval);
3344 if (rval) {
3345 fprintf (stderr, "CClp_objval failed\n"); goto CLEANUP;
3346 }
3347
3348 printf ("Polishing, objval %.6f\n", origval);
3349 fflush (stdout);
3350 do {
3351 szeit = CCutil_zeit();
3352
3353 rval = CClp_x (lp->lp, x);
3354 if (rval) {
3355 fprintf (stderr, "CClp_x failed\n"); goto CLEANUP;
3356 }
3357
3358 nset = 0;
3359 for (i=0; i<ncols; i++) {
3360 if (x[i] != 0.0 && x[i] < dust_val && marks[i] == 0) {
3361 marks[i] = 1;
3362 rval = CClp_setbnd (lp->lp, i, 'U', 0.0);
3363 if (rval) {
3364 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3365 }
3366 nset++;
3367 } else if (x[i] != 1.0 && x[i] > 1.0-dust_val && marks[i] == 0) {
3368 marks[i] = 2;
3369 rval = CClp_setbnd (lp->lp, i, 'L', 1.0);
3370 if (rval) {
3371 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3372 }
3373 nset++;
3374 }
3375 }
3376
3377 if (nset > 0) {
3378 rval = CClp_opt (lp->lp, CClp_METHOD_DUAL);
3379 if (rval == 2) {
3380 fprintf (stderr, "Polished LP infeasible\n"); goto CLEANUP;
3381 } else if (rval) {
3382 fprintf (stderr, "CClp_opt failed\n"); goto CLEANUP;
3383 }
3384 }
3385
3386 rval = CClp_objval (lp->lp, &objval);
3387 if (rval) {
3388 fprintf (stderr, "CClp_objval failed\n"); goto CLEANUP;
3389 }
3390 printf ("polished away %d dusty edges in %.2f seconds, objval %.6f\n",
3391 nset, CCutil_zeit() - szeit, objval);
3392 fflush (stdout);
3393 } while (nset > 0);
3394
3395 for (i=0; i<ncols; i++) {
3396 if (marks[i] == 1) {
3397 rval = CClp_setbnd (lp->lp, i, 'U', 1.0);
3398 if (rval) {
3399 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3400 }
3401 } else if (marks[i] == 2) {
3402 rval = CClp_setbnd (lp->lp, i, 'L', 0.0);
3403 if (rval) {
3404 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3405 }
3406 }
3407 }
3408
3409 rval = CClp_load_warmstart (lp->lp, warmstart);
3410 if (rval) {
3411 fprintf (stderr, "CClp_load_warmstart failed\n"); goto CLEANUP;
3412 }
3413
3414 rval = CClp_opt (lp->lp, CClp_METHOD_DUAL);
3415 if (rval == 2) {
3416 fprintf (stderr, "restored LP infeasible\n"); goto CLEANUP;
3417 } else if (rval) {
3418 fprintf (stderr, "CClp_opt failed\n"); goto CLEANUP;
3419 }
3420
3421 *newx = x;
3422 x = (double *) NULL;
3423
3424 *newlist = CC_SAFE_MALLOC (2 * ncols, int);
3425 if ((*newlist) == (int *) NULL) {
3426 fprintf (stderr, "out of memory in grab_polished_x\n");
3427 rval = 1; goto CLEANUP;
3428 }
3429 for (i = 0; i < ncols; i++) {
3430 (*newlist)[2*i] = lp->graph.edges[i].ends[0];
3431 (*newlist)[2*i+1] = lp->graph.edges[i].ends[1];
3432 }
3433
3434 *newcount = ncols;
3435 rval = 0;
3436
3437 CLEANUP:
3438 CClp_free_warmstart (&warmstart);
3439
3440 CC_IFFREE (x, double);
3441 CC_IFFREE (marks, char);
3442
3443 if (rval) {
3444 CC_IFFREE (*newlist, int);
3445 CC_IFFREE (*newx, double);
3446 }
3447 return rval;
3448 }
3449
grab_polished2_x(CCtsp_lp * lp,double dust_val,int * newcount,int ** newlist,double ** newx)3450 static int CC_UNUSED grab_polished2_x (CCtsp_lp *lp, double dust_val,
3451 int *newcount, int **newlist, double **newx)
3452 {
3453 int rval = 0;
3454 CClp_warmstart *warmstart = (CClp_warmstart *) NULL;
3455 double *x = (double *) NULL;
3456 char *marks = (char *) NULL;
3457 int i;
3458 int ncols;
3459 double szeit;
3460 double objval;
3461 double origval;
3462 double setval;
3463 int ninfeas = 0;
3464 int nfixed = 0;
3465
3466 CC_IFFREE (*newlist, int);
3467 CC_IFFREE (*newx, double);
3468
3469 ncols = CClp_ncols (lp->lp);
3470
3471 x = CC_SAFE_MALLOC (ncols, double);
3472 marks = CC_SAFE_MALLOC (ncols, char);
3473 if (x == (double *) NULL || marks == (char *) NULL) {
3474 fprintf (stderr, "Out of memory in grab_polished_x\n");
3475 rval = 1; goto CLEANUP;
3476 }
3477
3478 rval = CClp_get_warmstart (lp->lp, &warmstart);
3479 if (rval) {
3480 fprintf (stderr, "CClp_get_warmstart failed\n"); goto CLEANUP;
3481 }
3482
3483 rval = CClp_objval (lp->lp, &origval);
3484 if (rval) {
3485 fprintf (stderr, "CClp_objval failed\n"); goto CLEANUP;
3486 }
3487
3488 printf ("Polishing, objval %.6f\n", origval);
3489 fflush (stdout);
3490
3491 rval = CClp_x (lp->lp, x);
3492 if (rval) {
3493 fprintf (stderr, "CClp_x failed\n"); goto CLEANUP;
3494 }
3495
3496 for (i=0; i<ncols; i++) {
3497 if (lp->graph.edges[i].fixed || lp->graph.edges[i].branch) {
3498 marks[i] = -1;
3499 } else {
3500 if (x[i] - dust_val > 0.0) {
3501 rval = CClp_setbnd (lp->lp, i, 'L', x[i] - dust_val);
3502 if (rval) {
3503 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3504 }
3505 }
3506 if (x[i] + dust_val < 1.0) {
3507 rval = CClp_setbnd (lp->lp, i, 'U', x[i] + dust_val);
3508 if (rval) {
3509 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3510 }
3511 }
3512 }
3513 }
3514
3515 szeit = CCutil_zeit();
3516 for (i=0; i<ncols; i++) {
3517 if (marks[i] == 0 && (x[i] < dust_val || x[i] > 1.0 - dust_val)) {
3518 printf ("edge %d oldval %.6f", i, x[i]); fflush (stdout);
3519 if (x[i] < dust_val) setval = 0.0;
3520 else setval = 1.0;
3521 rval = CClp_setbnd (lp->lp, i, 'L', setval);
3522 if (rval) {
3523 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3524 }
3525 rval = CClp_setbnd (lp->lp, i, 'U', setval);
3526 if (rval) {
3527 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3528 }
3529 rval = CClp_opt (lp->lp, CClp_METHOD_DUAL);
3530 if (rval != 0 && rval != 2) {
3531 fprintf (stderr, "CClp_opt failed\n"); goto CLEANUP;
3532 } else if (rval == 2) {
3533 rval = CClp_setbnd (lp->lp, i, 'L', 0.0);
3534 if (rval) {
3535 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3536 }
3537 rval = CClp_setbnd (lp->lp, i, 'U', 1.0);
3538 if (rval) {
3539 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3540 }
3541 ninfeas++;
3542 } else {
3543 nfixed++;
3544 }
3545 rval = CClp_objval (lp->lp, &objval);
3546 if (rval) {
3547 fprintf (stderr, "CClp_objval failed\n"); goto CLEANUP;
3548 }
3549 printf (" dusted, cum time %.2f, objval %.6f\n",
3550 CCutil_zeit() - szeit, objval);
3551 fflush (stdout);
3552 }
3553 }
3554
3555 rval = CClp_opt (lp->lp, CClp_METHOD_DUAL);
3556 if (rval) {
3557 fprintf (stderr, "CClp_opt failed\n"); goto CLEANUP;
3558 }
3559 rval = CClp_objval (lp->lp, &objval);
3560 if (rval) {
3561 fprintf (stderr, "CClp_objval failed\n"); goto CLEANUP;
3562 }
3563 printf ("polished away %d dusty edges (%d stubborn) in %.2f seconds, objval %.6f\n",
3564 nfixed, ninfeas, CCutil_zeit() - szeit, objval);
3565 fflush (stdout);
3566
3567 rval = CClp_x (lp->lp, x);
3568 if (rval) {
3569 fprintf (stderr, "CClp_x failed\n"); goto CLEANUP;
3570 }
3571
3572 for (i=0; i<ncols; i++) {
3573 if (marks[i] == 0) {
3574 rval = CClp_setbnd (lp->lp, i, 'L', 0.0);
3575 if (rval) {
3576 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3577 }
3578 rval = CClp_setbnd (lp->lp, i, 'U', 1.0);
3579 if (rval) {
3580 fprintf (stderr, "CClp_setbnd failed\n"); goto CLEANUP;
3581 }
3582 }
3583 }
3584
3585 rval = CClp_load_warmstart (lp->lp, warmstart);
3586 if (rval) {
3587 fprintf (stderr, "CClp_load_warmstart failed\n"); goto CLEANUP;
3588 }
3589
3590 rval = CClp_opt (lp->lp, CClp_METHOD_DUAL);
3591 if (rval == 2) {
3592 fprintf (stderr, "restored LP infeasible\n"); goto CLEANUP;
3593 } else if (rval) {
3594 fprintf (stderr, "CClp_opt failed\n"); goto CLEANUP;
3595 }
3596
3597 *newx = x;
3598 x = (double *) NULL;
3599
3600 *newlist = CC_SAFE_MALLOC (2 * ncols, int);
3601 if ((*newlist) == (int *) NULL) {
3602 fprintf (stderr, "out of memory in grab_polished_x\n");
3603 rval = 1; goto CLEANUP;
3604 }
3605 for (i = 0; i < ncols; i++) {
3606 (*newlist)[2*i] = lp->graph.edges[i].ends[0];
3607 (*newlist)[2*i+1] = lp->graph.edges[i].ends[1];
3608 }
3609
3610 *newcount = ncols;
3611 rval = 0;
3612
3613 CLEANUP:
3614 CClp_free_warmstart (&warmstart);
3615
3616 CC_IFFREE (x, double);
3617 CC_IFFREE (marks, char);
3618
3619 if (rval) {
3620 CC_IFFREE (*newlist, int);
3621 CC_IFFREE (*newx, double);
3622 }
3623 return rval;
3624 }
3625
no_tighten(int ncount,int xcount,int * xlist,double * x,int * test,double tol)3626 static int no_tighten (int ncount, int xcount, int *xlist, double *x, int *test,
3627 double tol)
3628 {
3629 CC_SRKgraph G;
3630 int rval;
3631 int k;
3632
3633 *test = 0;
3634 CCcut_SRK_init_graph (&G);
3635
3636 rval = CCcut_SRK_buildgraph (&G, ncount, xcount, xlist, x);
3637 if (rval) {
3638 fprintf (stderr, "CCcut_SRK_buildgraph failed\n");
3639 goto CLEANUP;
3640 }
3641 CCcut_SRK_increment_marker (&G);
3642
3643 rval = CCcut_SRK_defluff (&G);
3644 if (rval) {
3645 fprintf (stderr, "CCcut_SRK_defluff failed\n");
3646 goto CLEANUP;
3647 }
3648
3649 CCcut_SRK_identify_paths_to_edges (&G, &k, 0);
3650
3651 if (k < (tol * ncount)) {
3652 *test = 1;
3653 }
3654
3655
3656 CLEANUP:
3657
3658 CCcut_SRK_free_graph (&G);
3659 return rval;
3660 }
3661
3662