1 /***************************************************************************/ 2 /***************************************************************************/ 3 /* */ 4 /* PROTOTYPES FOR FILES IN CUT */ 5 /* */ 6 /***************************************************************************/ 7 /***************************************************************************/ 8 9 10 #ifndef __TSP_H 11 #define __TSP_H 12 13 #include "util.h" 14 #include "edgegen.h" 15 #include "bigguy.h" 16 #include "lp.h" 17 #include "cut.h" 18 #include "kdtree.h" 19 20 /*************** Tolerances for the LP and Cutting routines ***************/ 21 22 #define CCtsp_MIN_VIOL (0.00001) /* min violation for cut to be added to lp */ 23 #define CCtsp_CUTS_NEXT_TOL (0.0001) /* to try next level */ 24 #define CCtsp_CUTS_NEXT_ROUND (0.00000001) /* if improve is less, stop round */ 25 #define CCtsp_PRICE_RCTHRESH (-0.00001) /* to add a bad edge */ 26 #define CCtsp_PRICE_MAXPENALTY (0.49) /* penalty permitted in addbad */ 27 #define CCtsp_PHASE1_RCTHRESH (-0.000000001) 28 #define CCtsp_PHASE1_MAXPENALTY (0.00000001) 29 #define CCtsp_EDGE_LIFE (1000000) /* 200 */ /* Large for subtour runs */ 30 #define CCtsp_CUT_LIFE (50) 31 #define CCtsp_CUT_BATCH (250) /* number of new cuts before lp optimize */ 32 #define CCtsp_STORE_BATCH (50) /* number of new cuts before lp addrows */ 33 #define CCtsp_INTTOL (0.0001) /* used to check if lp soln is integral */ 34 35 /************************** Branching Strategies ************************/ 36 37 #define CCtsp_BRANCH_MIDDLE 1 38 #define CCtsp_BRANCH_STRONG 2 39 40 /*************************************************************************/ 41 42 #define CCtsp_LP_MAXDOUBLE 1e30 43 44 #define CCtsp_CUTRHS(c) (3*(c)->cliquecount - (c)->handlecount - 1) 45 46 typedef struct CCtsp_lpnode { 47 int deg; 48 int mark; 49 struct CCtsp_lpadj *adj; 50 } CCtsp_lpnode; 51 52 typedef struct CCtsp_lpedge { 53 int ends[2]; /* ends[0] should always be < ends[1] */ 54 int fixed; 55 int branch; /* < 0 means set to 0 and > 0 means set to 1 */ 56 int len; 57 int age; 58 int coef; /* should be maintained at zero */ 59 int coefnext; /* should be maintained at -2 */ 60 } CCtsp_lpedge; 61 62 typedef struct CCtsp_lpadj { 63 int to; 64 int edge; 65 } CCtsp_lpadj; 66 67 typedef struct CCtsp_lpgraph { 68 int ncount; 69 int espace; 70 int ecount; 71 int nodemarker; 72 CCtsp_lpnode *nodes; 73 CCtsp_lpedge *edges; 74 CCtsp_lpadj *adjspace; 75 int adjstart; 76 int adjend; 77 } CCtsp_lpgraph; 78 79 typedef struct CCtsp_predge { 80 int ends[2]; 81 int len; 82 double rc; 83 } CCtsp_predge; 84 85 typedef struct CCtsp_pricegroup { 86 int ncount; 87 int espace; 88 int ecount; 89 CCtsp_lpnode *nodes; 90 CCtsp_predge *edges; 91 int cliquecount; 92 struct CCtsp_lpclique *cliques; /* just a copy of the pointer */ 93 CCtsp_lpgraph *graph; /* pointer to the copy in a CCtsp_lp */ 94 CCtsp_lpadj *adjspace; 95 double *node_pi; 96 double *clique_pi; 97 double penalty; 98 } CCtsp_pricegroup; 99 100 typedef struct CCtsp_extraedge { 101 int ends[2]; 102 } CCtsp_extraedge; 103 104 typedef struct CCtsp_sparser { 105 unsigned int node : 24; 106 unsigned int mult : 8; 107 } CCtsp_sparser; 108 109 typedef struct CCtsp_segment { 110 int lo; 111 int hi; 112 } CCtsp_segment; 113 114 typedef struct CCtsp_lpclique { 115 int segcount; 116 struct CCtsp_segment *nodes; 117 int hashnext; 118 int refcount; 119 } CCtsp_lpclique; 120 121 #define CC_FOREACH_NODE_IN_CLIQUE(i,c,tmp) \ 122 for(tmp=0;tmp<(c).segcount;tmp++) \ 123 for(i=(c).nodes[tmp].lo;i<=(c).nodes[tmp].hi;i++) 124 125 #define CCtsp_NEWCUT_AGE (-1) 126 127 typedef struct CCtsp_lpcut { 128 int handlecount; 129 int cliquecount; 130 int modcount; 131 int age; 132 int rhs; 133 char sense; 134 char branch; 135 int *cliques; 136 struct CCtsp_sparser *mods; 137 } CCtsp_lpcut; 138 139 typedef struct CCtsp_lpcut_in { 140 int handlecount; 141 int cliquecount; 142 int rhs; 143 char sense; 144 char branch; 145 CCtsp_lpclique *cliques; 146 struct CCtsp_lpcut_in *next; 147 struct CCtsp_lpcut_in *prev; 148 } CCtsp_lpcut_in; 149 150 typedef struct CCtsp_lp_result { 151 double ub; 152 double lb; 153 int ecount; 154 int *elist; 155 double *x; 156 double *rc; 157 } CCtsp_lp_result; 158 159 typedef struct CCtsp_lpcuts { 160 int cutcount; 161 int cliqueend; 162 int cutspace; 163 int cliquespace; 164 int cliquehashsize; 165 int cliquefree; 166 int *cliquehash; 167 CCtsp_lpcut *cuts; 168 CCtsp_lpclique *cliques; 169 CCgenhash *cuthash; 170 char *tempcuthash; 171 int tempcuthashsize; 172 } CCtsp_lpcuts; 173 174 typedef struct CCtsp_bigdual { 175 int cutcount; 176 CCbigguy *node_pi; 177 CCbigguy *cut_pi; 178 } CCtsp_bigdual; 179 180 typedef struct CCtsp_tighten_info { 181 int ncall; 182 int nfail; 183 int nadd; 184 int nadd_tied; 185 int ndel; 186 int ndel_tied; 187 double add_delta; 188 double del_delta; 189 double time; 190 } CCtsp_tighten_info; 191 192 typedef struct CCtsp_branchobj { 193 int depth; 194 int rhs; 195 int ends[2]; 196 char sense; 197 CCtsp_lpclique *clique; 198 } CCtsp_branchobj; 199 200 typedef struct CCtsp_cutselect { 201 int cutpool; 202 int connect; 203 int segments; 204 int exactsubtour; 205 int tighten_lp; 206 int decker_lp; 207 int teething_lp; 208 int tighten_pool; 209 int decker_pool; 210 int teething_pool; 211 int maxchunksize; 212 int Xfastcuts; 213 int Xexactsubtours; 214 int Xslowcuts; 215 int consecutiveones; 216 int necklace; 217 int usetighten; /* set to 1 to tighten before cuts are added */ 218 int extra_connect; /* set to 1 to force a connected solution */ 219 double nexttol; 220 double roundtol; 221 } CCtsp_cutselect; 222 223 /* nodes are reordered to match compression tour */ 224 225 typedef struct CCtsp_genadj { 226 int deg; 227 struct CCtsp_genadjobj *list; 228 } CCtsp_genadj; 229 230 typedef struct CCtsp_genadjobj { 231 int end; 232 int len; 233 } CCtsp_genadjobj; 234 235 typedef struct CCtsp_edgegenerator { 236 double *node_piest; 237 struct CCdatagroup *dg; 238 int *supply; 239 CCkdtree *kdtree; 240 CCxnear *xnear; 241 struct CCtsp_xnorm_pricer *xprice; 242 CCtsp_genadjobj *adjobjspace; 243 CCtsp_genadj *adj; 244 int ncount; 245 int nneighbors; 246 int start; 247 int current; 248 int supplyhead; 249 int supplycount; 250 } CCtsp_edgegenerator; 251 252 typedef struct CCtsp_xnorm_pricer_val { 253 double val; 254 struct CCtsp_xnorm_pricer_val *next; 255 struct CCtsp_xnorm_pricer_val *prev; 256 int index; 257 } CCtsp_xnorm_pricer_val; 258 259 typedef struct CCtsp_xnorm_pricer { 260 CCdatagroup *dat; 261 double *pi; 262 int *order; 263 CCtsp_xnorm_pricer_val *xminuspi_space; 264 CCtsp_xnorm_pricer_val *xminuspi; 265 int *invxminuspi; 266 int ncount; 267 } CCtsp_xnorm_pricer; 268 269 typedef struct CCtsp_lp { 270 CCtsp_lpgraph graph; 271 CCtsp_lpcuts cuts; 272 CCtsp_lpcuts *pool; 273 CClp lp; 274 int *perm; 275 CCdatagroup *dat; 276 int fullcount; 277 struct CCtsp_genadj *fulladj; 278 struct CCtsp_genadjobj *fulladjspace; 279 int nfixededges; 280 int *fixededges; 281 struct CCtsp_qsparsegroup *sparsifier; 282 int edge_life; 283 int cut_life; 284 char *name; 285 int id; 286 int parent_id; 287 int root; 288 double upperbound; 289 double lowerbound; 290 CCbigguy exact_lowerbound; 291 CCtsp_bigdual *exact_dual; 292 int infeasible; 293 int full_edges_valid; 294 CClpbasis *basis; 295 CCtsp_lpcut_in cutqueue; /* dummy entry for doubly-linked 296 list */ 297 CCtsp_lp_result result; 298 CCtsp_tighten_info tighten_stats; 299 int branchdepth; 300 CCtsp_branchobj *branchhistory; 301 } CCtsp_lp; 302 303 typedef struct CCtsp_lprow { 304 int rowcnt; 305 int nzcnt; 306 char *sense; 307 double *rhs; 308 int *begin; /* offset into the array for start of row */ 309 int indexspace; 310 int *indices; /* the column indices of the row entries */ 311 int entryspace; 312 double *entries; /* the matrix entries */ 313 } CCtsp_lprow; 314 315 316 317 /***************************************************************************/ 318 /* */ 319 /* tsp_lp.c */ 320 /* */ 321 /***************************************************************************/ 322 323 #ifdef CC_PROTOTYPE_ANSI 324 325 int 326 CCtsp_cutting_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, int savelp), 327 CCtsp_subtour_loop (CCtsp_lp *lp), 328 CCtsp_pricing_loop (CCtsp_lp *lp, double *bnd), 329 CCtsp_init_cutselect (CCtsp_lp *lp, CCtsp_cutselect *s), 330 CCtsp_call_x_heuristic (CCtsp_lp *lp, double *val, int *outcyc), 331 CCtsp_bb_cutting (char *probname, int probnum, int ncount, 332 CCdatagroup *dat, int *ptour, double *upbound, CCtsp_lpcuts *pool, 333 CCtsp_cutselect *sel, double *val, int *prune, int *foundtour, 334 int *besttour), 335 CCtsp_init_lp (CCtsp_lp **lp, char *probname, int probnum, 336 char *probfilename, int ncount, CCdatagroup *dat, int ecount, 337 int *elist, int *elen, int excount, int *exlist, int *exlen, 338 int exvalid, int *ptour, double initial_ub, CCtsp_lpcuts *pool), 339 CCtsp_bb_init_lp (CCtsp_lp **lp, char *probname, int probnum, 340 int ncount, CCdatagroup *dat, int *ptour, double initial_ub, 341 CCtsp_lpcuts *pool), 342 CCtsp_get_lp_result (CCtsp_lp *lp, double *lb, double *ub, int *ecount, 343 int **elist, double **x, double **rc, double **node_pi, 344 double **cut_pi), 345 CCtsp_process_cuts (CCtsp_lp *lp, int *pnadded, int tighten), 346 CCtsp_add_cut_to_cutlist (CCtsp_lpcuts *cuts, CCtsp_lpcut *c), 347 CCtsp_add_cut (CCtsp_lp *lp, CCtsp_lpcut_in *d, CCtsp_lprow *cr), 348 CCtsp_lpcut_in_nzlist (CCtsp_lpgraph *g, CCtsp_lpcut_in *c), 349 CCtsp_add_nzlist_to_lp (CCtsp_lp *lp, int nzlist, int rhs, char sense, 350 CCtsp_lprow *cr), 351 CCtsp_add_vars_to_lp (CCtsp_lp *lp, CCtsp_predge *prlist, int n), 352 CCtsp_update_result (CCtsp_lp *lp), 353 CCtsp_infeas_recover (CCtsp_lp *lp), 354 CCtsp_test_cut_branch (CCtsp_lp *lp, CCtsp_lpclique *c, double *down, 355 double *up), 356 CCtsp_register_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c, 357 CCtsp_lpcut *new), 358 CCtsp_addbad_variables (CCtsp_lp *lp, struct CCtsp_edgegenerator *eg, 359 double *ppenalty, int *pnadded, double rcthresh, 360 double maxpenalty, int phase1, int *feasible), 361 CCtsp_eliminate_variables (CCtsp_lp *lp), 362 CCtsp_build_lpgraph (CCtsp_lpgraph *g, int ncount, int ecount, 363 int *elist, int *elen), 364 CCtsp_build_lpadj (CCtsp_lpgraph *g, int estart, int eend), 365 CCtsp_add_multiple_rows (CCtsp_lp *lp, CCtsp_lprow *cr), 366 CCtsp_delete_cut (CCtsp_lp *lp, int i), 367 CCtsp_find_edge (CCtsp_lpgraph *g, int from, int to), 368 CCtsp_find_branch (CCtsp_lp *lp, int nwant, int *ngot, 369 CCtsp_branchobj **bobj, double *val, int **cyc, int usecliques), 370 CCtsp_bb_find_branch (char *probname, int probnum, int ncount, 371 CCdatagroup *dat, int *ptour, double *upperbound, 372 CCtsp_lpcuts *pool, CCtsp_branchobj **b, int usecliques, 373 int *foundtour, int *besttour), 374 CCtsp_check_integral (CCtsp_lp *lp, double *val, int **cyc, int *yesno), 375 CCtsp_find_branch_edge (CCtsp_lp *lp, int *n0, int *n1, double *val, 376 int **cyc, int branchtype), 377 CCtsp_find_branch_cliques (CCtsp_lp *lp, int nwant, int *ngot, 378 CCtsp_lpclique **bcliques, double **bval), 379 CCtsp_execute_branch (CCtsp_lp *lp, CCtsp_branchobj *b), 380 CCtsp_execute_unbranch (CCtsp_lp *lp, CClpbasis *basis), 381 CCtsp_splitprob (CCtsp_lp *lp, CCtsp_branchobj *b, int child0, int child1), 382 CCtsp_bb_splitprob (char *probname, int probnum, int ncount, 383 CCdatagroup *dat, int *ptour, double initial_ub, CCtsp_lpcuts *pool, 384 CCtsp_branchobj *b, int child0, int child1, double *val0, 385 double *val1, int *prune0, int *prune1), 386 CCtsp_dumptour (int ncount, CCdatagroup *dat, int *perm, char *probname, 387 int *tour), 388 CCtsp_add_branchhistory_to_lp (CCtsp_lp *lp), 389 CCtsp_easy_dfs_brancher (CCtsp_lp *lp, CCtsp_cutselect *sel, int depth, 390 double *upbound, int *bbcount, int usecliques, int *besttour), 391 CCtsp_bfs_brancher (char *probname, int id, double lowerbound, 392 CCtsp_cutselect *sel, double *upbound, int *bbcount, int usecliques, 393 CCdatagroup *mydat, int *ptour, CCtsp_lpcuts *pool, int ncount, 394 int *besttour), 395 CCtsp_do_interactive_branch (CCtsp_lp *lp), 396 CCtsp_inspect_full_edges (CCtsp_lp *lp), 397 CCtsp_read_probfile (CCtsp_lp *lp, char *fname, int ncount), 398 CCtsp_read_probfile_id (CCtsp_lp *lp, char *fname, int id, int ncount), 399 CCtsp_write_probfile_sav (CCtsp_lp *lp), 400 CCtsp_write_probfile_id (CCtsp_lp *lp), 401 CCtsp_dump_x (CCtsp_lp *lp, char *fname), 402 CCtsp_exact_price (CCtsp_lp *lp, CCbigguy *bound, int phase1), 403 CCtsp_edge_elimination (CCtsp_lp *lp), 404 CCtsp_exact_dual (CCtsp_lp *lp), 405 CCtsp_verify_infeasible_lp (CCtsp_lp *lp, int *yesno), 406 CCtsp_verify_lp_prune (CCtsp_lp *lp, int *yesno), 407 CCtsp_tighten_lpcut_in (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, 408 double *x, CCtsp_lpcut_in *d, CCtsp_tighten_info *stats, 409 double *pimprove), 410 CCtsp_tighten_lpcut (CCtsp_lpgraph *g, CCtsp_lpclique *cliques, 411 CCtsp_lpcut *c, double *x, CCtsp_lpcut_in *d, 412 CCtsp_tighten_info *stats, double *pimprove), 413 CCtsp_test_pure_comb (int ncount, CCtsp_lpcut_in *c, int *yes_no, 414 int *handle), 415 CCtsp_test_pseudocomb (int ncount, CCtsp_lpcut_in *c, int handle, 416 int *yes_no), 417 CCtsp_test_teeth_disjoint (int ncount, CCtsp_lpcut_in *c, int handle, 418 int *yes_no), 419 CCtsp_find_pure_handle (int ncount, CCtsp_lpcut_in *c, int *handle), 420 CCtsp_comb_to_double_decker (CCtsp_lpgraph *g, double *x, 421 CCtsp_lpcut_in *c, CCtsp_lpcut_in **d), 422 CCtsp_teething (CCtsp_lpgraph *g, double *x, CCtsp_lpcut_in *cut, 423 CCtsp_lpcut_in **newcut), 424 CCtsp_init_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts **pool), 425 CCtsp_write_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts *pool), 426 CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts, 427 int *cutcount, int ncount, int ecount, int *elist, double *x), 428 CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques, 429 int *cliquecount, int ncount, int ecount, int *elist, double *x, 430 double maxdelta, int maxcliques, double **cliquevals), 431 CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques, 432 int *cliquecount, int ncount, int ecount, int *elist, double *x, 433 int nwant, double **cliquevals), 434 CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts, 435 CCtsp_lpcut *c), 436 CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool, CCtsp_lpcut_in *cut), 437 CCtsp_display_cutpool (CCtsp_lpcuts *pool), 438 CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount, int *elist, 439 double *x, double *cutval), 440 CCtsp_clique_to_array (CCtsp_lpclique *c, int **ar, int *count), 441 CCtsp_clique_delta (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *c, 442 double *delta), 443 CCtsp_x_greedy_tour (CCdatagroup *dat, int ncount, int ecount, int *elist, 444 double *x, int *cyc, double *val), 445 CCtsp_x_greedy_tour_lk (CCdatagroup *dat, int ncount, int ecount, 446 int *elist, double *x, int *cyc, double *val); 447 448 void 449 CCtsp_init_tsp_lp_struct (CCtsp_lp *lp), 450 CCtsp_free_tsp_lp_struct (CCtsp_lp **lp), 451 CCtsp_add_cuts_to_queue (CCtsp_lp *lp, CCtsp_lpcut_in **c), 452 CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts *cuts, int ind), 453 CCtsp_init_lprow (CCtsp_lprow *cr), 454 CCtsp_free_lprow (CCtsp_lprow *cr), 455 CCtsp_unregister_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut *c), 456 CCtsp_free_cutpool (CCtsp_lpcuts **pool), 457 CCtsp_init_lpgraph_struct (CCtsp_lpgraph *g), 458 CCtsp_free_lpgraph (CCtsp_lpgraph *g), 459 CCtsp_free_lpcut_in (CCtsp_lpcut_in *c), 460 CCtsp_free_lpclique (CCtsp_lpclique *c), 461 CCtsp_free_bigdual (CCtsp_bigdual **d), 462 CCtsp_init_branchobj (CCtsp_branchobj *b), 463 CCtsp_free_branchobj (CCtsp_branchobj *b), 464 CCtsp_print_branchhistory (CCtsp_lp *lp), 465 CCtsp_init_tighten_info (CCtsp_tighten_info *stats), 466 CCtsp_print_tighten_info (CCtsp_tighten_info *stats), 467 CCtsp_mark_clique (CCtsp_lpclique *c, int *marks, int marker), 468 CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpclique *c, 469 int *marks, int marker), 470 CCtsp_mark_cut (CCtsp_lpcut_in *c, int *marks, int marker), 471 CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, 472 int *marks, int marker), 473 CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph *g, CCtsp_lpclique *c, 474 double *marks, double marker), 475 CCtsp_is_clique_marked (CCtsp_lpclique *c, int *marks, int marker, 476 int *yes_no), 477 CCtsp_clique_count (CCtsp_lpclique *c, int *count); 478 479 480 double 481 CCtsp_cutprice (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, double *x); 482 483 #else 484 485 int 486 CCtsp_cutting_loop (), 487 CCtsp_subtour_loop (), 488 CCtsp_pricing_loop (), 489 CCtsp_init_cutselect (), 490 CCtsp_call_x_heuristic (), 491 CCtsp_bb_cutting (), 492 CCtsp_init_lp (), 493 CCtsp_bb_init_lp (), 494 CCtsp_get_lp_result (), 495 CCtsp_process_cuts (), 496 CCtsp_add_cut_to_cutlist (), 497 CCtsp_add_cut (), 498 CCtsp_lpcut_in_nzlist (), 499 CCtsp_add_nzlist_to_lp (), 500 CCtsp_add_vars_to_lp (), 501 CCtsp_update_result (), 502 CCtsp_infeas_recover (), 503 CCtsp_test_cut_branch (), 504 CCtsp_register_cliques (), 505 CCtsp_addbad_variables (), 506 CCtsp_eliminate_variables (), 507 CCtsp_build_lpgraph (), 508 CCtsp_build_lpadj (), 509 CCtsp_add_multiple_rows (), 510 CCtsp_delete_cut (), 511 CCtsp_find_edge (), 512 CCtsp_find_branch (), 513 CCtsp_bb_find_branch (), 514 CCtsp_check_integral (), 515 CCtsp_find_branch_edge (), 516 CCtsp_find_branch_cliques (), 517 CCtsp_execute_branch (), 518 CCtsp_execute_unbranch (), 519 CCtsp_splitprob (), 520 CCtsp_bb_splitprob (), 521 CCtsp_dumptour (), 522 CCtsp_add_branchhistory_to_lp (), 523 CCtsp_easy_dfs_brancher (), 524 CCtsp_bfs_brancher (), 525 CCtsp_do_interactive_branch (), 526 CCtsp_inspect_full_edges (), 527 CCtsp_read_probfile (), 528 CCtsp_read_probfile_id (), 529 CCtsp_write_probfile_sav (), 530 CCtsp_write_probfile_id (), 531 CCtsp_dump_x (), 532 CCtsp_exact_price (), 533 CCtsp_edge_elimination (), 534 CCtsp_exact_dual (), 535 CCtsp_verify_infeasible_lp (), 536 CCtsp_verify_lp_prune (), 537 CCtsp_tighten_lpcut_in (), 538 CCtsp_tighten_lpcut (), 539 CCtsp_test_pure_comb (), 540 CCtsp_test_pseudocomb (), 541 CCtsp_test_teeth_disjoint (), 542 CCtsp_find_pure_handle (), 543 CCtsp_comb_to_double_decker (), 544 CCtsp_teething (), 545 CCtsp_init_cutpool (), 546 CCtsp_write_cutpool (), 547 CCtsp_search_cutpool (), 548 CCtsp_search_cutpool_cliques (), 549 CCtsp_branch_cutpool_cliques (), 550 CCtsp_add_to_cutpool (), 551 CCtsp_add_to_cutpool_lpcut_in (), 552 CCtsp_display_cutpool (), 553 CCtsp_price_cuts (), 554 CCtsp_clique_to_array (), 555 CCtsp_clique_delta (), 556 CCtsp_x_greedy_tour (), 557 CCtsp_x_greedy_tour_lk (); 558 559 void 560 CCtsp_init_tsp_lp_struct (), 561 CCtsp_free_tsp_lp_struct (), 562 CCtsp_add_cuts_to_queue (), 563 CCtsp_delete_cut_from_cutlist (), 564 CCtsp_init_lprow (), 565 CCtsp_free_lprow (), 566 CCtsp_unregister_cliques (), 567 CCtsp_free_cutpool (), 568 CCtsp_init_lpgraph_struct (), 569 CCtsp_free_lpgraph (), 570 CCtsp_free_lpcut_in (), 571 CCtsp_free_lpclique (), 572 CCtsp_free_bigdual (), 573 CCtsp_init_branchobj (), 574 CCtsp_free_branchobj (), 575 CCtsp_print_branchhistory (), 576 CCtsp_init_tighten_info (), 577 CCtsp_print_tighten_info (), 578 CCtsp_mark_clique (), 579 CCtsp_mark_clique_and_neighbors (), 580 CCtsp_mark_cut (), 581 CCtsp_mark_cut_and_neighbors (), 582 CCtsp_mark_clique_and_neighbors_double (), 583 CCtsp_is_clique_marked (), 584 CCtsp_clique_count (); 585 586 587 double 588 CCtsp_cutprice (); 589 590 #endif 591 592 /***************************************************************************/ 593 /* */ 594 /* cliqhash.c */ 595 /* */ 596 /***************************************************************************/ 597 598 #ifdef CC_PROTOTYPE_ANSI 599 600 int 601 CCtsp_init_cliquehash (CCtsp_lpcuts *cuts, int size), 602 CCtsp_register_clique (CCtsp_lpcuts *cuts, CCtsp_lpclique *c); 603 604 void 605 CCtsp_free_cliquehash (CCtsp_lpcuts *cuts), 606 CCtsp_unregister_clique (CCtsp_lpcuts *cuts, int c); 607 608 #else 609 610 int 611 CCtsp_init_cliquehash (), 612 CCtsp_register_clique (); 613 614 void 615 CCtsp_free_cliquehash (), 616 CCtsp_unregister_clique (); 617 618 #endif 619 620 621 622 /***************************************************************************/ 623 /* */ 624 /* cutcall.c */ 625 /* */ 626 /***************************************************************************/ 627 628 typedef struct cutinfo { 629 CC_SRKexpinfo expand; 630 CCtsp_lpcut_in **clist; 631 CCtsp_lpcut_in *current; 632 int *cutcount; 633 } cutinfo; 634 635 #ifdef CC_PROTOTYPE_ANSI 636 637 int 638 CCtsp_connect_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 639 int ecount, int *elist, double *x), 640 CCtsp_segment_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 641 int ecount, int *elist, double *x), 642 CCtsp_exact_subtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 643 int ecount, int *elist, double *x), 644 CCtsp_tighten_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 645 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 646 int *elist, double *x, double testtol, int maxcuts), 647 CCtsp_double_decker_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 648 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 649 int *elist, double *x, double testtol, int maxcuts), 650 CCtsp_teething_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 651 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 652 int *elist, double *x, double testtol, int maxcuts), 653 CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new), 654 CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b), 655 CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, int acount), 656 CCtsp_array_to_lpclique (int *ar, int acount, CCtsp_lpclique *cliq), 657 CCtsp_seglist_to_lpclique (int nseg, int *list, CCtsp_lpclique *cliq), 658 CCtsp_add_node_to_lpclique (CCtsp_lpclique *cin, CCtsp_lpclique *cout, 659 int n), 660 CCtsp_delete_node_from_lpclique (CCtsp_lpclique *cin, 661 CCtsp_lpclique *cout, int n), 662 CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c, 663 CCtsp_lpcut_in *new), 664 CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new), 665 CCtsp_file_cuts (char *cutfile, CCtsp_lpcut_in **cuts, int *cutcount, 666 int ncount, int *tour), 667 CCtsp_file_cuts_write (char *cutfile, CCtsp_lpcuts *cuts, int *tour), 668 CCtsp_buildcut_begin (cutinfo *cuts, int init_cliquecount), 669 CCtsp_buildcut_addclique (cutinfo *cuts, int *arr, int size, int handle); 670 671 void 672 CCtsp_init_lpcut_in (CCtsp_lpcut_in *c), 673 CCtsp_init_lpclique (CCtsp_lpclique *c), 674 CCtsp_print_lpcut_in (CCtsp_lpcut_in *c), 675 CCtsp_print_lpclique (CCtsp_lpclique *c), 676 CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b, int *diff), 677 CCtsp_buildcut_abort (cutinfo *cuts), 678 CCtsp_buildcut_finish (cutinfo *cuts, int rhs); 679 680 #else 681 682 int 683 CCtsp_connect_cuts (), 684 CCtsp_segment_cuts (), 685 CCtsp_exact_subtours (), 686 CCtsp_tighten_lp (), 687 CCtsp_double_decker_lp (), 688 CCtsp_teething_lp (), 689 CCtsp_copy_lpcut_in (), 690 CCtsp_segment_to_subtour (), 691 CCtsp_array_to_subtour (), 692 CCtsp_array_to_lpclique (), 693 CCtsp_seglist_to_lpclique (), 694 CCtsp_add_node_to_lpclique (), 695 CCtsp_delete_node_from_lpclique (), 696 CCtsp_lpcut_to_lpcut_in (), 697 CCtsp_copy_lpclique (), 698 CCtsp_file_cuts (), 699 CCtsp_file_cuts_write (), 700 CCtsp_buildcut_begin (), 701 CCtsp_buildcut_addclique (); 702 703 void 704 CCtsp_init_lpcut_in (), 705 CCtsp_init_lpclique (), 706 CCtsp_print_lpcut_in (), 707 CCtsp_print_lpclique (), 708 CCtsp_lpclique_compare (), 709 CCtsp_buildcut_abort (), 710 CCtsp_buildcut_finish (); 711 712 #endif 713 714 715 716 /***************************************************************************/ 717 /* */ 718 /* edgemap.c */ 719 /* */ 720 /***************************************************************************/ 721 722 typedef struct CCtsp_edgeinf { 723 int ends[2]; 724 int val; 725 struct CCtsp_edgeinf *next; 726 } CCtsp_edgeinf; 727 728 typedef struct CCtsp_edgehash { 729 struct CCtsp_edgeinf **table; 730 unsigned int size; 731 unsigned int mult; 732 } CCtsp_edgehash; 733 734 735 #ifdef CC_PROTOTYPE_ANSI 736 737 int 738 CCtsp_edgehash_init (CCtsp_edgehash *h, int size), 739 CCtsp_edgehash_add (CCtsp_edgehash *h, int end1, int end2, int val), 740 CCtsp_edgehash_del (CCtsp_edgehash *h, int end1, int end2), 741 CCtsp_edgehash_find (CCtsp_edgehash *h, int end1, int end2); 742 743 void 744 CCtsp_edgehash_delall (CCtsp_edgehash *h), 745 CCtsp_edgehash_free (CCtsp_edgehash *h); 746 747 #else 748 749 int 750 CCtsp_edgehash_init (), 751 CCtsp_edgehash_add (), 752 CCtsp_edgehash_del (), 753 CCtsp_edgehash_find (); 754 755 void 756 CCtsp_edgehash_delall (), 757 CCtsp_edgehash_free (); 758 759 #endif 760 761 762 /***************************************************************************/ 763 /* */ 764 /* generate.c */ 765 /* */ 766 /***************************************************************************/ 767 768 #define CCtsp_PRICE_COMPLETE_GRAPH -1 769 #define CCtsp_GEN_PRICE_EPSILON 0.0001 /* 0.0000001 */ 770 #define CCtsp_GEN_USE_ADJ 50 /* Cutoff for using explicit adj list */ 771 772 #ifdef CC_PROTOTYPE_ANSI 773 774 void 775 CCtsp_free_edgegenerator (CCtsp_edgegenerator *eg); 776 777 int 778 CCtsp_init_edgegenerator (CCtsp_edgegenerator *eg, int ncount, 779 CCdatagroup *dg, CCtsp_genadj *adj, int nneighbors), 780 CCtsp_reset_edgegenerator (CCtsp_edgegenerator *eg, double *node_piest), 781 CCtsp_generate_edges (CCtsp_edgegenerator *eg, int nwant, int *pngot, 782 int *elist, int *elen, int *finished), 783 CCtsp_edgelist_to_genadj (int ncount, int ecount, int *elist, int *elen, 784 CCtsp_genadj **adj, CCtsp_genadjobj **adjobjspace); 785 786 #else 787 788 void 789 CCtsp_free_edgegenerator (); 790 791 int 792 CCtsp_init_edgegenerator (), 793 CCtsp_reset_edgegenerator (), 794 CCtsp_generate_edges (), 795 CCtsp_edgelist_to_genadj (); 796 797 #endif 798 799 800 801 /***************************************************************************/ 802 /* */ 803 /* prob_io.c */ 804 /* */ 805 /***************************************************************************/ 806 807 #define CCtsp_PROB_IO_VERSION 1 808 #define CCtsp_PROB_FILE_NAME_LEN 128 809 810 #define CCtsp_PROB_IO_CUTS_VERSION_BASE -1000 811 #define CCtsp_PROB_IO_CUTS_VERSION -1001 /* Should be <= BASE (-1000) */ 812 813 typedef struct CCtsp_PROB_FILE { 814 CC_SFILE *f; 815 char name[CCtsp_PROB_FILE_NAME_LEN]; 816 int id; 817 int parent; 818 double ub; 819 double lb; 820 CCbigguy exactlb; 821 int nnodes; 822 int child0; 823 int child1; 824 int real; /* Set to 1 when we know this is a real child */ 825 int processed; 826 int infeasible; 827 struct { 828 int dat; 829 int edge; 830 int fulladj; 831 int cut; 832 int tour; 833 int basis; 834 int norms; 835 int fix; 836 int exactdual; 837 int history; 838 } offsets; 839 } CCtsp_PROB_FILE; 840 841 842 #ifdef CC_PROTOTYPE_ANSI 843 844 CCtsp_PROB_FILE 845 *CCtsp_prob_read (char *f, int n), 846 *CCtsp_prob_read_name (char *f), 847 *CCtsp_prob_write (char *f, int n), 848 *CCtsp_prob_write_name (char *fname, char *pname); 849 850 int 851 CCtsp_prob_file_delete (char *f, int n), 852 CCtsp_prob_getname (CCtsp_PROB_FILE *p, char *name), 853 CCtsp_prob_getid (CCtsp_PROB_FILE *p, int *id), 854 CCtsp_prob_getparent (CCtsp_PROB_FILE *p, int *parent), 855 CCtsp_prob_getub (CCtsp_PROB_FILE *p, double *ub), 856 CCtsp_prob_getlb (CCtsp_PROB_FILE *p, double *lb), 857 CCtsp_prob_getexactlb (CCtsp_PROB_FILE *p, CCbigguy *lb), 858 CCtsp_prob_getnnodes (CCtsp_PROB_FILE *p, int *nnodes), 859 CCtsp_prob_getchildren (CCtsp_PROB_FILE *p, int *child0, int *child1), 860 CCtsp_prob_getreal (CCtsp_PROB_FILE *p, int *real), 861 CCtsp_prob_getprocessed (CCtsp_PROB_FILE *p, int *processed), 862 CCtsp_prob_getinfeasible (CCtsp_PROB_FILE *p, int *infeasible), 863 CCtsp_prob_gettour (CCtsp_PROB_FILE *p, int **tour), 864 CCtsp_prob_getedges (CCtsp_PROB_FILE *p, int *nedges, int **elist, 865 int **elen), 866 CCtsp_prob_getcuts (CCtsp_PROB_FILE *p, CC_SFILE *s, CCtsp_lpcuts *cuts), 867 CCtsp_prob_getbasis (CCtsp_PROB_FILE *p, int *ccount, int *rcount, 868 int **cstat, int **rstat), 869 CCtsp_prob_getnorms (CCtsp_PROB_FILE *p, int *rcount, double **dnorm), 870 CCtsp_prob_getfulladj (CCtsp_PROB_FILE *p, int ncount, int *fullcount, 871 CCtsp_genadj **adj, CCtsp_genadjobj **adjspace), 872 CCtsp_prob_getfixed (CCtsp_PROB_FILE *p, int *ecount, int **elist), 873 CCtsp_prob_getexactdual (CCtsp_PROB_FILE *p, int ncount, 874 CCtsp_bigdual **d), 875 CCtsp_prob_gethistory (CCtsp_PROB_FILE *p, int *depth, 876 CCtsp_branchobj **history), 877 CCtsp_prob_rclose (CCtsp_PROB_FILE *p), 878 879 CCtsp_prob_putname (CCtsp_PROB_FILE *p, char *name), 880 CCtsp_prob_putid (CCtsp_PROB_FILE *p, int id), 881 CCtsp_prob_putparent (CCtsp_PROB_FILE *p, int parent), 882 CCtsp_prob_putub (CCtsp_PROB_FILE *p, double ub), 883 CCtsp_prob_putlb (CCtsp_PROB_FILE *p, double lb), 884 CCtsp_prob_putexactlb (CCtsp_PROB_FILE *p, CCbigguy lb), 885 CCtsp_prob_putnnodes (CCtsp_PROB_FILE *p, int nnodes), 886 CCtsp_prob_putchildren (CCtsp_PROB_FILE *p, int child0, int child1), 887 CCtsp_prob_putreal (CCtsp_PROB_FILE *p, int real), 888 CCtsp_prob_putprocessed (CCtsp_PROB_FILE *p, int processed), 889 CCtsp_prob_putinfeasible (CCtsp_PROB_FILE *p, int infeasible), 890 CCtsp_prob_puttour (CCtsp_PROB_FILE *p, int *tour), 891 CCtsp_prob_putedges (CCtsp_PROB_FILE *p, int nedges, int *elist, int *elen), 892 CCtsp_prob_putcuts (CCtsp_PROB_FILE *p, CC_SFILE *s, CCtsp_lpcuts *cuts), 893 CCtsp_prob_putbasis (CCtsp_PROB_FILE *p, int ccount, int rcount, int *cstat, 894 int *rstat), 895 CCtsp_prob_putnorms (CCtsp_PROB_FILE *p, int rcount, double *dnorm), 896 CCtsp_prob_putfulladj (CCtsp_PROB_FILE *p, int ncount, int fullcount, 897 CCtsp_genadj *adj), 898 CCtsp_prob_putfixed (CCtsp_PROB_FILE *p, int ecount, int *elist), 899 CCtsp_prob_putexactdual (CCtsp_PROB_FILE *p, CCtsp_bigdual *d, int ncount), 900 CCtsp_prob_puthistory (CCtsp_PROB_FILE *p, int depth, 901 CCtsp_branchobj *history), 902 CCtsp_prob_wclose (CCtsp_PROB_FILE *p); 903 904 #else 905 906 CCtsp_PROB_FILE 907 *CCtsp_prob_read (), 908 *CCtsp_prob_read_name (), 909 *CCtsp_prob_write (), 910 *CCtsp_prob_write_name (); 911 912 int 913 CCtsp_prob_file_delete (), 914 CCtsp_prob_getname (), 915 CCtsp_prob_getid (), 916 CCtsp_prob_getparent (), 917 CCtsp_prob_getub (), 918 CCtsp_prob_getlb (), 919 CCtsp_prob_getexactlb (), 920 CCtsp_prob_getnnodes (), 921 CCtsp_prob_getchildren (), 922 CCtsp_prob_getreal (), 923 CCtsp_prob_getprocessed (), 924 CCtsp_prob_getinfeasible (), 925 CCtsp_prob_gettour (), 926 CCtsp_prob_getedges (), 927 CCtsp_prob_getcuts (), 928 CCtsp_prob_getbasis (), 929 CCtsp_prob_getnorms (), 930 CCtsp_prob_getfulladj (), 931 CCtsp_prob_getfixed (), 932 CCtsp_prob_getexactdual (), 933 CCtsp_prob_gethistory (), 934 CCtsp_prob_rclose (), 935 936 CCtsp_prob_putname (), 937 CCtsp_prob_putid (), 938 CCtsp_prob_putparent (), 939 CCtsp_prob_putub (), 940 CCtsp_prob_putlb (), 941 CCtsp_prob_putexactlb (), 942 CCtsp_prob_putnnodes (), 943 CCtsp_prob_putchildren (), 944 CCtsp_prob_putreal (), 945 CCtsp_prob_putprocessed (), 946 CCtsp_prob_putinfeasible (), 947 CCtsp_prob_puttour (), 948 CCtsp_prob_putedges (), 949 CCtsp_prob_putcuts (), 950 CCtsp_prob_putbasis (), 951 CCtsp_prob_putnorms (), 952 CCtsp_prob_putfulladj (), 953 CCtsp_prob_putfixed (), 954 CCtsp_prob_putexactdual (), 955 CCtsp_prob_puthistory (), 956 CCtsp_prob_wclose (); 957 958 #endif 959 960 961 962 /***************************************************************************/ 963 /* */ 964 /* qsparse.c */ 965 /* */ 966 /***************************************************************************/ 967 968 typedef struct CCtsp_qsparsegroup { 969 CCdheap *add_queue; /* An empty heap will be maintained */ 970 CCdheap *sub_queue; /* An empty heap will be maintained */ 971 int *count_m1; /* The array will be maintained at 0 */ 972 int *count_non0; /* The array will be maintained at 0 */ 973 int *count_1; /* The array will be maintained at 0 */ 974 int *on_add_queue; /* The array will be maintained at 0 */ 975 int *on_sub_queue; /* The array will be maintained at 0 */ 976 int *mults; /* The array will be maintained at 0 */ 977 } CCtsp_qsparsegroup; 978 979 #ifdef CC_PROTOTYPE_ANSI 980 981 void 982 CCtsp_free_qsparsify (CCtsp_qsparsegroup **pqs); 983 int 984 CCtsp_qsparsify (CCtsp_qsparsegroup **pqs, struct CCtsp_lpgraph *g, 985 int *pnzlist, int *scount, struct CCtsp_sparser **slist, 986 int *savedcount); 987 #else 988 989 void 990 CCtsp_free_qsparsify (); 991 int 992 CCtsp_qsparsify (); 993 994 #endif 995 996 #endif /* __TSP_H */ 997