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 /* */ 19 /* PROTOTYPES FOR FILES IN TSP */ 20 /* */ 21 /****************************************************************************/ 22 /****************************************************************************/ 23 24 25 #ifndef __TSP_H 26 #define __TSP_H 27 28 #include "util.h" 29 #include "edgegen.h" 30 #include "bigguy.h" 31 #include "lp.h" 32 #include "cut.h" 33 #include "kdtree.h" 34 #include "combs.h" 35 36 /*************** Tolerances for the LP and Cutting routines *****************/ 37 38 #define CCtsp_MIN_VIOL (0.002) /* min violation for cut to be added to lp */ 39 #define CCtsp_CUTS_DELTA /* define to set tolerances on ub-lb */ 40 #define CCtsp_CUTS_NEXT_TOL (0.01) /* to try next level */ 41 #define CCtsp_CUTS_NEXT_ROUND (0.001) /* if improve is less, stop round */ 42 #define CCtsp_TENTATIVE_CUTS_NEXT_TOL (0.1) 43 #define CCtsp_TENTATIVE_CUTS_NEXT_ROUND (0.01) 44 #define CCtsp_PRICE_RCTHRESH (-0.00001) /* to add a bad edge */ 45 #define CCtsp_PRICE_MAXPENALTY (0.10) /* penalty permitted in addbad */ 46 #define CCtsp_PHASE1_RCTHRESH (-0.000000001) 47 #define CCtsp_PHASE1_MAXPENALTY (0.00000001) 48 #define CCtsp_EDGE_LIFE (1000000) /* 1000000 */ /* 200 */ /* Large for subtour runs */ 49 #define CCtsp_CUT_LIFE (10) /* 10 */ 50 #define CCtsp_DUAL_DUST (0.01) /* 0.001 */ 51 #define CCtsp_EDGE_DUST (0.000001) /* 0.0001 */ 52 53 #define CCtsp_CUT_BATCH (250) /* number of new cuts before lp optimize */ 54 #define CCtsp_STORE_BATCH (250) /* 50 */ /* number of new cuts before lp addrows */ 55 #define CCtsp_INTTOL (0.0001) /* used to check if lp soln is integral */ 56 57 /************************** Branching Strategies ***************************/ 58 59 #define CCtsp_BRANCH_MIDDLE 1 60 #define CCtsp_BRANCH_STRONG 2 61 62 /****************************************************************************/ 63 64 /************************** Default Communication Ports *********************/ 65 66 #define CCtsp_HOST_PORT ((unsigned short) 24846) 67 #define CCtsp_PROB_PORT ((unsigned short) 24847) 68 #define CCtsp_CUT_PORT ((unsigned short) 24868) 69 #define CCtsp_DOMINO_PORT ((unsigned short) 24869) 70 71 /****************************************************************************/ 72 73 /************************ Experimental Cutting Planes ***********************/ 74 75 #undef CCtsp_USE_DOMINO_CUTS 76 77 /****************************************************************************/ 78 79 #define CCtsp_LP_MAXDOUBLE 1e30 80 81 #define CCtsp_COMBRHS(c) (3*(c)->cliquecount - 2) 82 #define CCtsp_DOMINORHS(c) (3*(c)->dominocount + 1) 83 84 typedef struct CCtsp_lpnode { 85 int deg; 86 int mark; 87 struct CCtsp_lpadj *adj; 88 } CCtsp_lpnode; 89 90 typedef struct CCtsp_lpedge { 91 int ends[2]; /* ends[0] should always be < ends[1] */ 92 int fixed; 93 int branch; /* < 0 means set to 0 and > 0 means set to 1 */ 94 int len; 95 int age; 96 int coef; /* should be maintained at zero */ 97 int coefnext; /* should be maintained at -2 */ 98 } CCtsp_lpedge; 99 100 typedef struct CCtsp_lpadj { 101 int to; 102 int edge; 103 } CCtsp_lpadj; 104 105 typedef struct CCtsp_lpgraph { 106 int ncount; 107 int espace; 108 int ecount; 109 int nodemarker; 110 CCtsp_lpnode *nodes; 111 CCtsp_lpedge *edges; 112 CCtsp_lpadj *adjspace; 113 int adjstart; 114 int adjend; 115 } CCtsp_lpgraph; 116 117 typedef struct CCtsp_predge { 118 int ends[2]; 119 int len; 120 double rc; 121 } CCtsp_predge; 122 123 typedef struct CCtsp_pricegroup { 124 int ncount; 125 int espace; 126 int ecount; 127 CCtsp_lpnode *nodes; 128 CCtsp_predge *edges; 129 int cliquecount; 130 struct CCtsp_lpclique *cliques; /* just a copy of the pointer */ 131 CCtsp_lpgraph *graph; /* pointer to the copy in a CCtsp_lp */ 132 CCtsp_lpadj *adjspace; 133 double *node_pi; 134 double *clique_pi; 135 double penalty; 136 } CCtsp_pricegroup; 137 138 typedef struct CCtsp_extraedge { 139 int ends[2]; 140 } CCtsp_extraedge; 141 142 typedef struct CCtsp_sparser { 143 unsigned int node : 24; 144 unsigned int mult : 8; 145 } CCtsp_sparser; 146 147 typedef struct CCtsp_segment { 148 int lo; 149 int hi; 150 } CCtsp_segment; 151 152 typedef struct CCtsp_lpclique { 153 int segcount; 154 struct CCtsp_segment *nodes; 155 int hashnext; 156 int refcount; 157 } CCtsp_lpclique; 158 159 typedef struct CCtsp_lpdomino { 160 CCtsp_lpclique sets[2]; 161 int hashnext; 162 int refcount; 163 } CCtsp_lpdomino; 164 165 #define CC_FOREACH_NODE_IN_CLIQUE(i,c,tmp) \ 166 for(tmp=0;tmp<(c).segcount;tmp++) \ 167 for(i=(c).nodes[tmp].lo;i<=(c).nodes[tmp].hi;i++) 168 169 typedef struct CCtsp_skeleton { 170 int atomcount; 171 int *atoms; 172 } CCtsp_skeleton; 173 174 #define CCtsp_NEWCUT_AGE (-1) 175 176 typedef struct CCtsp_lpcut { 177 int cliquecount; 178 int dominocount; 179 int modcount; 180 int age; 181 int rhs; 182 char sense; 183 char branch; 184 int *cliques; 185 int *dominos; 186 struct CCtsp_sparser *mods; 187 CCtsp_skeleton skel; 188 } CCtsp_lpcut; 189 190 typedef struct CCtsp_lpcut_in { 191 int cliquecount; 192 int dominocount; 193 int rhs; 194 char sense; 195 char branch; 196 CCtsp_lpclique *cliques; 197 CCtsp_lpdomino *dominos; 198 CCtsp_skeleton skel; 199 struct CCtsp_lpcut_in *next; 200 struct CCtsp_lpcut_in *prev; 201 } CCtsp_lpcut_in; 202 203 typedef struct CCtsp_lp_result { 204 double ub; 205 double lb; 206 int ecount; 207 int *elist; 208 double *x; 209 double *rc; 210 } CCtsp_lp_result; 211 212 typedef struct CCtsp_lpcuts { 213 int cutcount; 214 int savecount; 215 int cliqueend; 216 int cutspace; 217 int cliquespace; 218 int cliquehashsize; 219 int cliquefree; 220 int *cliquehash; 221 CCtsp_lpcut *cuts; 222 CCtsp_lpclique *cliques; 223 CCgenhash *cuthash; 224 char *tempcuthash; 225 int tempcuthashsize; 226 int dominoend; 227 int dominospace; 228 int dominohashsize; 229 int dominofree; 230 int *dominohash; 231 CCtsp_lpdomino *dominos; 232 double *workloads; 233 } CCtsp_lpcuts; 234 235 typedef struct CCtsp_bigdual { 236 int cutcount; 237 CCbigguy *node_pi; 238 CCbigguy *cut_pi; 239 } CCtsp_bigdual; 240 241 typedef struct CCtsp_tighten_info { 242 int ncall; 243 int nfail; 244 int nadd; 245 int nadd_tied; 246 int ndel; 247 int ndel_tied; 248 double add_delta; 249 double del_delta; 250 double time; 251 } CCtsp_tighten_info; 252 253 typedef struct CCtsp_branchobj { 254 int depth; 255 int rhs; 256 int ends[2]; 257 char sense; 258 CCtsp_lpclique *clique; 259 } CCtsp_branchobj; 260 261 typedef struct CCtsp_cutnode { 262 #define CCtsp_CUT_INNODELIST(t) ((t)&4) 263 #define CCtsp_CUT_ROOT 0 264 #define CCtsp_CUT_PNODE 1 265 #define CCtsp_CUT_QNODE 2 266 #define CCtsp_CUT_LEAF 4 267 #define CCtsp_CUT_EXTERN 5 268 int type; 269 struct CCtsp_cutnode *child; 270 struct CCtsp_cutnode *sibling; 271 struct CCtsp_cutnode *next; 272 } CCtsp_cutnode; 273 274 typedef struct CCtsp_cuttree { 275 int nodecount; 276 int extern_node; 277 CCtsp_cutnode *nodelist; 278 CCtsp_cutnode *root; 279 CCptrworld cutnode_world; 280 } CCtsp_cuttree; 281 282 /* nodes are reordered to match compression tour */ 283 284 typedef struct CCtsp_genadj { 285 int deg; 286 struct CCtsp_genadjobj *list; 287 } CCtsp_genadj; 288 289 typedef struct CCtsp_genadjobj { 290 int end; 291 int len; 292 } CCtsp_genadjobj; 293 294 typedef struct CCtsp_edgegenerator { 295 double *node_piest; 296 struct CCdatagroup *dg; 297 int *supply; 298 CCkdtree *kdtree; 299 CCxnear *xnear; 300 struct CCtsp_xnorm_pricer *xprice; 301 CCtsp_genadjobj *adjobjspace; 302 CCtsp_genadj *adj; 303 int ncount; 304 int nneighbors; 305 int start; 306 int current; 307 int supplyhead; 308 int supplycount; 309 } CCtsp_edgegenerator; 310 311 typedef struct CCtsp_xnorm_pricer_val { 312 double val; 313 struct CCtsp_xnorm_pricer_val *next; 314 struct CCtsp_xnorm_pricer_val *prev; 315 int index; 316 } CCtsp_xnorm_pricer_val; 317 318 typedef struct CCtsp_xnorm_pricer { 319 CCdatagroup *dat; 320 double *pi; 321 int *order; 322 CCtsp_xnorm_pricer_val *xminuspi_space; 323 CCtsp_xnorm_pricer_val *xminuspi; 324 int *invxminuspi; 325 int ncount; 326 } CCtsp_xnorm_pricer; 327 328 typedef struct CCtsp_statistics { 329 CCutil_timer cutting_loop; 330 CCutil_timer cutting_inner_loop; 331 CCutil_timer cuts_filecut; 332 CCutil_timer cuts_filecut_opt; 333 CCutil_timer cuts_cutpool; 334 CCutil_timer cuts_cutpool_opt; 335 CCutil_timer cuts_connect; 336 CCutil_timer cuts_connect_opt; 337 CCutil_timer cuts_segment; 338 CCutil_timer cuts_segment_opt; 339 CCutil_timer cuts_remotepool; 340 CCutil_timer cuts_remotepool_opt; 341 CCutil_timer cuts_blockcomb; 342 CCutil_timer cuts_blockcomb_opt; 343 CCutil_timer cuts_growcomb; 344 CCutil_timer cuts_growcomb_opt; 345 CCutil_timer cuts_exactsubtour; 346 CCutil_timer cuts_exactsubtour_opt; 347 CCutil_timer cuts_tighten_lp; 348 CCutil_timer cuts_tighten_lp_opt; 349 CCutil_timer cuts_tighten_lp_close; 350 CCutil_timer cuts_tighten_lp_close_opt; 351 CCutil_timer cuts_decker_lp; 352 CCutil_timer cuts_decker_lp_opt; 353 CCutil_timer cuts_decker_lp_close; 354 CCutil_timer cuts_decker_lp_close_opt; 355 CCutil_timer cuts_star_lp; 356 CCutil_timer cuts_star_lp_opt; 357 CCutil_timer cuts_handling_lp; 358 CCutil_timer cuts_handling_lp_opt; 359 CCutil_timer cuts_cliquetree_lp; 360 CCutil_timer cuts_cliquetree_lp_opt; 361 CCutil_timer cuts_teething_lp; 362 CCutil_timer cuts_teething_lp_opt; 363 CCutil_timer cuts_fastblossom; 364 CCutil_timer cuts_fastblossom_opt; 365 CCutil_timer cuts_ghfastblossom; 366 CCutil_timer cuts_ghfastblossom_opt; 367 CCutil_timer cuts_exactblossom; 368 CCutil_timer cuts_exactblossom_opt; 369 CCutil_timer cuts_tighten_pool; 370 CCutil_timer cuts_tighten_pool_opt; 371 CCutil_timer cuts_decker_pool; 372 CCutil_timer cuts_decker_pool_opt; 373 CCutil_timer cuts_star_pool; 374 CCutil_timer cuts_star_pool_opt; 375 CCutil_timer cuts_handling_pool; 376 CCutil_timer cuts_handling_pool_opt; 377 CCutil_timer cuts_teething_pool; 378 CCutil_timer cuts_teething_pool_opt; 379 CCutil_timer cuts_consecutiveones; 380 CCutil_timer cuts_consecutiveones_opt; 381 CCutil_timer cuts_necklace; 382 CCutil_timer cuts_necklace_opt; 383 CCutil_timer cuts_localcut; 384 CCutil_timer cuts_localcut_opt; 385 386 CCutil_timer cuts_extraconnect; 387 CCutil_timer cuts_extraconnect_opt; 388 389 CCutil_timer sparse_edge_check; 390 CCutil_timer full_edge_check; 391 392 CCutil_timer addcuts; 393 CCutil_timer addcuts_opt; 394 CCutil_timer agecuts; 395 CCutil_timer agecuts_opt; 396 CCutil_timer ageedges; 397 CCutil_timer ageedges_opt; 398 CCutil_timer addbad; 399 CCutil_timer addbad_opt; 400 CCutil_timer strongbranch; 401 CCutil_timer strongbranch_opt; 402 CCutil_timer linkern; 403 404 CCutil_timer misc; 405 CCutil_timer misc_opt; 406 CCutil_timer total; 407 int problem_cnt; 408 409 CCtsp_tighten_info tighten_stats; 410 CCtsp_tighten_info extra_tighten_stats; 411 } CCtsp_statistics; 412 413 typedef struct CCtsp_lp { 414 CCtsp_lpgraph graph; 415 CCtsp_lpcuts cuts; 416 CCtsp_lpcuts *pool; 417 CCtsp_lpcuts *remotepool; 418 CCtsp_lpcuts *dominopool; 419 CClp *lp; 420 int *perm; 421 CCdatagroup *dat; 422 int fullcount; 423 CCtsp_genadj *fulladj; 424 CCtsp_genadjobj *fulladjspace; 425 int nfixededges; 426 int *fixededges; 427 struct CCtsp_qsparsegroup *sparsifier; 428 int edge_life; 429 int cut_life; 430 char *problabel; 431 char *probloc; 432 int id; 433 int parent_id; 434 int root; 435 double upperbound; 436 double lowerbound; 437 CCbigguy exact_lowerbound; 438 CCtsp_bigdual *exact_dual; 439 int infeasible; 440 int full_edges_valid; 441 CClp_warmstart *warmstart; 442 CCtsp_lpcut_in cutqueue; /* dummy entry for doubly-linked 443 list */ 444 CCtsp_lp_result result; 445 int branchdepth; 446 CCtsp_branchobj *branchhistory; 447 CCtsp_cuttree tightcuts; 448 CCtsp_statistics stats; 449 } CCtsp_lp; 450 451 typedef struct CCtsp_lprow { 452 int rowcnt; 453 int nzcnt; 454 char *sense; 455 double *rhs; 456 int *begin; /* offset into the array for start of row */ 457 int indexspace; 458 int *indices; /* the column indices of the row entries */ 459 int entryspace; 460 double *entries; /* the matrix entries */ 461 } CCtsp_lprow; 462 463 typedef struct CCtsp_cutselect { 464 int cutpool; 465 int remotepool; 466 char *remotehost; 467 unsigned short remoteport; 468 int domboss; 469 char *dombosshost; 470 int connect; 471 int segments; 472 int exactsubtour; 473 int blockcombs; 474 int growcombs; 475 int prclique; 476 int tighten_lp; 477 int teething_lp; 478 int cliquetree_lp; 479 int tighten_pool; 480 int decker_lp; 481 int decker_pool; 482 int star_lp; 483 int star_pool; 484 int handling_lp; 485 int handling_pool; 486 int maxchunksize; 487 int filecuts; 488 char *filecutname; 489 int teething_pool; 490 int fastblossom; 491 int ghfastblossom; 492 int exactblossom; 493 int consecutiveones; 494 int dominos; 495 int shrunk_dominos; 496 int necklace; 497 int usetighten; /* set to 1 to tighten before cuts are added */ 498 int extra_connect; /* set to 1 to force a connected solution */ 499 double nexttol; 500 double roundtol; 501 int fastcuts; /* set to 0 to stop the update of tols */ 502 } CCtsp_cutselect; 503 504 505 506 /****************************************************************************/ 507 /* */ 508 /* bcontrol.c */ 509 /* */ 510 /****************************************************************************/ 511 512 #define CCtsp_BBTASK_BRANCH 'b' 513 #define CCtsp_BBREQ_BRANCHDONE 'B' 514 #define CCtsp_BBTASK_CUT 'c' 515 #define CCtsp_BBREQ_CUTDONE 'C' 516 #define CCtsp_BBREQ_DEADNODE 'D' 517 #define CCtsp_BBREQ_HELLO 'H' 518 #define CCtsp_BBREQ_NOBRANCH 'N' 519 #define CCtsp_BBREQ_TASK 'T' 520 #define CCtsp_BBREQ_TOUR 'U' 521 #define CCtsp_BBTASK_WAIT 'w' 522 #define CCtsp_BBTASK_EXIT 'x' 523 #define CCtsp_BBREQ_EXIT 'X' 524 525 #define CCtsp_BBTASK_TENTATIVE_CUT 'i' 526 #define CCtsp_BBREQ_TENTATIVE_CUTDONE 'I' 527 #define CCtsp_BBTASK_TENTATIVE_BRANCH 'j' 528 #define CCtsp_BBREQ_TENTATIVE_BRANCHDONE 'J' 529 530 531 int 532 CCtsp_bfs_brancher (char *probloc, int id, double lowerbound, 533 CCtsp_cutselect *sel, CCtsp_cutselect *tsel, double *upbound, 534 int *bbcount, int usecliques, CCdatagroup *mydat, int *ptour, 535 CCtsp_lpcuts *pool, int ncount, int *besttour, unsigned short hostport, 536 double *branchzeit, int save_proof, int tentative_branch_num, 537 int longedge_branching, double *timebound, int *hit_timebound, 538 int silent, CCrandstate *rstate), 539 CCtsp_bfs_restart (char *probloc, char *restart_name, CCtsp_cutselect *sel, 540 CCtsp_cutselect *tsel, double *upbound, int *bbcount, int usecliques, 541 CCdatagroup *dat, int *ptour, CCtsp_lpcuts *pool, int ncount, 542 int *besttour, unsigned short hostport, double *branchzeit, 543 int save_proof, int tentative_branch_num, int longedge_branching, 544 double *timebound, int *hit_timebound, int silent, 545 CCrandstate *rstate), 546 #ifdef CC_NETREADY 547 CCtsp_grunt (char *hostname, unsigned short hostport, char *poolfname, 548 char *cutbossname, char *probloc, int silent, 549 CCrandstate *rstate), 550 #endif /* CC_NETREADY */ 551 CCtsp_easy_dfs_brancher (CCtsp_lp *lp, CCtsp_cutselect *sel, int depth, 552 double *upbound, int *bbcount, int usecliques, int *besttour, 553 int longedge_branching, int simple_branching, int silent, 554 CCrandstate *rstate), 555 CCtsp_do_interactive_branch (CCtsp_lp *lp, int silent, CCrandstate *rstate); 556 557 558 559 /****************************************************************************/ 560 /* */ 561 /* blkcomb.c */ 562 /* */ 563 /****************************************************************************/ 564 565 566 int 567 CCtsp_block_combs (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 568 int ecount, int *elist, double *x, int silent); 569 570 571 572 /****************************************************************************/ 573 /* */ 574 /* blossom.c */ 575 /* */ 576 /****************************************************************************/ 577 578 579 int 580 CCtsp_fastblossom (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 581 int ecount, int *elist, double *x), 582 CCtsp_ghfastblossom (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 583 int ecount, int *elist, double *x), 584 CCtsp_exactblossom (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 585 int ecount, int *elist, double *x, CCrandstate *rstate); 586 587 588 589 /****************************************************************************/ 590 /* */ 591 /* branch.c */ 592 /* */ 593 /****************************************************************************/ 594 595 596 int 597 CCtsp_find_branch (CCtsp_lp *lp, int nwant, int *ngot, 598 CCtsp_branchobj **bobj, double *val, int **cyc, int usecliques, 599 int longedge_branching, int silent), 600 CCtsp_find_fast_branch (CCtsp_lp *lp, int *ngot, CCtsp_branchobj **bobj, 601 double *val, int **cyc, int usecliques, int longedge_branching, 602 int silent), 603 CCtsp_find_branch_edge (CCtsp_lp *lp, int *n0, int *n1, double *val, 604 int **cyc, int branchtype, int silent), 605 CCtsp_check_integral (CCtsp_lp *lp, double *val, int **cyc, int *yesno, 606 int silent), 607 CCtsp_find_branch_cliques (CCtsp_lp *lp, int nwant, int longedge_branching, 608 int *ngot, CCtsp_lpclique **bcliques, double **bval, int silent), 609 CCtsp_execute_branch (CCtsp_lp *lp, CCtsp_branchobj *b, 610 int silent, CCrandstate *rstate), 611 CCtsp_execute_unbranch (CCtsp_lp *lp, CClp_warmstart *warmstart, 612 int silent, CCrandstate *rstate), 613 CCtsp_add_branchhistory_to_lp (CCtsp_lp *lp), 614 CCtsp_bb_find_branch (char *probname, int probnum, int ncount, 615 CCdatagroup *dat, int *ptour, double *upperbound, CCtsp_lpcuts *pool, 616 int nwant, int *ngot, CCtsp_branchobj **b, int usecliques, 617 int longedge_branching, int *prune, int *foundtour, int *besttour, 618 int silent, CCrandstate *rstate), 619 CCtsp_splitprob (CCtsp_lp *lp, CCtsp_branchobj *b, int child0, int child1, 620 int silent, CCrandstate *rstate), 621 CCtsp_bb_splitprob (char *probname, int probnum, int ncount, 622 CCdatagroup *dat, int *ptour, double initial_ub, CCtsp_lpcuts *pool, 623 CCtsp_branchobj *b, int child0, int child1, double *val0, double *val1, 624 int *prune0, int *prune1, int silent, CCrandstate *rstate), 625 CCtsp_dumptour (int ncount, CCdatagroup *dat, int *perm, char *probname, 626 int *tour, char *fname, int writeedges, int silent); 627 628 void 629 CCtsp_init_branchobj (CCtsp_branchobj *b), 630 CCtsp_free_branchobj (CCtsp_branchobj *b), 631 CCtsp_print_branchhistory (CCtsp_lp *lp); 632 633 634 /****************************************************************************/ 635 /* */ 636 /* cliqhash.c */ 637 /* */ 638 /****************************************************************************/ 639 640 641 int 642 CCtsp_init_cliquehash (CCtsp_lpcuts *cuts, int size), 643 CCtsp_register_clique (CCtsp_lpcuts *cuts, CCtsp_lpclique *c); 644 645 unsigned int 646 CCtsp_hashclique (CCtsp_lpclique *c); 647 648 void 649 CCtsp_free_cliquehash (CCtsp_lpcuts *cuts), 650 CCtsp_unregister_clique (CCtsp_lpcuts *cuts, int c), 651 CCtsp_clique_eq (CCtsp_lpclique *c, CCtsp_lpclique *d, int *yes_no); 652 653 int 654 CCtsp_init_dominohash (CCtsp_lpcuts *cuts, int size), 655 CCtsp_register_domino (CCtsp_lpcuts *cuts, CCtsp_lpdomino *c); 656 657 unsigned int 658 CCtsp_hashdomino (CCtsp_lpdomino *d); 659 660 void 661 CCtsp_free_dominohash (CCtsp_lpcuts *cuts), 662 CCtsp_domino_eq (CCtsp_lpdomino *c, CCtsp_lpdomino *d, int *yes_no), 663 CCtsp_unregister_domino (CCtsp_lpcuts *cuts, int c); 664 665 666 667 /****************************************************************************/ 668 /* */ 669 /* cliqwork.c */ 670 /* */ 671 /****************************************************************************/ 672 673 typedef struct CCtsp_cutinfo { 674 CC_SRKexpinfo expand; 675 CCtsp_lpcut_in **clist; 676 CCtsp_lpcut_in *current; 677 int *cutcount; 678 } CCtsp_cutinfo; 679 680 681 int 682 CCtsp_clique_to_array (CCtsp_lpclique *c, int **ar, int *count), 683 CCtsp_clique_delta (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *c, 684 double *delta), 685 CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new), 686 CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b, int ncount), 687 CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, int acount, 688 int ncount), 689 CCtsp_array_to_lpclique (int *ar, int acount, CCtsp_lpclique *cliq), 690 CCtsp_seglist_to_lpclique (int nseg, int *list, CCtsp_lpclique *cliq), 691 CCtsp_shrunk_set_to_lpclique (int cnt, int *set, int *wset, 692 CC_SRKexpinfo *expand, CCtsp_lpclique *cliq), 693 CCtsp_add_nodes_to_lpclique (CCtsp_lpclique *cin, CCtsp_lpclique *cout, 694 int addcount, int *adda), 695 CCtsp_delete_nodes_from_lpclique (CCtsp_lpclique *cin, 696 CCtsp_lpclique *cout, int delcount, int *del), 697 CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c, 698 CCtsp_lpcut_in *new), 699 CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new), 700 CCtsp_copy_lpdomino (CCtsp_lpdomino *c, CCtsp_lpdomino *new), 701 CCtsp_create_lpcliques (CCtsp_lpcut_in *c, int cliquecount), 702 CCtsp_max_node (CCtsp_lpcut_in *c), 703 CCtsp_build_dp_cut (CCtsp_lpcut_in **cut, int ndomino, int *Acount, 704 int **A, int *Bcount, int **B, int handlecount, int *handle); 705 706 void 707 CCtsp_mark_clique (CCtsp_lpclique *c, int *marks, int marker), 708 CCtsp_mark_domino (CCtsp_lpdomino *c, int *marks, int marker), 709 CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpclique *c, 710 int *marks, int marker), 711 CCtsp_mark_domino_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpdomino *c, 712 int *marks, int marker), 713 CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph *g, 714 CCtsp_lpclique *c, double *marks, double marker), 715 CCtsp_mark_cut (CCtsp_lpcut_in *c, int *marks, int marker), 716 CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, 717 int *marks, int marker), 718 CCtsp_is_clique_marked (CCtsp_lpclique *c, int *marks, int marker, 719 int *yes_no), 720 CCtsp_clique_count (CCtsp_lpclique *c, int *count), 721 CCtsp_clique_marked_count (CCtsp_lpclique *c, int *marks, int marker, 722 int *count), 723 CCtsp_init_lpcut_in (CCtsp_lpcut_in *c), 724 CCtsp_init_lpcut (CCtsp_lpcut *c), 725 CCtsp_init_lpclique (CCtsp_lpclique *c), 726 CCtsp_init_lpdomino (CCtsp_lpdomino *c), 727 CCtsp_print_lpcut_in (CCtsp_lpcut_in *c), 728 CCtsp_print_lpclique (CCtsp_lpclique *c), 729 CCtsp_print_lpdomino (CCtsp_lpdomino *d), 730 CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b, int *diff); 731 732 733 734 /****************************************************************************/ 735 /* */ 736 /* control.c */ 737 /* */ 738 /****************************************************************************/ 739 740 741 int 742 CCtsp_cutting_multiple_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, 743 int savelp, int maxlocal, int update_tol, int silent, 744 CCrandstate *rstate), 745 CCtsp_cutting_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, int savelp, 746 int silent, CCrandstate *rstate), 747 CCtsp_subtour_loop (CCtsp_lp *lp, int silent, CCrandstate *rstate), 748 CCtsp_blossom_loop (CCtsp_lp *lp, int silent, CCrandstate *rstate), 749 CCtsp_subtour_and_blossom_loop (CCtsp_lp *lp, int silent, 750 CCrandstate *rstate), 751 CCtsp_pricing_loop (CCtsp_lp *lp, double *bnd, int silent, 752 CCrandstate *rstate), 753 CCtsp_call_x_heuristic (CCtsp_lp *lp, double *val, int *outcyc, 754 int silent, CCrandstate *rstate), 755 CCtsp_bb_cutting (char *probname, int probnum, int prob_newnum, int ncount, 756 CCdatagroup *dat, int *ptour, double *upbound, CCtsp_lpcuts *pool, 757 CCtsp_cutselect *sel, double *val, int *prune, int *foundtour, 758 int *besttour, int level, int silent, CCrandstate *rstate), 759 CCtsp_cutselect_set_tols (CCtsp_cutselect *s, CCtsp_lp *lp, int level, 760 int silent); 761 762 void 763 CCtsp_init_cutselect (CCtsp_cutselect *s), 764 CCtsp_cutselect_dominos (CCtsp_cutselect *s, int domsel), 765 CCtsp_cutselect_tighten (CCtsp_cutselect *s, int tighten), 766 CCtsp_cutselect_chunksize (CCtsp_cutselect *s, int chunksize), 767 CCtsp_cutselect_filecuts (CCtsp_cutselect *s, char *fname), 768 CCtsp_cutselect_remotepool (CCtsp_cutselect *s, char *cutbossname), 769 CCtsp_cutselect_domboss (CCtsp_cutselect *s, char *dombossname), 770 CCtsp_init_tentative_cutselect (CCtsp_cutselect *s), 771 CCtsp_init_simple_cutselect (CCtsp_cutselect *s), 772 CCtsp_init_fast_cutselect (CCtsp_cutselect *s); 773 774 775 /****************************************************************************/ 776 /* */ 777 /* cutcall.c */ 778 /* */ 779 /****************************************************************************/ 780 781 782 int 783 CCtsp_connect_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 784 int ecount, int *elist, double *x), 785 CCtsp_segment_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 786 int ecount, int *elist, double *x), 787 CCtsp_shrink_subtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 788 int ecount, int *elist, double *x), 789 CCtsp_exact_subtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 790 int ecount, int *elist, double *x), 791 CCtsp_tighten_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 792 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 793 int *elist, double *x, double testtol, int maxcuts, 794 double *viol, CCrandstate *rstate), 795 CCtsp_double_decker_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 796 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 797 int *elist, double *x, double testtol, int maxcuts, 798 double *viol, CCrandstate *rstate), 799 CCtsp_cliquetree_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 800 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 801 int *elist, double *x, double testtol, int maxcuts, 802 double *viol, CCrandstate *rstate), 803 CCtsp_star_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 804 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 805 int *elist, double *x, double testtol, int maxcuts, 806 double *viol, CCrandstate *rstate), 807 CCtsp_handling_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 808 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 809 int *elist, double *x, double testtol, int maxcuts, 810 double *viol, CCrandstate *rstate), 811 CCtsp_teething_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 812 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 813 int *elist, double *x, double testtol, int maxcuts, 814 double *viol, CCrandstate *rstate), 815 CCtsp_domino_trial (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 816 int ecount, int *elist, double *x, CCrandstate *rstate), 817 CCtsp_file_cuts (char *cutfile, CCtsp_lpcut_in **cuts, int *cutcount, 818 int ncount, int *tour), 819 CCtsp_file_cuts_write (const char *cutfile, CCtsp_lpcuts *cuts, int *tour), 820 CCtsp_test_pure_comb (int ncount, CCtsp_lpcut_in *c, int *yes_no, 821 int *handle), 822 CCtsp_test_pseudocomb (int ncount, CCtsp_lpcut_in *c, int handle, 823 int *yes_no), 824 CCtsp_test_teeth_disjoint (int ncount, CCtsp_lpcut_in *c, int handle, 825 int *yes_no), 826 CCtsp_find_pure_handle (int ncount, CCtsp_lpcut_in *c, int *handle), 827 CCtsp_truncate_cutlist (CCtsp_lpcut_in **cuts, int ncount, int ecount, 828 int *elist, double *x, int maxcuts, CCrandstate *rstate), 829 CCtsp_buildcut_begin (CCtsp_cutinfo *cuts, int init_cliquecount), 830 CCtsp_buildcut_addclique (CCtsp_cutinfo *cuts, int *arr, int size), 831 CCtsp_buildcut_finish (CCtsp_cutinfo *cuts, int rhs), 832 CCtsp_new_domino (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 833 int ecount, int *elist, double *x, const char *bossname), 834 CCtsp_shrink_domino (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 835 int ecount, int *elist, double *x, int quickshrink, int rand_minor, 836 CCrandstate *rstate, const char *bossname); 837 838 void 839 CCtsp_buildcut_abort (CCtsp_cutinfo *cuts); 840 841 842 843 /****************************************************************************/ 844 /* */ 845 /* cutpool.c */ 846 /* */ 847 /****************************************************************************/ 848 849 #define CCtsp_POOL_GETCUTS 'G' 850 #define CCtsp_POOL_PUTCUTS 'P' 851 #define CCtsp_POOL_SAVECUTS 'S' 852 #define CCtsp_POOL_EXIT 'X' 853 854 855 int 856 CCtsp_init_cutpool (int *ncount, char *poolfilename, CCtsp_lpcuts **pool), 857 CCtsp_write_cutpool (int ncount, const char *poolfilename, 858 CCtsp_lpcuts *pool), 859 CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts, 860 int *cutcount, double *maxviol, int ncount, int ecount, int *elist, 861 double *x, int nthreads, CCrandstate *rstate), 862 CCtsp_search_remotepool (char *remotehost, unsigned short remoteport, 863 CCtsp_lpcut_in **cuts, int *cutcount, double *maxviol, int ncount, 864 int ecount, int *elist, double *x), 865 CCtsp_read_cuts (CC_SFILE *f, int *ncount, CCtsp_lpcuts *cuts, 866 int readmods, int buildhash), 867 CCtsp_read_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount), 868 CCtsp_read_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount), 869 CCtsp_read_lpdomino (CC_SFILE *f, CCtsp_lpdomino *d, int ncount), 870 CCtsp_write_cuts (CC_SFILE *f, int ncount, CCtsp_lpcuts *cuts, 871 int writemods), 872 CCtsp_send_newcuts (int ncount, CCtsp_lpcuts *pool, char *remotehost, 873 unsigned short remoteport), 874 CCtsp_write_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount), 875 CCtsp_write_lpcut (CC_SFILE *f, CCtsp_lpcuts *cuts, CCtsp_lpcut *c, 876 int ncount), 877 CCtsp_write_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount), 878 CCtsp_write_lpdomino (CC_SFILE *f, CCtsp_lpdomino *c, int ncount), 879 CCtsp_copy_cuts (CC_SFILE *f, CC_SFILE *t, int copymods), 880 CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques, 881 int *cliquecount, int ncount, int ecount, int *elist, double *x, 882 double maxdelta, int maxcliques, double **cliquevals, 883 CCrandstate *rstate), 884 CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques, 885 int *cliquecount, int ncount, int ecount, int *elist, double *x, 886 int nwant, double **cliquevals, int silent), 887 CCtsp_get_clique_prices (CCtsp_lpcuts *pool, int **p_cliquenums, 888 double **p_cliquevals, double mindelta, double maxdelta, 889 int *p_cliquecount, int ncount, int ecount, int *elist, double *x), 890 CCtsp_get_clique (CCtsp_lpcuts *pool, int cliquenum, 891 CCtsp_lpclique **p_clique), 892 CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts, 893 CCtsp_lpcut *c), 894 CCtsp_add_to_dominopool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts, 895 CCtsp_lpcut *c), 896 CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool, CCtsp_lpcut_in *cut), 897 CCtsp_display_cutpool (CCtsp_lpcuts *pool), 898 CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount, int *elist, 899 double *x, double *cutval), 900 CCtsp_price_cuts_threaded (CCtsp_lpcuts *pool, int ncount, int ecount, 901 int *elist, double *x, double *cutval, int numthreads), 902 CCtsp_register_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c, 903 CCtsp_lpcut *new), 904 CCtsp_register_dominos (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c, 905 CCtsp_lpcut *new), 906 CCtsp_add_cut_to_cutlist (CCtsp_lpcuts *cuts, CCtsp_lpcut *c); 907 908 void 909 CCtsp_free_cutpool (CCtsp_lpcuts **pool), 910 CCtsp_free_lpcut_in (CCtsp_lpcut_in *c), 911 CCtsp_free_lpclique (CCtsp_lpclique *c), 912 CCtsp_free_lpdomino (CCtsp_lpdomino *c), 913 CCtsp_unregister_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut *c), 914 CCtsp_unregister_dominos (CCtsp_lpcuts *cuts, CCtsp_lpcut *c), 915 CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts *cuts, int ind); 916 917 918 /****************************************************************************/ 919 /* */ 920 /* ddecker.c */ 921 /* */ 922 /****************************************************************************/ 923 924 925 int 926 CCtsp_test_pure_double_decker (CCtsp_lpcut_in *c, int *yes_no, 927 int *handle1, int *handle2), 928 CCtsp_comb_to_double_decker (CCtsp_lpgraph *g, CC_GCgraph *h, 929 double *x, CCtsp_lpcut_in *c, CCtsp_lpcut_in **d), 930 CCtsp_comb_to_star (CCtsp_lpgraph *g, CC_GCgraph *h, double *x, 931 CCtsp_lpcut_in *c, CCtsp_lpcut_in **d), 932 CCtsp_test_pure_simple_cliquetree (int ncount, CCtsp_lpcut_in *c, 933 int *yes_no), 934 CCtsp_comb_to_cliquetree (CCtsp_lpgraph *g, CC_GCgraph *h, double *x, 935 CCtsp_lpcut_in *c, CCtsp_lpcut_in **d), 936 CCtsp_comb_handling (CCtsp_lpgraph *g, CC_GCgraph *h, double *x, 937 CCtsp_lpcut_in *c, CCtsp_lpcut_in **d); 938 939 940 941 /****************************************************************************/ 942 /* */ 943 /* ex_price.c */ 944 /* */ 945 /****************************************************************************/ 946 947 948 int 949 CCtsp_exact_price (CCtsp_lp *lp, CCbigguy *bound, int complete_price, 950 int phase1, int silent), 951 CCtsp_edge_elimination (CCtsp_lp *lp, int eliminate_sparse, int silent), 952 CCtsp_exact_dual (CCtsp_lp *lp), 953 CCtsp_verify_infeasible_lp (CCtsp_lp *lp, int *yesno, int silent), 954 CCtsp_verify_lp_prune (CCtsp_lp *lp, int *yesno, int silent); 955 956 void 957 CCtsp_free_bigdual (CCtsp_bigdual **d); 958 959 960 /****************************************************************************/ 961 /* */ 962 /* generate.c */ 963 /* */ 964 /****************************************************************************/ 965 966 967 #define CCtsp_PRICE_COMPLETE_GRAPH -1 968 #define CCtsp_GEN_PRICE_EPSILON 0.0001 /* 0.0000001 */ 969 #define CCtsp_GEN_USE_ADJ 50 /* Cutoff for using explicit adj list */ 970 971 972 void 973 CCtsp_free_edgegenerator (CCtsp_edgegenerator *eg); 974 975 int 976 CCtsp_init_edgegenerator (CCtsp_edgegenerator *eg, int ncount, 977 CCdatagroup *dg, CCtsp_genadj *adj, int nneighbors, 978 int silent, CCrandstate *rstate), 979 CCtsp_reset_edgegenerator (CCtsp_edgegenerator *eg, double *node_piest, 980 int silent), 981 CCtsp_generate_edges (CCtsp_edgegenerator *eg, int nwant, int *pngot, 982 int *elist, int *elen, int *finished, int silent, CCrandstate *rstate), 983 CCtsp_edgelist_to_genadj (int ncount, int ecount, int *elist, int *elen, 984 CCtsp_genadj **adj, CCtsp_genadjobj **adjobjspace); 985 986 987 988 /****************************************************************************/ 989 /* */ 990 /* growcomb.c */ 991 /* */ 992 /****************************************************************************/ 993 994 995 int 996 CCtsp_edge_comb_grower (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 997 int ecount, int *elist, double *x, CCtsp_tighten_info *stats); 998 999 1000 1001 /****************************************************************************/ 1002 /* */ 1003 /* prclique.c */ 1004 /* */ 1005 /****************************************************************************/ 1006 1007 1008 int 1009 CCtsp_pr_cliquetree (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 1010 int ecount, int *elist, double *x, CCtsp_tighten_info *stats); 1011 1012 1013 1014 /****************************************************************************/ 1015 /* */ 1016 /* prob_io.c */ 1017 /* */ 1018 /****************************************************************************/ 1019 1020 #define CCtsp_PROB_FILE_NAME_LEN 128 1021 1022 #define CCtsp_Pdelete 'D' 1023 #define CCtsp_Pread 'R' 1024 #define CCtsp_Pwrite 'W' 1025 #define CCtsp_Pmaster 'M' 1026 #define CCtsp_Pexit 'X' 1027 #define CCtsp_Pcuts 'c' 1028 #define CCtsp_Pdual 'd' 1029 #define CCtsp_Pedges 'e' 1030 #define CCtsp_Pfixed 'f' 1031 #define CCtsp_Pfull 'g' 1032 #define CCtsp_Pheader 'h' 1033 #define CCtsp_Phistory 'i' 1034 #define CCtsp_Ptour 't' 1035 #define CCtsp_Pwarmstart 'w' 1036 1037 typedef struct CCtsp_PROB_FILE { 1038 CC_SFILE *f; 1039 int type; 1040 char name[CCtsp_PROB_FILE_NAME_LEN]; 1041 int id; 1042 int parent; 1043 double ub; 1044 double lb; 1045 CCbigguy exactlb; 1046 int nnodes; 1047 int child0; 1048 int child1; 1049 int real; /* Set to 1 when we know this is a real child */ 1050 int processed; 1051 int infeasible; 1052 struct { 1053 int dat; 1054 int edge; 1055 int fulladj; 1056 int cut; 1057 int tour; 1058 int basis; /* obsolete - replaced by warmstart */ 1059 int norms; /* obsolete - replaced by warmstart */ 1060 int fix; 1061 int exactdual; 1062 int history; 1063 int warmstart; 1064 } offsets; 1065 } CCtsp_PROB_FILE; 1066 1067 1068 CCtsp_PROB_FILE 1069 *CCtsp_prob_read (char *f, int n), 1070 *CCtsp_prob_read_name (char *f), 1071 *CCtsp_prob_write (char *f, int n), 1072 *CCtsp_prob_write_name (char *fname); 1073 1074 int 1075 CCtsp_prob_file_delete (char *f, int n), 1076 CCtsp_prob_getname (CCtsp_PROB_FILE *p, char *name), 1077 CCtsp_prob_getid (CCtsp_PROB_FILE *p, int *id), 1078 CCtsp_prob_getparent (CCtsp_PROB_FILE *p, int *parent), 1079 CCtsp_prob_getub (CCtsp_PROB_FILE *p, double *ub), 1080 CCtsp_prob_getlb (CCtsp_PROB_FILE *p, double *lb), 1081 CCtsp_prob_getexactlb (CCtsp_PROB_FILE *p, CCbigguy *lb), 1082 CCtsp_prob_getnnodes (CCtsp_PROB_FILE *p, int *nnodes), 1083 CCtsp_prob_getchildren (CCtsp_PROB_FILE *p, int *child0, int *child1), 1084 CCtsp_prob_getreal (CCtsp_PROB_FILE *p, int *real), 1085 CCtsp_prob_getprocessed (CCtsp_PROB_FILE *p, int *processed), 1086 CCtsp_prob_getinfeasible (CCtsp_PROB_FILE *p, int *infeasible), 1087 CCtsp_prob_gettour (CCtsp_PROB_FILE *p, int ncount, int **tour, int silent), 1088 CCtsp_prob_getedges (CCtsp_PROB_FILE *p, int ncount, int *nedges, 1089 int **elist, int **elen, int silent), 1090 CCtsp_prob_getcuts (CCtsp_PROB_FILE *p, int *ncount, CCtsp_lpcuts *cuts, 1091 int silent), 1092 CCtsp_prob_getwarmstart (CCtsp_PROB_FILE *p, CClp_warmstart **w, 1093 int silent), 1094 CCtsp_prob_getfulladj (CCtsp_PROB_FILE *p, int ncount, int *fullcount, 1095 CCtsp_genadj **adj, CCtsp_genadjobj **adjspace, int silent), 1096 CCtsp_prob_getfixed (CCtsp_PROB_FILE *p, int ncount, int *ecount, 1097 int **elist, int silent), 1098 CCtsp_prob_getexactdual (CCtsp_PROB_FILE *p, int ncount, 1099 CCtsp_bigdual **d, int silent), 1100 CCtsp_prob_gethistory (CCtsp_PROB_FILE *p, int *depth, 1101 CCtsp_branchobj **history, int silent), 1102 CCtsp_prob_rclose (CCtsp_PROB_FILE *p), 1103 CCtsp_prob_putname (CCtsp_PROB_FILE *p, char *name), 1104 CCtsp_prob_putid (CCtsp_PROB_FILE *p, int id), 1105 CCtsp_prob_putparent (CCtsp_PROB_FILE *p, int parent), 1106 CCtsp_prob_putub (CCtsp_PROB_FILE *p, double ub), 1107 CCtsp_prob_putlb (CCtsp_PROB_FILE *p, double lb), 1108 CCtsp_prob_putexactlb (CCtsp_PROB_FILE *p, CCbigguy lb), 1109 CCtsp_prob_putnnodes (CCtsp_PROB_FILE *p, int nnodes), 1110 CCtsp_prob_putchildren (CCtsp_PROB_FILE *p, int child0, int child1), 1111 CCtsp_prob_putreal (CCtsp_PROB_FILE *p, int real), 1112 CCtsp_prob_putprocessed (CCtsp_PROB_FILE *p, int processed), 1113 CCtsp_prob_putinfeasible (CCtsp_PROB_FILE *p, int infeasible), 1114 CCtsp_prob_puttour (CCtsp_PROB_FILE *p, int ncount, int *tour), 1115 CCtsp_prob_putedges (CCtsp_PROB_FILE *p, int ncount, int nedges, 1116 int *elist, int *elen), 1117 CCtsp_prob_putcuts (CCtsp_PROB_FILE *p, int ncount, CCtsp_lpcuts *cuts), 1118 CCtsp_prob_putwarmstart (CCtsp_PROB_FILE *p, CClp_warmstart *w), 1119 CCtsp_prob_putfulladj (CCtsp_PROB_FILE *p, int ncount, int fullcount, 1120 CCtsp_genadj *adj), 1121 CCtsp_prob_putfixed (CCtsp_PROB_FILE *p, int ncount, int ecount, 1122 int *elist), 1123 CCtsp_prob_putexactdual (CCtsp_PROB_FILE *p, CCtsp_bigdual *d, int ncount), 1124 CCtsp_prob_puthistory (CCtsp_PROB_FILE *p, int depth, 1125 CCtsp_branchobj *history), 1126 CCtsp_prob_wclose (CCtsp_PROB_FILE *p), 1127 CCtsp_prob_copy_section (CCtsp_PROB_FILE *f, CCtsp_PROB_FILE *t, 1128 char section, int silent); 1129 1130 char 1131 *CCtsp_problabel (const char *probloc); 1132 1133 #ifdef CC_NETREADY 1134 CCtsp_PROB_FILE 1135 *CCtsp_prob_read_remote (char *hname, char *pname, int n), 1136 *CCtsp_prob_write_remote (char *hname, char *pname, int n), 1137 *CCtsp_prob_server (CC_SFILE *s); 1138 1139 int 1140 CCtsp_prob_delete_remote (char *hname, char *pname, int n); 1141 #endif /* CC_NETREADY */ 1142 1143 1144 1145 1146 /****************************************************************************/ 1147 /* */ 1148 /* qsparse.c */ 1149 /* */ 1150 /****************************************************************************/ 1151 1152 typedef struct CCtsp_qsparsegroup { 1153 CCdheap *add_queue; /* An empty heap will be maintained */ 1154 CCdheap *sub_queue; /* An empty heap will be maintained */ 1155 int *count_m1; /* The array will be maintained at 0 */ 1156 int *count_non0; /* The array will be maintained at 0 */ 1157 int *count_1; /* The array will be maintained at 0 */ 1158 int *on_add_queue; /* The array will be maintained at 0 */ 1159 int *on_sub_queue; /* The array will be maintained at 0 */ 1160 int *mults; /* The array will be maintained at 0 */ 1161 } CCtsp_qsparsegroup; 1162 1163 1164 void 1165 CCtsp_free_qsparsify (CCtsp_qsparsegroup **pqs); 1166 1167 int 1168 CCtsp_qsparsify (CCtsp_qsparsegroup **pqs, struct CCtsp_lpgraph *g, 1169 int *pnzlist, int *scount, struct CCtsp_sparser **slist, 1170 int *savedcount); 1171 1172 1173 /****************************************************************************/ 1174 /* */ 1175 /* skeleton.c */ 1176 /* */ 1177 /****************************************************************************/ 1178 1179 1180 int 1181 CCtsp_copy_skeleton (CCtsp_skeleton *old, CCtsp_skeleton *new), 1182 CCtsp_construct_skeleton (CCtsp_lpcut_in *c, int nodecount), 1183 CCtsp_read_skeleton (CC_SFILE *f, CCtsp_skeleton *skel, int ncount), 1184 CCtsp_write_skeleton (CC_SFILE *f, CCtsp_skeleton *skel, int ncount); 1185 1186 void 1187 CCtsp_init_skeleton (CCtsp_skeleton *skel), 1188 CCtsp_free_skeleton (CCtsp_skeleton *skel), 1189 CCtsp_compare_skeletons (CCtsp_skeleton *a, CCtsp_skeleton *b, int *diff); 1190 1191 1192 1193 /****************************************************************************/ 1194 /* */ 1195 /* teething.c */ 1196 /* */ 1197 /****************************************************************************/ 1198 1199 1200 int 1201 CCtsp_teething (CCtsp_lpgraph *g, double *x, CCtsp_lpcut_in *cut, 1202 CCtsp_lpcut_in **newcut), 1203 CCtsp_teething_list (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *handle, 1204 int nbig, CCtsp_lpclique **bigteeth, CCtsp_lpcut_in **newcut); 1205 1206 1207 1208 /****************************************************************************/ 1209 /* */ 1210 /* tighten.c */ 1211 /* */ 1212 /****************************************************************************/ 1213 1214 1215 int 1216 CCtsp_tighten_lpcut_in (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, double *x, 1217 CCtsp_lpcut_in *d, CCtsp_tighten_info *stats, double *pimprove), 1218 CCtsp_tighten_lpcut (CCtsp_lpgraph *g, CCtsp_lpclique *cliques, 1219 CCtsp_lpcut *c, double *x, CCtsp_lpcut_in *d, 1220 CCtsp_tighten_info *stats, double *pimprove); 1221 1222 void 1223 CCtsp_init_tighten_info (CCtsp_tighten_info *stats), 1224 CCtsp_print_tighten_info (CCtsp_tighten_info *stats); 1225 1226 1227 /****************************************************************************/ 1228 /* */ 1229 /* tsp_lp.c */ 1230 /* */ 1231 /****************************************************************************/ 1232 1233 1234 int 1235 CCtsp_bb_init_lp (CCtsp_lp **lp, char *probname, int probnum, int ncount, 1236 CCdatagroup *dat, int *ptour, double initial_ub, CCtsp_lpcuts *pool, 1237 int silent, CCrandstate *rstate), 1238 CCtsp_init_lp (CCtsp_lp **lp, char *probname, int probnum, 1239 char *probfilename, int ncount, CCdatagroup *dat, int ecount, 1240 int *elist, int *elen, int excount, int *exlist, int *exlen, 1241 int exvalid, int *ptour, double initial_ub, CCtsp_lpcuts *pool, 1242 CCtsp_lpcuts *dominopool, int silent, CCrandstate *rstate), 1243 CCtsp_build_lpgraph (CCtsp_lpgraph *g, int ncount, int ecount, 1244 int *elist, int *elen), 1245 CCtsp_build_lpadj (CCtsp_lpgraph *g, int estart, int eend), 1246 CCtsp_find_edge (CCtsp_lpgraph *g, int from, int to), 1247 CCtsp_inspect_full_edges (CCtsp_lp *lp), 1248 CCtsp_resparsify_lp (CCtsp_lp *lp, int silent), 1249 CCtsp_lpcut_nzlist (CCtsp_lpgraph *g, CCtsp_lpcut *c, 1250 CCtsp_lpclique *cliques, CCtsp_lpdomino *dominos, int do_mods), 1251 CCtsp_update_result (CCtsp_lp *lp), 1252 CCtsp_get_lp_result (CCtsp_lp *lp, double *lb, double *ub, int *ecount, 1253 int **elist, double **x, double **rc, double **node_pi, 1254 double **cut_pi), 1255 CCtsp_lpcut_in_nzlist (CCtsp_lpgraph *g, CCtsp_lpcut_in *c), 1256 CCtsp_process_cuts (CCtsp_lp *lp, int *pnadded, int tighten, 1257 int silent, CCrandstate *rstate), 1258 CCtsp_infeas_recover (CCtsp_lp *lp, int silent, CCrandstate *rstate), 1259 CCtsp_add_cut (CCtsp_lp *lp, CCtsp_lpcut_in *d, CCtsp_lprow *cr), 1260 CCtsp_add_nzlist_to_lp (CCtsp_lp *lp, int nzlist, int rhs, char sense, 1261 CCtsp_lprow *cr), 1262 CCtsp_addbad_variables (CCtsp_lp *lp, CCtsp_edgegenerator *eg, 1263 double *ppenalty, int *pnadded, double rcthresh, 1264 double maxpenalty, int phase1, int *feasible, int silent, 1265 CCrandstate *rstate), 1266 CCtsp_eliminate_variables (CCtsp_lp *lp, int eliminate_sparse, int silent), 1267 CCtsp_add_vars_to_lp (CCtsp_lp *lp, CCtsp_predge *prlist, int n), 1268 CCtsp_add_multiple_rows (CCtsp_lp *lp, CCtsp_lprow *cr), 1269 CCtsp_delete_cut (CCtsp_lp *lp, int i), 1270 CCtsp_reduced_cost_nearest (CCtsp_lp *lp, int k, int *ecount, int **elist, 1271 double **elen, int sparse), 1272 CCtsp_write_probfile_sav (CCtsp_lp *lp), 1273 CCtsp_write_probfile_id (CCtsp_lp *lp), 1274 CCtsp_write_probroot_id (char *probloc, CCtsp_lp *lp), 1275 CCtsp_write_probleaf_id (CCtsp_lp *lp), 1276 CCtsp_read_probfile (CCtsp_lp *lp, char *fname, char *probloc, 1277 int *ncount, int silent), 1278 CCtsp_read_probfile_id (CCtsp_lp *lp, char *fname, int id, int *ncount, 1279 int silent), 1280 CCtsp_dump_rc_nearest (CCtsp_lp *lp, int k, char *fname, int sparse), 1281 CCtsp_dump_x (CCtsp_lp *lp, char *fname), 1282 CCtsp_depot_valid (CCtsp_lp *lp, int ndepot, int *yesno); 1283 1284 double 1285 CCtsp_cutprice (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, double *x); 1286 1287 void 1288 CCtsp_init_tsp_lpcuts_struct (CCtsp_lpcuts *c), 1289 CCtsp_init_tsp_lp_struct (CCtsp_lp *lp), 1290 CCtsp_free_tsp_lp_struct (CCtsp_lp **lp), 1291 CCtsp_init_lpgraph_struct (CCtsp_lpgraph *g), 1292 CCtsp_free_lpgraph (CCtsp_lpgraph *g), 1293 CCtsp_init_statistics (CCtsp_statistics *stats), 1294 CCtsp_output_statistics (CCtsp_statistics *stats), 1295 CCtsp_add_cuts_to_queue (CCtsp_lp *lp, CCtsp_lpcut_in **c), 1296 CCtsp_init_lprow (CCtsp_lprow *cr), 1297 CCtsp_free_lprow (CCtsp_lprow *cr); 1298 1299 1300 /****************************************************************************/ 1301 /* */ 1302 /* tsp_lp.c */ 1303 /* */ 1304 /****************************************************************************/ 1305 1306 int 1307 CCtsp_solve_sparse (int ncount, int ecount, int *elist, int *elen, 1308 int *in_tour, int *out_tour, double *in_val, double *optval, 1309 int *success, int *foundtour, char *name, double *timebound, 1310 int *hit_timebound, int silent, CCrandstate *rstate), 1311 CCtsp_solve_dat (int ncount, CCdatagroup *indat, int *in_tour, 1312 int *out_tour, double *in_val, double *optval, int *success, 1313 int *foundtour, char *name, double *timebound, int *hit_timebound, 1314 int silent, CCrandstate *rstate); 1315 1316 1317 1318 /****************************************************************************/ 1319 /* */ 1320 /* xtour.c */ 1321 /* */ 1322 /****************************************************************************/ 1323 1324 1325 int 1326 CCtsp_x_greedy_tour (CCdatagroup *dat, int ncount, int ecount, int *elist, 1327 double *x, int *cyc, double *val, int silent), 1328 CCtsp_x_greedy_tour_lk (CCdatagroup *dat, int ncount, int ecount, 1329 int *elist, double *x, int *cyc, double *val, int silent, 1330 CCrandstate *rstate); 1331 1332 1333 /****************************************************************************/ 1334 /* */ 1335 /* domboss.c */ 1336 /* */ 1337 /****************************************************************************/ 1338 1339 #define CCtsp_DOMINO_WORK 'A' 1340 #define CCtsp_DOMINO_GRAPH 'G' 1341 #define CCtsp_DOMINO_NO 'N' 1342 #define CCtsp_DOMINO_RECEIVE 'R' 1343 #define CCtsp_DOMINO_SEND 'S' 1344 #define CCtsp_DOMINO_WAIT 'W' 1345 #define CCtsp_DOMINO_YES 'Y' 1346 #define CCtsp_DOMINO_EXIT 'X' 1347 1348 #endif /* __TSP_H */ 1349