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 /* ROUTINES TO PRICE EDGES USING BIGGUY ARITHMETIC */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: January 21, 1997 */
25 /* */
26 /* */
27 /* EXPORTED FUNCTIONS: */
28 /* */
29 /* int CCtsp_exact_price (CCtsp_lp *lp, CCbigguy *bound, */
30 /* int complete_price, int phase1, int silent) */
31 /* RETURNS a bound that is valid for the entire edge set; the values */
32 /* of the dual variables will be stored in lp->exact_dual unless */
33 /* the existing lp->exact_dual's cutcount agrees with the */
34 /* cutcount for lp */
35 /* -lp is a pointer to the tsp lp */
36 /* -bound returns the LP bound */
37 /* -if complete_price is nonzero, then price over the complete */
38 /* graph, even if a valid full edge set is present */
39 /* -phase1 is either 0 or 1, with 1 indicating that the pricing */
40 /* should be to determine a Farkas' lemma bound to prove that the */
41 /* LP is infeasbile */
42 /* */
43 /* int CCtsp_edge_elimination (CCtsp_lp *lp, int eliminate_sparse, */
44 /* int silent) */
45 /* USES the bound information to elimination edges and set edges to 1; */
46 /* the remaining edges are placed into lp->fulladj (the old adj */
47 /* is freed) and the fixed edges are placed on the list */
48 /* lp->fixededges; the dual values are taken from lp->exact_dual */
49 /* -lp is a pointer to the tsp lp; lp->exact_lowerbound will be used */
50 /* together with lp->upperbound to determine the cutoff to elim */
51 /* and fix edges */
52 /* -if eliminate_sparse is nonzero and lp->full_edges_valid, then */
53 /* the elimination is based on the lp->fulladj list. Otherwise */
54 /* the elimination is based on the lp->dat. */
55 /* NOTES: this function does not alter the LP or lp->graph */
56 /* */
57 /* int CCtsp_exact_dual (CCtsp_lp *lp) */
58 /* RETURNS the dual values as bigguys (used to store the info used */
59 /* to establish the exact lower bound); the values will be */
60 /* stored in lp->exact_dual (and the existing values freed) */
61 /* -lp is the CCtsp_lp */
62 /* */
63 /* int CCtsp_verify_infeasible_lp (CCtsp_lp *lp, int *yesno, int silent) */
64 /* VERIFIES that the lp is infeasible using exact pricing. */
65 /* -yesno is set to 1 if the lp is infeasible and 0 otherwise. */
66 /* */
67 /* int CCtsp_verify_lp_prune (CCtsp_lp *lp, int *yesno, int silent) */
68 /* VERIFIES that the lp bound is less than the lp upperbound - 1. */
69 /* -yesno is set to 1 if bound < upperbound - 1 and 0 otherwise. */
70 /* */
71 /****************************************************************************/
72
73 #include "machdefs.h"
74 #include "util.h"
75 #include "macrorus.h"
76 #include "bigguy.h"
77 #include "tsp.h"
78
79 #define BIG_PRICE_GEN 20000
80
81 typedef struct bigpredge {
82 int ends[2];
83 int len;
84 CCbigguy rc;
85 } bigpredge;
86
87
88 static int
89 big_pricing_duals (CCtsp_lp *lp, CCbigguy *node_pi, CCbigguy *node_piest,
90 CCbigguy *node_domino, CCbigguy *cut_pi, CCbigguy *clique_pi,
91 CCbigguy *rhs_sum),
92 big_price_list (CCtsp_lp *lp, int ecount, bigpredge *elist,
93 CCbigguy *node_pi, CCbigguy *clique_pi, CCbigguy *cut_pi),
94 big_generate_edges (CCtsp_lp *lp, int use_full_edges, CCbigguy *node_piest,
95 CCbigguy *node_domino, int nwant, int *gencount, bigpredge *genlist,
96 int *n1, int *n2, int *finished, CCbigguy cutoff, int phase1),
97 add_to_inlist (CCtsp_lp *lp, int use_full_edges, bigpredge *inlist,
98 int *count, int end0, int end1, int phase1),
99 add_to_adj (CCtsp_lp *lp, CCtsp_genadj *adj, int end0, int end1,
100 int *count),
101 test_edge (int end1, int end2, int len, CCbigguy *node_pi,
102 CCbigguy *node_domino, CCbigguy cutoff);
103
104
CCtsp_exact_price(CCtsp_lp * lp,CCbigguy * bound,int complete_price,int phase1,int silent)105 int CCtsp_exact_price (CCtsp_lp *lp, CCbigguy *bound, int complete_price,
106 int phase1, int silent)
107 {
108 int incount;
109 bigpredge *inlist = (bigpredge *) NULL;
110 CCbigguy penalty, rhs_sum;
111 CCbigguy *node_pi = (CCbigguy *) NULL;
112 CCbigguy *node_piest = (CCbigguy *) NULL;
113 CCbigguy *node_domino = (CCbigguy *) NULL;
114 CCbigguy *clique_pi = (CCbigguy *) NULL;
115 CCbigguy *cut_pi = (CCbigguy *) NULL;
116 int nbranch = 0;
117 int n1, n2, i, j, finished;
118 int rval = 0;
119 double szeit;
120 int use_full_edges;
121
122 szeit = CCutil_zeit ();
123 *bound = CCbigguy_ZERO;
124
125 if (!lp->dat && !lp->full_edges_valid) {
126 fprintf (stderr, "must have dat file or full edge set\n");
127 return 1;
128 }
129
130 if (!lp->dat && complete_price) {
131 fprintf (stderr, "must have dat file for complete price\n");
132 return 1;
133 }
134
135 if (phase1) {
136 printf ("phase 1 pricing\n");
137 fflush (stdout);
138 }
139
140 use_full_edges = lp->full_edges_valid;
141
142 if (complete_price) {
143 printf ("Pricing COMPLETE GRAPH\n");
144 fflush (stdout);
145 use_full_edges = 0;
146 }
147
148 if (!lp->exact_dual || lp->exact_dual->cutcount != lp->cuts.cutcount) {
149 fflush (stdout);
150 rval = CCtsp_exact_dual (lp);
151 if (rval) {
152 fprintf (stderr, "CCtsp_exact_dual failed\n");
153 goto CLEANUP;
154 }
155 }
156
157 for (i = 0; i < lp->branchdepth; i++) {
158 if (lp->branchhistory[i].ends[0] != -1) {
159 nbranch++;
160 }
161 }
162
163 incount = 0;
164 if (BIG_PRICE_GEN >= lp->nfixededges + nbranch) {
165 inlist = CC_SAFE_MALLOC (BIG_PRICE_GEN, bigpredge);
166 } else {
167 inlist = CC_SAFE_MALLOC (lp->nfixededges + nbranch, bigpredge);
168 }
169 CCcheck_NULL (inlist, "out of memory in CCtsp_exact_price");
170
171 node_pi = CC_SAFE_MALLOC (lp->graph.ncount, CCbigguy);
172 CCcheck_NULL (node_pi, "out of memory in CCtsp_exact_price");
173 node_piest = CC_SAFE_MALLOC (lp->graph.ncount, CCbigguy);
174 CCcheck_NULL (node_piest, "out of memory in CCtsp_exact_price");
175
176 if (lp->cuts.dominoend) {
177 node_domino = CC_SAFE_MALLOC (lp->graph.ncount, CCbigguy);
178 CCcheck_NULL (node_domino, "out of memory in CCtsp_exact_price");
179 }
180
181 if (lp->cuts.cliqueend) {
182 clique_pi = CC_SAFE_MALLOC (lp->cuts.cliqueend, CCbigguy);
183 CCcheck_NULL (clique_pi, "out of memory in CCtsp_exact_price");
184 }
185 if (lp->cuts.cutcount) {
186 cut_pi = CC_SAFE_MALLOC (lp->cuts.cutcount, CCbigguy);
187 CCcheck_NULL (cut_pi, "out of memory in CCtsp_exact_price");
188 }
189
190 rval = big_pricing_duals (lp, node_pi, node_piest, node_domino, cut_pi,
191 clique_pi, &rhs_sum);
192 CCcheck_rval (rval, "big_pricing_duals failed");
193
194 finished = 0;
195 n1 = 0;
196 n2 = (use_full_edges ? 0 : 1);
197 penalty = CCbigguy_ZERO;
198
199 while (!finished) {
200 rval = big_generate_edges (lp, use_full_edges, node_piest,
201 node_domino, BIG_PRICE_GEN, &incount, inlist, &n1, &n2,
202 &finished, CCbigguy_ZERO, phase1);
203 CCcheck_rval (rval, "big_generate_edges failed");
204
205 rval = big_price_list (lp, incount, inlist, node_pi, clique_pi, cut_pi);
206 CCcheck_rval (rval, "big_price_list failed");
207
208 for (i = 0; i < incount; i++) {
209 if (CCbigguy_cmp (inlist[i].rc, CCbigguy_ZERO) < 0) {
210 CCbigguy_add (&penalty, inlist[i].rc);
211 #if 0
212 {
213 int q;
214 q = CCtsp_find_edge (&lp->graph, inlist[i].ends[0],
215 inlist[i].ends[1]);
216 if (q == -1) {
217 printf ("YIPES: %f [%d, %d %d]: %f %f\n",
218 CCbigguy_bigguytod (inlist[i].rc), inlist[i].ends[0],
219 inlist[i].ends[1], inlist[i].len,
220 CCbigguy_bigguytod (node_pi[inlist[i].ends[0]]),
221 CCbigguy_bigguytod (node_pi[inlist[i].ends[1]]));
222 fflush (stdout);
223 }
224 }
225 #endif
226 }
227 }
228 }
229
230 if (lp->nfixededges + nbranch) {
231 int end0, end1;
232
233 /* Adjust bound for fixed/branch edges */
234 /* If a fixed or a branch=1 edge has positive rc, it can be added */
235 /* If a branch=0 edge has negative rc, it should be subtracted */
236 /* from the penalty since it was earlier added. */
237
238 incount = 0;
239 for (i = 0; i < lp->nfixededges; i++) {
240 end0 = lp->fixededges[2*i];
241 end1 = lp->fixededges[2*i+1];
242 rval = add_to_inlist (lp, use_full_edges, inlist, &incount,
243 end0, end1, phase1);
244 if (rval) {
245 fprintf (stderr, "add_to_inlist failed\n");
246 goto CLEANUP;
247 }
248 }
249 for (i = 0; i < lp->branchdepth; i++) {
250 if (lp->branchhistory[i].ends[0] != -1) {
251 end0 = lp->branchhistory[i].ends[0];
252 end1 = lp->branchhistory[i].ends[1];
253 rval = add_to_inlist (lp, use_full_edges, inlist, &incount,
254 end0, end1, phase1);
255 if (rval) {
256 fprintf (stderr, "add_to_inlist failed\n");
257 goto CLEANUP;
258 }
259 }
260 }
261
262 rval = big_price_list (lp, incount, inlist, node_pi, clique_pi, cut_pi);
263 CCcheck_rval (rval, "big_price_list failed");
264
265 for (i = 0; i < lp->nfixededges; i++) {
266 if (CCbigguy_cmp (inlist[i].rc, CCbigguy_ZERO) > 0) {
267 CCbigguy_add (&penalty, inlist[i].rc);
268 }
269 }
270 for (i = lp->nfixededges, j = 0; i < lp->nfixededges+nbranch; i++) {
271 while (lp->branchhistory[j].ends[0] == -1)
272 j++;
273 if (lp->branchhistory[j].rhs == 0) {
274 if (CCbigguy_cmp (inlist[i].rc, CCbigguy_ZERO) < 0) {
275 CCbigguy_sub (&penalty, inlist[i].rc);
276 }
277 } else {
278 if (CCbigguy_cmp (inlist[i].rc, CCbigguy_ZERO) > 0) {
279
280 CCbigguy_add (&penalty, inlist[i].rc);
281 }
282 }
283 j++;
284 }
285 }
286
287 *bound = rhs_sum;
288 CCbigguy_add (bound, penalty);
289
290 if (!silent) {
291 printf ("Exact Price Time: %.2f seconds\n", CCutil_zeit () - szeit);
292 fflush (stdout);
293 }
294 rval = 0;
295
296 CLEANUP:
297
298 CC_IFFREE (cut_pi, CCbigguy);
299 CC_IFFREE (clique_pi, CCbigguy);
300 CC_IFFREE (node_pi, CCbigguy);
301 CC_IFFREE (node_piest, CCbigguy);
302 CC_IFFREE (node_domino, CCbigguy);
303 CC_IFFREE (inlist, bigpredge);
304 return rval;
305 }
306
add_to_inlist(CCtsp_lp * lp,int use_full_edges,bigpredge * inlist,int * count,int end0,int end1,int phase1)307 static int add_to_inlist (CCtsp_lp *lp, int use_full_edges, bigpredge *inlist,
308 int *count, int end0, int end1, int phase1)
309 {
310 int rval = 0;
311 int j;
312 int len = 0;
313 CCtsp_genadj *adj = lp->fulladj;
314
315 if (end0 > end1) {
316 CC_SWAP (end0, end1, j);
317 }
318 if (phase1) {
319 len = 0;
320 } else {
321 if (use_full_edges) {
322 for (j = 0; j < adj[end0].deg; j++) {
323 if (adj[end0].list[j].end == end1) {
324 len = adj[end0].list[j].len;
325 break;
326 }
327 }
328 if (j == adj[end0].deg) {
329 fprintf (stderr, "ERROR: fixed edge not in fulladj\n");
330 rval = 1; goto CLEANUP;
331 }
332 } else {
333 len = CCutil_dat_edgelen (end0, end1, lp->dat);
334 }
335 }
336 inlist[*count].ends[0] = end0;
337 inlist[*count].ends[1] = end1;
338 inlist[*count].len = len;
339 (*count)++;
340
341 CLEANUP:
342
343 return rval;
344 }
345
CCtsp_edge_elimination(CCtsp_lp * lp,int eliminate_sparse,int silent)346 int CCtsp_edge_elimination (CCtsp_lp *lp, int eliminate_sparse, int silent)
347 {
348 int incount;
349 bigpredge *inlist = (bigpredge *) NULL;
350 CCbigguy rhs_sum;
351 CCbigguy *node_pi = (CCbigguy *) NULL;
352 CCbigguy *node_piest = (CCbigguy *) NULL;
353 CCbigguy *node_domino = (CCbigguy *) NULL;
354 CCbigguy *clique_pi = (CCbigguy *) NULL;
355 CCbigguy *cut_pi = (CCbigguy *) NULL;
356 CCtsp_genadj *adj = (CCtsp_genadj *) NULL;
357 CCtsp_genadjobj *adjspace = (CCtsp_genadjobj *) NULL;
358 CCtsp_genadjobj *pa;
359 int i, n1, n2, finished, nremain, nfixed, ek;
360 int nbranch = 0;
361 int end0, end1;
362 int oldnfixed = lp->nfixededges;
363 int rval = 0;
364 CCbigguy cutoff, negcutoff;
365 double szeit;
366
367 /* This code has not been tested after branching (at present, we only */
368 /* call edge_elimination at the root LP). */
369
370 if (CCbigguy_cmp (lp->exact_lowerbound, CCbigguy_MINBIGGUY) == 0) {
371 fprintf (stderr, "need an exact lowerbound to run elimination\n");
372 return 1;
373 }
374 if (lp->upperbound == CCtsp_LP_MAXDOUBLE) {
375 fprintf (stderr, "need an exact upperbound to run elimination\n");
376 return 1;
377 }
378 if (!lp->exact_dual || lp->exact_dual->cutcount != lp->cuts.cutcount) {
379 fprintf (stderr, "no exact_dual in CCtsp_edge_elimination\n");
380 return 1;
381 }
382
383 szeit = CCutil_zeit ();
384
385 cutoff = CCbigguy_dtobigguy (lp->upperbound);
386 CCbigguy_sub (&cutoff, lp->exact_lowerbound);
387 CCbigguy_sub (&cutoff, CCbigguy_ONE);
388 negcutoff = CCbigguy_ZERO;
389 CCbigguy_sub (&negcutoff, cutoff);
390 if (!silent) {
391 printf ("Edge Elimination Cutoff: %f\n", CCbigguy_bigguytod (cutoff));
392 fflush (stdout);
393 }
394 if (CCbigguy_cmp (cutoff, CCbigguy_ZERO) < 0) {
395 printf ("Cutoff is less than ZERO, do not eliminate\n");
396 fflush (stdout);
397 return 1;
398 }
399
400 incount = 0;
401 inlist = CC_SAFE_MALLOC (BIG_PRICE_GEN, bigpredge);
402 CCcheck_NULL (inlist, "out of memory in CCtsp_edge_elimination");
403
404 node_pi = CC_SAFE_MALLOC (lp->graph.ncount, CCbigguy);
405 CCcheck_NULL (node_pi, "out of memory in CCtsp_edge_elimination");
406 node_piest = CC_SAFE_MALLOC (lp->graph.ncount, CCbigguy);
407 CCcheck_NULL (node_piest, "out of memory in CCtsp_edge_elimination");
408
409 if (lp->cuts.dominoend) {
410 node_domino = CC_SAFE_MALLOC (lp->graph.ncount, CCbigguy);
411 CCcheck_NULL (node_domino, "out of memory in CCtsp_edge_elimination");
412 }
413
414 if (lp->cuts.cliqueend) {
415 clique_pi = CC_SAFE_MALLOC (lp->cuts.cliqueend, CCbigguy);
416 CCcheck_NULL (clique_pi, "out of memory in CCtsp_edge_elimination");
417 }
418 if (lp->cuts.cutcount) {
419 cut_pi = CC_SAFE_MALLOC (lp->cuts.cutcount, CCbigguy);
420 CCcheck_NULL (cut_pi, "out of memory in CCtsp_edge_elimination");
421 }
422
423 rval = big_pricing_duals (lp, node_pi, node_piest, node_domino, cut_pi,
424 clique_pi, &rhs_sum);
425 CCcheck_rval (rval, "big_pricing_duals failed");
426
427 adj = CC_SAFE_MALLOC (lp->graph.ncount, CCtsp_genadj);
428 CCcheck_NULL (adj, "out of memory in CCtsp_edge_elimination");
429
430 for (i = 0; i < lp->graph.ncount; i++) {
431 adj[i].deg = 0;
432 }
433
434 if (eliminate_sparse == 0) lp->full_edges_valid = 0;
435 finished = 0;
436 nremain = 0;
437 nfixed = 0;
438 n1 = 0;
439 n2 = (lp->full_edges_valid ? 0 : 1);
440
441 while (!finished) {
442 rval = big_generate_edges (lp, lp->full_edges_valid, node_piest,
443 node_domino, BIG_PRICE_GEN, &incount, inlist, &n1, &n2,
444 &finished, cutoff, 0);
445 if (rval) {
446 fprintf (stderr, "big_generate_edges failed\n");
447 CC_FREE (adj, CCtsp_genadj);
448 goto CLEANUP;
449 }
450 rval = big_price_list (lp, incount, inlist, node_pi, clique_pi, cut_pi);
451 if (rval) {
452 fprintf (stderr, "big_price_list failed\n");
453 CC_FREE (adj, CCtsp_genadj);
454 goto CLEANUP;
455 }
456
457 for (i = 0; i < incount; i++) {
458 if (CCbigguy_cmp (inlist[i].rc, cutoff) <= 0) {
459 adj[inlist[i].ends[0]].deg++;
460 nremain++;
461 if (CCbigguy_cmp (inlist[i].rc, negcutoff) < 0) {
462 ek = CCtsp_find_edge (&(lp->graph),inlist[i].ends[0],
463 inlist[i].ends[1]);
464 if (ek != -1 && (lp->graph.edges[ek].fixed == 0 &&
465 lp->graph.edges[ek].branch == 0)) {
466 /* Bico 9.12.99
467 if (ek == -1 || (lp->graph.edges[ek].fixed == 0 &&
468 lp->graph.edges[ek].branch == 0)) {
469 */
470 /*
471 printf ("[%d, %d] ", inlist[i].ends[0],
472 inlist[i].ends[1]);
473 fflush (stdout);
474 */
475 nfixed++;
476 }
477 }
478 }
479 }
480 }
481
482 /* leave enough room for the old fixed edges and the branch edges */
483
484 for (i = 0; i < lp->branchdepth; i++) {
485 if (lp->branchhistory[i].ends[0] != -1) {
486 end0 = lp->branchhistory[i].ends[0];
487 end1 = lp->branchhistory[i].ends[1];
488 if (end0 < end1)
489 adj[end0].deg++;
490 else
491 adj[end1].deg++;
492 nbranch++;
493 }
494 }
495 for (i = 0; i < lp->nfixededges; i++) {
496 end0 = lp->fixededges[2*i];
497 end1 = lp->fixededges[2*i+1];
498 if (end0 < end1)
499 adj[end0].deg++;
500 else
501 adj[end1].deg++;
502 }
503
504 if (nremain + lp->nfixededges + nbranch) {
505 adjspace = CC_SAFE_MALLOC (nremain + lp->nfixededges + nbranch,
506 CCtsp_genadjobj);
507 if (!adjspace) {
508 fprintf (stderr, "out of memory in CCtsp_edge_elimination\n");
509 CC_FREE (adj, CCtsp_genadj);
510 rval = 1;
511 goto CLEANUP;
512 }
513 }
514 if (nfixed) {
515 rval = CCutil_reallocrus_count ((void **) &(lp->fixededges),
516 2 * (lp->nfixededges + nfixed), sizeof (int));
517 if (rval) {
518 fprintf (stderr, "out of memory in CCtsp_edge_elimination\n");
519 CC_FREE (adj, CCtsp_genadj);
520 CC_IFFREE (adjspace, CCtsp_genadjobj);
521 goto CLEANUP;
522 }
523 }
524
525 pa = adjspace;
526 for (i = 0; i < lp->graph.ncount; i++) {
527 adj[i].list = pa;
528 pa += adj[i].deg;
529 adj[i].deg = 0;
530 }
531
532 finished = 0;
533 n1 = 0;
534 n2 = (lp->full_edges_valid ? 0 : 1);
535
536 while (!finished) {
537 rval = big_generate_edges (lp, lp->full_edges_valid, node_piest,
538 node_domino, BIG_PRICE_GEN, &incount, inlist, &n1, &n2,
539 &finished, cutoff, 0);
540 if (rval) {
541 fprintf (stderr, "big_generate_edges failed\n");
542 CC_FREE (adj, CCtsp_genadj);
543 CC_IFFREE (adjspace, CCtsp_genadjobj);
544 goto CLEANUP;
545 }
546 rval = big_price_list (lp, incount, inlist, node_pi, clique_pi, cut_pi);
547 if (rval) {
548 fprintf (stderr, "big_price_list failed\n");
549 CC_FREE (adj, CCtsp_genadj);
550 CC_IFFREE (adjspace, CCtsp_genadjobj);
551 goto CLEANUP;
552 }
553 for (i = 0; i < incount; i++) {
554 if (CCbigguy_cmp (inlist[i].rc, cutoff) <= 0) {
555 adj[inlist[i].ends[0]].list[adj[inlist[i].ends[0]].deg].end =
556 inlist[i].ends[1];
557 adj[inlist[i].ends[0]].list[adj[inlist[i].ends[0]].deg].len =
558 inlist[i].len;
559 adj[inlist[i].ends[0]].deg++;
560 if (CCbigguy_cmp (inlist[i].rc, negcutoff) < 0) {
561 ek = CCtsp_find_edge (&(lp->graph),inlist[i].ends[0],
562 inlist[i].ends[1]);
563 if (ek != -1 && (lp->graph.edges[ek].fixed == 0 &&
564 lp->graph.edges[ek].branch == 0)) {
565 /* Bico 9.12.99
566 if (ek == -1 || (lp->graph.edges[ek].fixed == 0 &&
567 lp->graph.edges[ek].branch == 0)) {
568 */
569 lp->fixededges[2*lp->nfixededges] = inlist[i].ends[0];
570 lp->fixededges[2*lp->nfixededges+1] =
571 inlist[i].ends[1];
572 lp->nfixededges++;
573 }
574 }
575 }
576 }
577 }
578
579 /* some of the old fixed and branched edges may not have gotten into adj */
580
581 for (i = 0; i < lp->branchdepth; i++) {
582 if (lp->branchhistory[i].ends[0] != -1) {
583 end0 = lp->branchhistory[i].ends[0];
584 end1 = lp->branchhistory[i].ends[1];
585 rval = add_to_adj (lp, adj, end0, end1, &nremain);
586 if (rval) {
587 fprintf (stderr, "add_to_adj failed\n"); goto CLEANUP;
588 }
589 }
590 }
591 for (i = 0; i < oldnfixed; i++) {
592 end0 = lp->fixededges[2*i];
593 end1 = lp->fixededges[2*i+1];
594 rval = add_to_adj (lp, adj, end0, end1, &nremain);
595 if (rval) {
596 fprintf (stderr, "add_to_adj failed\n"); goto CLEANUP;
597 }
598 }
599 rval = 0;
600
601 CC_IFFREE (lp->fulladjspace, CCtsp_genadjobj);
602 CC_IFFREE (lp->fulladj, CCtsp_genadj);
603 lp->fullcount = nremain;
604 lp->fulladjspace = adjspace;
605 lp->fulladj = adj;
606 lp->full_edges_valid = 1;
607
608 if (!silent) {
609 printf ("Remaining Edges: %d (with %d new fixed)\n", nremain, nfixed);
610 printf ("Edge Elimination Time: %.2f seconds\n",
611 CCutil_zeit () - szeit);
612 fflush (stdout);
613 }
614
615 CLEANUP:
616
617 CC_IFFREE (cut_pi, CCbigguy);
618 CC_IFFREE (clique_pi, CCbigguy);
619 CC_IFFREE (node_pi, CCbigguy);
620 CC_IFFREE (node_piest, CCbigguy);
621 CC_IFFREE (node_domino, CCbigguy);
622 CC_IFFREE (inlist, bigpredge);
623 return rval;
624 }
625
add_to_adj(CCtsp_lp * lp,CCtsp_genadj * adj,int end0,int end1,int * count)626 static int add_to_adj (CCtsp_lp *lp, CCtsp_genadj *adj, int end0, int end1,
627 int *count)
628 {
629 int rval = 0;
630 int len = 0;
631 int j, k;
632
633 if (end0 > end1) {
634 CC_SWAP (end0, end1, k);
635 }
636 for (k = 0; k < adj[end0].deg; k++) {
637 if (adj[end0].list[k].end == end1)
638 break;
639 }
640 if (k == adj[end0].deg) {
641 if (lp->full_edges_valid) {
642 for (j = 0; j < lp->fulladj[end0].deg; j++) {
643 if (lp->fulladj[end0].list[j].end == end1) {
644 len = lp->fulladj[end0].list[j].len;
645 break;
646 }
647 }
648 if (j == lp->fulladj[end0].deg) {
649 fprintf (stderr, "ERROR: fixed/branch edge not in fulladj\n");
650 rval = 1; goto CLEANUP;
651 }
652 } else {
653 len = CCutil_dat_edgelen (end0, end1, lp->dat);
654 }
655 adj[end0].list[adj[end0].deg].end = end1;
656 adj[end0].list[adj[end0].deg].len = len;
657 adj[end0].deg++;
658 (*count)++;
659 }
660
661 CLEANUP:
662
663 return rval;
664 }
665
big_pricing_duals(CCtsp_lp * lp,CCbigguy * node_pi,CCbigguy * node_piest,CCbigguy * node_domino,CCbigguy * cut_pi,CCbigguy * clique_pi,CCbigguy * rhs_sum)666 static int big_pricing_duals (CCtsp_lp *lp, CCbigguy *node_pi,
667 CCbigguy *node_piest, CCbigguy *node_domino, CCbigguy *cut_pi,
668 CCbigguy *clique_pi, CCbigguy *rhs_sum)
669 {
670 CCbigguy x;
671 int i, j, k, s, tmp;
672 int rval = 0;
673 CCtsp_lpcut *c;
674
675 *rhs_sum = CCbigguy_ZERO;
676
677 if (!lp->exact_dual || lp->exact_dual->cutcount != lp->cuts.cutcount) {
678 fprintf (stderr, "no exact_dual in big_pricing_duals\n");
679 rval = 1; goto CLEANUP;
680 }
681
682 for (i = 0; i < lp->graph.ncount; i++) {
683 node_pi[i] = lp->exact_dual->node_pi[i];
684 }
685 for (i = 0; i < lp->cuts.cutcount; i++) {
686 cut_pi[i] = lp->exact_dual->cut_pi[i];
687 }
688
689 for (i = 0; i < lp->graph.ncount; i++)
690 CCbigguy_addmult (rhs_sum, node_pi[i], 2);
691
692 for (i = 0; i < lp->cuts.cutcount; i++) {
693 x = cut_pi[i];
694 CCbigguy_addmult (rhs_sum, x, lp->cuts.cuts[i].rhs);
695 for (j = 0; j < lp->cuts.cuts[i].modcount; j++) {
696 CCbigguy_addmult (rhs_sum, x,
697 2 * (lp->cuts.cuts[i].mods[j].mult - 128));
698 }
699 }
700
701 for (i = 0; i < lp->cuts.cliqueend; i++) {
702 clique_pi[i] = CCbigguy_ZERO;
703 }
704
705 for (i = 0; i < lp->cuts.cutcount; i++) {
706 x = cut_pi[i];
707 for (j = 0; j < lp->cuts.cuts[i].modcount; j++) {
708 CCbigguy_addmult (&(node_pi[lp->cuts.cuts[i].mods[j].node]), x,
709 lp->cuts.cuts[i].mods[j].mult - 128);
710 }
711 if (lp->cuts.cuts[i].dominocount <= 0) {
712 for (j = 0; j < lp->cuts.cuts[i].cliquecount; j++) {
713 CCbigguy_add (&(clique_pi[lp->cuts.cuts[i].cliques[j]]), x);
714 }
715 }
716 }
717
718 for (i = 0; i < lp->graph.ncount; i++) {
719 node_piest[i] = node_pi[i];
720 }
721
722 for (i = 0; i < lp->cuts.cliqueend; i++) {
723 x = clique_pi[i];
724 if (CCbigguy_cmp (x, CCbigguy_ZERO) > 0) {
725 CC_FOREACH_NODE_IN_CLIQUE (j, lp->cuts.cliques[i], tmp) {
726 CCbigguy_add (&(node_pi[j]), x);
727 CCbigguy_add (&(node_piest[j]), x);
728 }
729 } else if (CCbigguy_cmp (x, CCbigguy_ZERO) < 0) {
730 CC_FOREACH_NODE_IN_CLIQUE (j, lp->cuts.cliques[i], tmp) {
731 CCbigguy_add (&(node_pi[j]), x);
732 }
733 }
734 }
735
736 if (node_domino) {
737 for (i = 0; i < lp->graph.ncount; i++) {
738 node_domino[i] = CCbigguy_ZERO;
739 }
740 for (i = 0; i < lp->cuts.cutcount; i++) {
741 c = &lp->cuts.cuts[i];
742 if (c->dominocount > 0) {
743 x = cut_pi[i];
744 if (CCbigguy_cmp (x, CCbigguy_ZERO) > 0) {
745 if (c->cliquecount != 1) {
746 fprintf (stderr, "YIPES: No handle for domino\n");
747 rval = 1; goto CLEANUP;
748 }
749 CC_FOREACH_NODE_IN_CLIQUE (j,
750 lp->cuts.cliques[c->cliques[0]], tmp) {
751 CCbigguy_add (&(node_domino[j]), x);
752 }
753 for (k = 0; k < c->dominocount; k++) {
754 for (s = 0; s < 2; s++) {
755 CC_FOREACH_NODE_IN_CLIQUE (j,
756 lp->cuts.dominos[c->dominos[k]].sets[s], tmp) {
757 CCbigguy_addmult (&(node_domino[j]), x, 2);
758 }
759 }
760 }
761 } else if (CCbigguy_cmp (x, CCbigguy_ZERO) < 0) {
762 fprintf (stderr, "YIPES: negative domino\n");
763 rval = 1; goto CLEANUP;
764 }
765 }
766 }
767 }
768
769 CLEANUP:
770
771 return rval;
772 }
773
big_price_list(CCtsp_lp * lp,int ecount,bigpredge * elist,CCbigguy * node_pi,CCbigguy * clique_pi,CCbigguy * cut_pi)774 static int big_price_list (CCtsp_lp *lp, int ecount, bigpredge *elist,
775 CCbigguy *node_pi, CCbigguy *clique_pi, CCbigguy *cut_pi)
776 {
777 CCtsp_lpadj *adjspace = (CCtsp_lpadj *) NULL;
778 CCtsp_lpnode *n = (CCtsp_lpnode *) NULL;
779 int *temp_elist = (int *) NULL;
780 int i, j, tmp, l, nzlist, nznext;
781 CCtsp_lpadj *a;
782 int marker = 0;
783 CCbigguy x;
784 int ncount = lp->graph.ncount;
785 int ccount = lp->cuts.cliqueend;
786 CCtsp_lpclique *c = lp->cuts.cliques;
787 CCtsp_lpcut *cut;
788 CCtsp_lpgraph g;
789 int rval = 0;
790
791 CCtsp_init_lpgraph_struct (&g);
792
793 if (ecount == 0) goto CLEANUP;
794
795 n = CC_SAFE_MALLOC (ncount, CCtsp_lpnode);
796 CCcheck_NULL (n, "out of memory in big_price_list");
797 adjspace = CC_SAFE_MALLOC (2*ecount, CCtsp_lpadj);
798 CCcheck_NULL (adjspace, "out of memory in big_price_list");
799
800 for (i = 0; i < ncount; i++) {
801 n[i].deg = 0;
802 n[i].mark = 0;
803 }
804 for (i = 0; i < ecount; i++) {
805 elist[i].rc = CCbigguy_itobigguy (elist[i].len);
806 CCbigguy_sub (&(elist[i].rc), node_pi[elist[i].ends[0]]);
807 CCbigguy_sub (&(elist[i].rc), node_pi[elist[i].ends[1]]);
808 n[elist[i].ends[0]].deg++;
809 n[elist[i].ends[1]].deg++;
810 }
811 a = adjspace;
812 for (i = 0; i < ncount; i++) {
813 n[i].adj = a;
814 a += n[i].deg;
815 n[i].deg = 0;
816 }
817 for (i = 0; i < ecount; i++) {
818 j = elist[i].ends[0];
819 n[j].adj[n[j].deg].to = elist[i].ends[1];
820 n[j].adj[n[j].deg].edge = i;
821 n[j].deg++;
822 j = elist[i].ends[1];
823 n[j].adj[n[j].deg].to = elist[i].ends[0];
824 n[j].adj[n[j].deg].edge = i;
825 n[j].deg++;
826 }
827
828 for (i = 0; i < ccount; i++) {
829 if (CCbigguy_cmp (clique_pi[i], CCbigguy_ZERO)) {
830 x = clique_pi[i];
831 CCbigguy_add (&x, clique_pi[i]);
832 marker++;
833 CC_FOREACH_NODE_IN_CLIQUE (j, c[i], tmp) {
834 a = n[j].adj;
835 for (l = 0; l < n[j].deg; l++) {
836 if (n[a[l].to].mark == marker) {
837 CCbigguy_add (&(elist[a[l].edge].rc), x);
838 }
839 }
840 n[j].mark = marker;
841 }
842 }
843 }
844
845 /* Price dominos, using nzlist */
846
847 if (lp->cuts.dominoend > 0) {
848 temp_elist = CC_SAFE_MALLOC (2*ecount, int);
849 CCcheck_NULL (temp_elist, "out of memory in price_list");
850 for (i = 0; i < ecount; i++) {
851 temp_elist[2*i] = elist[i].ends[0];
852 temp_elist[2*i+1] = elist[i].ends[1];
853 }
854 rval = CCtsp_build_lpgraph (&g, ncount, ecount, temp_elist,
855 (int *) NULL);
856 CCcheck_rval (rval, "CCtsp_build_lpgraph failed");
857 rval = CCtsp_build_lpadj (&g, 0, ecount);
858 CCcheck_rval (rval, "CCtsp_build_lpadj failed");
859 CC_FREE (temp_elist, int);
860
861 for (i = 0; i < lp->cuts.cutcount; i++) {
862 cut = &lp->cuts.cuts[i];
863 if (cut->dominocount > 0) {
864 x = cut_pi[i];
865 if (CCbigguy_cmp (x, CCbigguy_ZERO) > 0) {
866 if (cut->cliquecount != 1) {
867 fprintf (stderr, "YIPES: No handle for domino\n");
868 rval = 1; goto CLEANUP;
869 }
870 nzlist = CCtsp_lpcut_nzlist (&g, cut, lp->cuts.cliques,
871 lp->cuts.dominos, 0);
872 while (nzlist != -1) {
873 nznext = g.edges[nzlist].coefnext;
874 g.edges[nzlist].coefnext = -2;
875 if (g.edges[nzlist].coef) {
876 CCbigguy_addmult (&(elist[nzlist].rc), x,
877 -g.edges[nzlist].coef);
878 g.edges[nzlist].coef = 0;
879 }
880 nzlist = nznext;
881 }
882 } else if (CCbigguy_cmp (x, CCbigguy_ZERO) < 0) {
883 fprintf (stderr, "YIPES: negative domino\n");
884 rval = 1; goto CLEANUP;
885 }
886 }
887 }
888 }
889
890 CLEANUP:
891
892 CC_IFFREE (n, CCtsp_lpnode);
893 CC_IFFREE (adjspace, CCtsp_lpadj);
894 CC_IFFREE (temp_elist, int);
895 CCtsp_free_lpgraph (&g);
896
897 return rval;
898 }
899
big_generate_edges(CCtsp_lp * lp,int use_full_edges,CCbigguy * node_piest,CCbigguy * node_domino,int nwant,int * gencount,bigpredge * genlist,int * n1,int * n2,int * finished,CCbigguy cutoff,int phase1)900 static int big_generate_edges (CCtsp_lp *lp, int use_full_edges,
901 CCbigguy *node_piest, CCbigguy *node_domino, int nwant, int *gencount,
902 bigpredge *genlist, int *n1, int *n2, int *finished, CCbigguy cutoff,
903 int phase1)
904 {
905 int i = *n1;
906 int j = *n2;
907 int cnt = 0;
908 int len;
909 CCtsp_genadj *adj;
910 CCdatagroup *dat;
911 int ncount = lp->graph.ncount;
912
913 *gencount = 0;
914 *finished = 0;
915
916 if (!lp->dat && !use_full_edges) {
917 fprintf (stderr, "no source of edges in big_generate_edges\n");
918 return 1;
919 }
920
921 if (i >= ncount) {
922 *finished = 1;
923 return 0;
924 }
925
926 if (use_full_edges) {
927 if (!phase1) {
928 adj = lp->fulladj;
929 for (; j < adj[i].deg; j++) {
930 if (test_edge (i, adj[i].list[j].end, adj[i].list[j].len,
931 node_piest, node_domino, cutoff)) {
932 genlist[cnt].ends[0] = i;
933 genlist[cnt].ends[1] = adj[i].list[j].end;
934 genlist[cnt].len = adj[i].list[j].len;
935 cnt++;
936 if (cnt == nwant) {
937 *finished = 0;
938 *gencount = cnt;
939 *n1 = i; *n2 = j + 1;
940 return 0;
941 }
942 }
943 }
944 for (i++; i < ncount; i++) {
945 for (j = 0; j < adj[i].deg; j++) {
946 if (test_edge (i, adj[i].list[j].end, adj[i].list[j].len,
947 node_piest, node_domino, cutoff)) {
948 genlist[cnt].ends[0] = i;
949 genlist[cnt].ends[1] = adj[i].list[j].end;
950 genlist[cnt].len = adj[i].list[j].len;
951 cnt++;
952 if (cnt == nwant) {
953 *finished = 0;
954 *gencount = cnt;
955 *n1 = i; *n2 = j + 1;
956 return 0;
957 }
958 }
959 }
960 }
961 } else {
962 adj = lp->fulladj;
963 for (; j < adj[i].deg; j++) {
964 if (test_edge (i, adj[i].list[j].end, 0, node_piest,
965 node_domino, cutoff)) {
966 genlist[cnt].ends[0] = i;
967 genlist[cnt].ends[1] = adj[i].list[j].end;
968 genlist[cnt].len = 0;
969 cnt++;
970 if (cnt == nwant) {
971 *finished = 0;
972 *gencount = cnt;
973 *n1 = i; *n2 = j + 1;
974 return 0;
975 }
976 }
977 }
978 for (i++; i < ncount; i++) {
979 for (j = 0; j < adj[i].deg; j++) {
980 if (test_edge (i, adj[i].list[j].end, 0, node_piest,
981 node_domino, cutoff)) {
982 genlist[cnt].ends[0] = i;
983 genlist[cnt].ends[1] = adj[i].list[j].end;
984 genlist[cnt].len = 0;
985 cnt++;
986 if (cnt == nwant) {
987 *finished = 0;
988 *gencount = cnt;
989 *n1 = i; *n2 = j + 1;
990 return 0;
991 }
992 }
993 }
994 }
995 }
996 } else {
997 if (!phase1) {
998 dat = lp->dat;
999 for (; j < ncount; j++) {
1000 len = CCutil_dat_edgelen (i, j, dat);
1001 if (test_edge (i, j, len, node_piest, node_domino, cutoff)) {
1002 genlist[cnt].ends[0] = i;
1003 genlist[cnt].ends[1] = j;
1004 genlist[cnt].len = len;
1005 cnt++;
1006 if (cnt == nwant) {
1007 *finished = 0;
1008 *gencount = cnt;
1009 *n1 = i; *n2 = j + 1;
1010 return 0;
1011 }
1012 }
1013 }
1014 for (i++; i < ncount; i++) {
1015 for (j = i + 1; j < ncount; j++) {
1016 len = CCutil_dat_edgelen (i, j, dat);
1017 if (test_edge (i, j, len, node_piest, node_domino,
1018 cutoff)) {
1019 genlist[cnt].ends[0] = i;
1020 genlist[cnt].ends[1] = j;
1021 genlist[cnt].len = len;
1022 cnt++;
1023 if (cnt == nwant) {
1024 *finished = 0;
1025 *gencount = cnt;
1026 *n1 = i; *n2 = j + 1;
1027 return 0;
1028 }
1029 }
1030 }
1031 }
1032 } else {
1033 for (; j < ncount; j++) {
1034 if (test_edge (i, j, 0, node_piest, node_domino, cutoff)) {
1035 genlist[cnt].ends[0] = i;
1036 genlist[cnt].ends[1] = j;
1037 genlist[cnt].len = 0;
1038 cnt++;
1039 if (cnt == nwant) {
1040 *finished = 0;
1041 *gencount = cnt;
1042 *n1 = i; *n2 = j + 1;
1043 return 0;
1044 }
1045 }
1046 }
1047 for (i++; i < ncount; i++) {
1048 for (j = i + 1; j < ncount; j++) {
1049 if (test_edge (i, j, 0, node_piest, node_domino, cutoff)) {
1050 genlist[cnt].ends[0] = i;
1051 genlist[cnt].ends[1] = j;
1052 genlist[cnt].len = 0;
1053 cnt++;
1054 if (cnt == nwant) {
1055 *finished = 0;
1056 *gencount = cnt;
1057 *n1 = i; *n2 = j + 1;
1058 return 0;
1059 }
1060 }
1061 }
1062 }
1063 }
1064 }
1065
1066 *n1 = ncount;
1067 *n2 = ncount;
1068 *gencount = cnt;
1069 *finished = 1;
1070
1071 return 0;
1072 }
1073
test_edge(int end1,int end2,int len,CCbigguy * node_pi,CCbigguy * node_domino,CCbigguy cutoff)1074 static int test_edge (int end1, int end2, int len, CCbigguy *node_pi,
1075 CCbigguy *node_domino, CCbigguy cutoff)
1076 {
1077 CCbigguy rc;
1078
1079 rc = CCbigguy_itobigguy (len);
1080 CCbigguy_sub (&rc, node_pi[end1]);
1081 CCbigguy_sub (&rc, node_pi[end2]);
1082 if (node_domino) {
1083 CCbigguy_sub (&rc, node_domino[end1]);
1084 CCbigguy_sub (&rc, node_domino[end2]);
1085 }
1086 if (CCbigguy_cmp (rc, cutoff) <= 0) {
1087 return 1;
1088 } else {
1089 return 0;
1090 }
1091 }
1092
CCtsp_exact_dual(CCtsp_lp * lp)1093 int CCtsp_exact_dual (CCtsp_lp *lp)
1094 {
1095 int i;
1096 int ncount = lp->graph.ncount;
1097 int cutcount = lp->cuts.cutcount;
1098 double *d_node_pi = (double *) NULL;
1099 double *d_cut_pi = (double *) NULL;
1100 CCtsp_bigdual *d = (CCtsp_bigdual *) NULL;
1101 int rval = 0;
1102
1103 rval = CCtsp_get_lp_result (lp, (double *) NULL, (double *) NULL,
1104 (int *) NULL, (int **) NULL, (double **) NULL,
1105 (double **) NULL, &d_node_pi, &d_cut_pi);
1106 if (rval) {
1107 fprintf (stderr, "get_lp_result failed\n");
1108 fflush (stdout);
1109 goto CLEANUP;
1110 }
1111
1112 d = CC_SAFE_MALLOC (1, CCtsp_bigdual);
1113 if (!(d)) {
1114 fprintf (stderr, "out of memory in CCtsp_exact_dual C\n");
1115 rval = 1; goto CLEANUP;
1116 }
1117 d->cutcount = cutcount;
1118 d->node_pi = (CCbigguy *) NULL;
1119 d->cut_pi = (CCbigguy *) NULL;
1120
1121 d->node_pi = CC_SAFE_MALLOC (ncount, CCbigguy);
1122 if (!d->node_pi) {
1123 fprintf (stderr, "out of memory in CCtsp_exact_dual B\n");
1124 CC_FREE (d, CCtsp_bigdual);
1125 rval = 1; goto CLEANUP;
1126 }
1127
1128 for (i = 0; i < ncount; i++) {
1129 d->node_pi[i] = CCbigguy_dtobigguy (d_node_pi[i]);
1130 }
1131
1132 if (cutcount) {
1133 d->cut_pi = CC_SAFE_MALLOC (cutcount, CCbigguy);
1134 if (!d->cut_pi) {
1135 fprintf (stderr, "out of memory in CCtsp_exact_dual A\n");
1136 CC_FREE (d->node_pi, CCbigguy);
1137 CC_FREE (d, CCtsp_bigdual);
1138 rval = 1; goto CLEANUP;
1139 }
1140 for (i = 0; i < lp->cuts.cutcount; i++) {
1141 d->cut_pi[i] = CCbigguy_dtobigguy (d_cut_pi[i]);
1142 }
1143 }
1144
1145 if (lp->exact_dual) {
1146 CC_IFFREE (lp->exact_dual->node_pi, CCbigguy);
1147 CC_IFFREE (lp->exact_dual->cut_pi, CCbigguy);
1148 CC_FREE (lp->exact_dual, CCtsp_bigdual);
1149 }
1150 lp->exact_dual = d;
1151
1152
1153 CLEANUP:
1154
1155 CC_IFFREE (d_node_pi, double);
1156 CC_IFFREE (d_cut_pi, double);
1157 return rval;
1158 }
1159
CCtsp_free_bigdual(CCtsp_bigdual ** d)1160 void CCtsp_free_bigdual (CCtsp_bigdual **d)
1161 {
1162 if (d) {
1163 if (*d) {
1164 CC_IFFREE ((*d)->node_pi, CCbigguy);
1165 CC_IFFREE ((*d)->cut_pi, CCbigguy);
1166 CC_IFFREE ((*d), CCtsp_bigdual);
1167 }
1168 }
1169 }
1170
CCtsp_verify_infeasible_lp(CCtsp_lp * lp,int * yesno,int silent)1171 int CCtsp_verify_infeasible_lp (CCtsp_lp *lp, int *yesno, int silent)
1172 {
1173 int rval = 0;
1174 CCbigguy exactbound;
1175
1176 *yesno = 0;
1177 rval = CCtsp_exact_price (lp, &exactbound, 0, 1, silent);
1178 if (rval) {
1179 fprintf (stderr, "CCtsp_exact_price_failed\n"); goto CLEANUP;
1180 }
1181
1182 if (!silent) {
1183 printf ("Exactbound: %f\n", CCbigguy_bigguytod (exactbound));
1184 fflush (stdout);
1185 }
1186
1187 if (CCbigguy_cmp (exactbound, CCbigguy_ZERO) > 0) {
1188 printf ("Problem is shown to be infeasible\n"); fflush (stdout);
1189 *yesno = 1;
1190 lp->infeasible = 1;
1191 lp->lowerbound = CCtsp_LP_MAXDOUBLE;
1192 lp->exact_lowerbound = CCbigguy_MAXBIGGUY;
1193 } else {
1194 printf ("Did not verify an infeasible LP\n"); fflush (stdout);
1195 *yesno = 0;
1196 }
1197
1198 CLEANUP:
1199
1200 return rval;
1201 }
1202
CCtsp_verify_lp_prune(CCtsp_lp * lp,int * yesno,int silent)1203 int CCtsp_verify_lp_prune (CCtsp_lp *lp, int *yesno, int silent)
1204 {
1205 int rval = 0;
1206 CCbigguy exactbound, bnd;
1207
1208 *yesno = 0;
1209 rval = CCtsp_exact_price (lp, &exactbound, 0, 0, silent);
1210 if (rval) {
1211 fprintf (stderr, "CCtsp_exact_price_failed\n"); goto CLEANUP;
1212 }
1213
1214 if (!silent) {
1215 printf ("Exact LP bound: %f\n", CCbigguy_bigguytod (exactbound));
1216 fflush (stdout);
1217 }
1218
1219 bnd = CCbigguy_dtobigguy (lp->upperbound);
1220 CCbigguy_sub (&bnd, CCbigguy_ONE);
1221
1222 if (CCbigguy_cmp (exactbound, bnd) > 0) {
1223 if (!silent) {
1224 printf ("Can prune lp.\n"); fflush (stdout);
1225 }
1226 *yesno = 1;
1227 lp->exact_lowerbound = exactbound;
1228 } else {
1229 if (!silent) {
1230 printf ("Cannot prune lp.\n"); fflush (stdout);
1231 }
1232 *yesno = 0;
1233 }
1234
1235 CLEANUP:
1236
1237 return rval;
1238 }
1239