00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #ifndef __TSP_H
00026 #define __TSP_H
00027
00028 #include "util.h"
00029 #include "edgegen.h"
00030 #include "bigguy.h"
00031 #include "lp.h"
00032 #include "cut.h"
00033 #include "kdtree.h"
00034 #include "combs.h"
00035
00036
00037
00038 #define CCtsp_MIN_VIOL (0.002)
00039 #define CCtsp_CUTS_DELTA
00040 #define CCtsp_CUTS_NEXT_TOL (0.01)
00041 #define CCtsp_CUTS_NEXT_ROUND (0.001)
00042 #define CCtsp_TENTATIVE_CUTS_NEXT_TOL (0.1)
00043 #define CCtsp_TENTATIVE_CUTS_NEXT_ROUND (0.01)
00044 #define CCtsp_PRICE_RCTHRESH (-0.00001)
00045 #define CCtsp_PRICE_MAXPENALTY (0.10)
00046 #define CCtsp_PHASE1_RCTHRESH (-0.000000001)
00047 #define CCtsp_PHASE1_MAXPENALTY (0.00000001)
00048 #define CCtsp_EDGE_LIFE (1000000)
00049 #define CCtsp_CUT_LIFE (10)
00050 #define CCtsp_DUAL_DUST (0.01)
00051 #define CCtsp_EDGE_DUST (0.000001)
00052
00053 #define CCtsp_CUT_BATCH (250)
00054 #define CCtsp_STORE_BATCH (250)
00055 #define CCtsp_INTTOL (0.0001)
00056
00057
00058
00059 #define CCtsp_BRANCH_MIDDLE 1
00060 #define CCtsp_BRANCH_STRONG 2
00061
00062
00063
00064
00065
00066 #define CCtsp_HOST_PORT ((unsigned short) 24846)
00067 #define CCtsp_PROB_PORT ((unsigned short) 24847)
00068 #define CCtsp_CUT_PORT ((unsigned short) 24868)
00069 #define CCtsp_DOMINO_PORT ((unsigned short) 24869)
00070
00071
00072
00073 #define CCtsp_LP_MAXDOUBLE 1e30
00074
00075 #define CCtsp_COMBRHS(c) (3*(c)->cliquecount - 2)
00076 #define CCtsp_DOMINORHS(c) (3*(c)->dominocount + 1)
00077
00078 typedef struct CCtsp_lpnode
00079 {
00080 int deg;
00081 int mark;
00082 struct CCtsp_lpadj *adj;
00083 }
00084 CCtsp_lpnode;
00085
00086 typedef struct CCtsp_lpedge
00087 {
00088 int ends[2];
00089 int fixed;
00090 int branch;
00091 int len;
00092 int age;
00093 int coef;
00094 int coefnext;
00095 }
00096 CCtsp_lpedge;
00097
00098 typedef struct CCtsp_lpadj
00099 {
00100 int to;
00101 int edge;
00102 }
00103 CCtsp_lpadj;
00104
00105 typedef struct CCtsp_lpgraph
00106 {
00107 int ncount;
00108 int espace;
00109 int ecount;
00110 int nodemarker;
00111 CCtsp_lpnode *nodes;
00112 CCtsp_lpedge *edges;
00113 CCtsp_lpadj *adjspace;
00114 int adjstart;
00115 int adjend;
00116 }
00117 CCtsp_lpgraph;
00118
00119 typedef struct CCtsp_predge
00120 {
00121 int ends[2];
00122 int len;
00123 double rc;
00124 }
00125 CCtsp_predge;
00126
00127 typedef struct CCtsp_pricegroup
00128 {
00129 int ncount;
00130 int espace;
00131 int ecount;
00132 CCtsp_lpnode *nodes;
00133 CCtsp_predge *edges;
00134 int cliquecount;
00135 struct CCtsp_lpclique *cliques;
00136 CCtsp_lpgraph *graph;
00137 CCtsp_lpadj *adjspace;
00138 double *node_pi;
00139 double *clique_pi;
00140 double penalty;
00141 }
00142 CCtsp_pricegroup;
00143
00144 typedef struct CCtsp_extraedge
00145 {
00146 int ends[2];
00147 }
00148 CCtsp_extraedge;
00149
00150 typedef struct CCtsp_sparser
00151 {
00152 unsigned int node:24;
00153 unsigned int mult:8;
00154 }
00155 CCtsp_sparser;
00156
00157 typedef struct CCtsp_segment
00158 {
00159 int lo;
00160 int hi;
00161 }
00162 CCtsp_segment;
00163
00164 typedef struct CCtsp_lpclique
00165 {
00166 int segcount;
00167 struct CCtsp_segment *nodes;
00168 int hashnext;
00169 int refcount;
00170 }
00171 CCtsp_lpclique;
00172
00173 typedef struct CCtsp_lpdomino
00174 {
00175 CCtsp_lpclique sets[2];
00176 int hashnext;
00177 int refcount;
00178 }
00179 CCtsp_lpdomino;
00180
00181 #define CC_FOREACH_NODE_IN_CLIQUE(i,c,tmp) \
00182 for(tmp=0;tmp<(c).segcount;tmp++) \
00183 for(i=(c).nodes[tmp].lo;i<=(c).nodes[tmp].hi;i++)
00184
00185 typedef struct CCtsp_skeleton
00186 {
00187 int atomcount;
00188 int *atoms;
00189 }
00190 CCtsp_skeleton;
00191
00192 #define CCtsp_NEWCUT_AGE (-1)
00193
00194 typedef struct CCtsp_lpcut
00195 {
00196 int cliquecount;
00197 int dominocount;
00198 int modcount;
00199 int age;
00200 int rhs;
00201 char sense;
00202 char branch;
00203 int *cliques;
00204 int *dominos;
00205 struct CCtsp_sparser *mods;
00206 CCtsp_skeleton skel;
00207 }
00208 CCtsp_lpcut;
00209
00210 typedef struct CCtsp_lpcut_in
00211 {
00212 int cliquecount;
00213 int dominocount;
00214 int rhs;
00215 char sense;
00216 char branch;
00217 CCtsp_lpclique *cliques;
00218 CCtsp_lpdomino *dominos;
00219 CCtsp_skeleton skel;
00220 struct CCtsp_lpcut_in *next;
00221 struct CCtsp_lpcut_in *prev;
00222 }
00223 CCtsp_lpcut_in;
00224
00225 typedef struct CCtsp_lp_result
00226 {
00227 double ub;
00228 double lb;
00229 int ecount;
00230 int *elist;
00231 double *x;
00232 double *rc;
00233 }
00234 CCtsp_lp_result;
00235
00236 typedef struct CCtsp_lpcuts
00237 {
00238 int cutcount;
00239 int savecount;
00240 int cliqueend;
00241 int cutspace;
00242 int cliquespace;
00243 int cliquehashsize;
00244 int cliquefree;
00245 int *cliquehash;
00246 CCtsp_lpcut *cuts;
00247 CCtsp_lpclique *cliques;
00248 CCgenhash *cuthash;
00249 char *tempcuthash;
00250 int tempcuthashsize;
00251 int dominoend;
00252 int dominospace;
00253 int dominohashsize;
00254 int dominofree;
00255 int *dominohash;
00256 CCtsp_lpdomino *dominos;
00257 double *workloads;
00258 }
00259 CCtsp_lpcuts;
00260
00261 typedef struct CCtsp_bigdual
00262 {
00263 int cutcount;
00264 CCbigguy *node_pi;
00265 CCbigguy *cut_pi;
00266 }
00267 CCtsp_bigdual;
00268
00269 typedef struct CCtsp_tighten_info
00270 {
00271 int ncall;
00272 int nfail;
00273 int nadd;
00274 int nadd_tied;
00275 int ndel;
00276 int ndel_tied;
00277 double add_delta;
00278 double del_delta;
00279 double time;
00280 }
00281 CCtsp_tighten_info;
00282
00283 typedef struct CCtsp_branchobj
00284 {
00285 int depth;
00286 int rhs;
00287 int ends[2];
00288 char sense;
00289 CCtsp_lpclique *clique;
00290 }
00291 CCtsp_branchobj;
00292
00293 typedef struct CCtsp_cutnode
00294 {
00295 #define CCtsp_CUT_INNODELIST(t) ((t)&4)
00296 #define CCtsp_CUT_ROOT 0
00297 #define CCtsp_CUT_PNODE 1
00298 #define CCtsp_CUT_QNODE 2
00299 #define CCtsp_CUT_LEAF 4
00300 #define CCtsp_CUT_EXTERN 5
00301 int type;
00302 struct CCtsp_cutnode *child;
00303 struct CCtsp_cutnode *sibling;
00304 struct CCtsp_cutnode *next;
00305 }
00306 CCtsp_cutnode;
00307
00308 typedef struct CCtsp_cuttree
00309 {
00310 int nodecount;
00311 int extern_node;
00312 CCtsp_cutnode *nodelist;
00313 CCtsp_cutnode *root;
00314 CCptrworld cutnode_world;
00315 }
00316 CCtsp_cuttree;
00317
00318
00319
00320 typedef struct CCtsp_genadj
00321 {
00322 int deg;
00323 struct CCtsp_genadjobj *list;
00324 }
00325 CCtsp_genadj;
00326
00327 typedef struct CCtsp_genadjobj
00328 {
00329 int end;
00330 int len;
00331 }
00332 CCtsp_genadjobj;
00333
00334 typedef struct CCtsp_edgegenerator
00335 {
00336 double *node_piest;
00337 struct CCdatagroup *dg;
00338 int *supply;
00339 CCkdtree *kdtree;
00340 CCxnear *xnear;
00341 struct CCtsp_xnorm_pricer *xprice;
00342 CCtsp_genadjobj *adjobjspace;
00343 CCtsp_genadj *adj;
00344 int ncount;
00345 int nneighbors;
00346 int start;
00347 int current;
00348 int supplyhead;
00349 int supplycount;
00350 }
00351 CCtsp_edgegenerator;
00352
00353 typedef struct CCtsp_xnorm_pricer_val
00354 {
00355 double val;
00356 struct CCtsp_xnorm_pricer_val *next;
00357 struct CCtsp_xnorm_pricer_val *prev;
00358 int index;
00359 }
00360 CCtsp_xnorm_pricer_val;
00361
00362 typedef struct CCtsp_xnorm_pricer
00363 {
00364 CCdatagroup *dat;
00365 double *pi;
00366 int *order;
00367 CCtsp_xnorm_pricer_val *xminuspi_space;
00368 CCtsp_xnorm_pricer_val *xminuspi;
00369 int *invxminuspi;
00370 int ncount;
00371 }
00372 CCtsp_xnorm_pricer;
00373
00374 typedef struct CCtsp_statistics
00375 {
00376 CCutil_timer cutting_loop;
00377 CCutil_timer cutting_inner_loop;
00378 CCutil_timer cuts_filecut;
00379 CCutil_timer cuts_filecut_opt;
00380 CCutil_timer cuts_cutpool;
00381 CCutil_timer cuts_cutpool_opt;
00382 CCutil_timer cuts_connect;
00383 CCutil_timer cuts_connect_opt;
00384 CCutil_timer cuts_segment;
00385 CCutil_timer cuts_segment_opt;
00386 CCutil_timer cuts_remotepool;
00387 CCutil_timer cuts_remotepool_opt;
00388 CCutil_timer cuts_blockcomb;
00389 CCutil_timer cuts_blockcomb_opt;
00390 CCutil_timer cuts_growcomb;
00391 CCutil_timer cuts_growcomb_opt;
00392 CCutil_timer cuts_exactsubtour;
00393 CCutil_timer cuts_exactsubtour_opt;
00394 CCutil_timer cuts_tighten_lp;
00395 CCutil_timer cuts_tighten_lp_opt;
00396 CCutil_timer cuts_tighten_lp_close;
00397 CCutil_timer cuts_tighten_lp_close_opt;
00398 CCutil_timer cuts_decker_lp;
00399 CCutil_timer cuts_decker_lp_opt;
00400 CCutil_timer cuts_decker_lp_close;
00401 CCutil_timer cuts_decker_lp_close_opt;
00402 CCutil_timer cuts_star_lp;
00403 CCutil_timer cuts_star_lp_opt;
00404 CCutil_timer cuts_handling_lp;
00405 CCutil_timer cuts_handling_lp_opt;
00406 CCutil_timer cuts_cliquetree_lp;
00407 CCutil_timer cuts_cliquetree_lp_opt;
00408 CCutil_timer cuts_teething_lp;
00409 CCutil_timer cuts_teething_lp_opt;
00410 CCutil_timer cuts_fastblossom;
00411 CCutil_timer cuts_fastblossom_opt;
00412 CCutil_timer cuts_ghfastblossom;
00413 CCutil_timer cuts_ghfastblossom_opt;
00414 CCutil_timer cuts_exactblossom;
00415 CCutil_timer cuts_exactblossom_opt;
00416 CCutil_timer cuts_tighten_pool;
00417 CCutil_timer cuts_tighten_pool_opt;
00418 CCutil_timer cuts_decker_pool;
00419 CCutil_timer cuts_decker_pool_opt;
00420 CCutil_timer cuts_star_pool;
00421 CCutil_timer cuts_star_pool_opt;
00422 CCutil_timer cuts_handling_pool;
00423 CCutil_timer cuts_handling_pool_opt;
00424 CCutil_timer cuts_teething_pool;
00425 CCutil_timer cuts_teething_pool_opt;
00426 CCutil_timer cuts_consecutiveones;
00427 CCutil_timer cuts_consecutiveones_opt;
00428 CCutil_timer cuts_necklace;
00429 CCutil_timer cuts_necklace_opt;
00430 CCutil_timer cuts_localcut;
00431 CCutil_timer cuts_localcut_opt;
00432
00433 CCutil_timer cuts_extraconnect;
00434 CCutil_timer cuts_extraconnect_opt;
00435
00436 CCutil_timer sparse_edge_check;
00437 CCutil_timer full_edge_check;
00438
00439 CCutil_timer addcuts;
00440 CCutil_timer addcuts_opt;
00441 CCutil_timer agecuts;
00442 CCutil_timer agecuts_opt;
00443 CCutil_timer ageedges;
00444 CCutil_timer ageedges_opt;
00445 CCutil_timer addbad;
00446 CCutil_timer addbad_opt;
00447 CCutil_timer strongbranch;
00448 CCutil_timer strongbranch_opt;
00449 CCutil_timer linkern;
00450
00451 CCutil_timer misc;
00452 CCutil_timer misc_opt;
00453 CCutil_timer total;
00454 int problem_cnt;
00455
00456 CCtsp_tighten_info tighten_stats;
00457 CCtsp_tighten_info extra_tighten_stats;
00458 }
00459 CCtsp_statistics;
00460
00461 typedef struct CCtsp_lp
00462 {
00463 CCtsp_lpgraph graph;
00464 CCtsp_lpcuts cuts;
00465 CCtsp_lpcuts *pool;
00466 CCtsp_lpcuts *remotepool;
00467 CClp *lp;
00468 int *perm;
00469 CCdatagroup *dat;
00470 int fullcount;
00471 CCtsp_genadj *fulladj;
00472 CCtsp_genadjobj *fulladjspace;
00473 int nfixededges;
00474 int *fixededges;
00475 struct CCtsp_qsparsegroup *sparsifier;
00476 int edge_life;
00477 int cut_life;
00478 char *problabel;
00479 char *probloc;
00480 int id;
00481 int parent_id;
00482 int root;
00483 double upperbound;
00484 double lowerbound;
00485 CCbigguy exact_lowerbound;
00486 CCtsp_bigdual *exact_dual;
00487 int infeasible;
00488 int full_edges_valid;
00489 CClp_warmstart *warmstart;
00490 CCtsp_lpcut_in cutqueue;
00491
00492 CCtsp_lp_result result;
00493 int branchdepth;
00494 CCtsp_branchobj *branchhistory;
00495 CCtsp_cuttree tightcuts;
00496 CCtsp_statistics stats;
00497 }
00498 CCtsp_lp;
00499
00500 typedef struct CCtsp_lprow
00501 {
00502 int rowcnt;
00503 int nzcnt;
00504 char *sense;
00505 double *rhs;
00506 int *begin;
00507 int indexspace;
00508 int *indices;
00509 int entryspace;
00510 double *entries;
00511 }
00512 CCtsp_lprow;
00513
00514 typedef struct CCtsp_cutselect
00515 {
00516 int cutpool;
00517 int remotepool;
00518 char *remotehost;
00519 unsigned short remoteport;
00520 int connect;
00521 int segments;
00522 int exactsubtour;
00523 int blockcombs;
00524 int growcombs;
00525 int prclique;
00526 int tighten_lp;
00527 int teething_lp;
00528 int cliquetree_lp;
00529 int tighten_pool;
00530 int decker_lp;
00531 int decker_pool;
00532 int star_lp;
00533 int star_pool;
00534 int handling_lp;
00535 int handling_pool;
00536 int maxchunksize;
00537 int filecuts;
00538 char *filecutname;
00539 int teething_pool;
00540 int fastblossom;
00541 int ghfastblossom;
00542 int exactblossom;
00543 int consecutiveones;
00544 int dominos;
00545 int necklace;
00546 int usetighten;
00547 int extra_connect;
00548 double nexttol;
00549 double roundtol;
00550 int fastcuts;
00551 }
00552 CCtsp_cutselect;
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562 #define CCtsp_BBTASK_BRANCH 'b'
00563 #define CCtsp_BBREQ_BRANCHDONE 'B'
00564 #define CCtsp_BBTASK_CUT 'c'
00565 #define CCtsp_BBREQ_CUTDONE 'C'
00566 #define CCtsp_BBREQ_DEADNODE 'D'
00567 #define CCtsp_BBREQ_HELLO 'H'
00568 #define CCtsp_BBREQ_NOBRANCH 'N'
00569 #define CCtsp_BBREQ_TASK 'T'
00570 #define CCtsp_BBREQ_TOUR 'U'
00571 #define CCtsp_BBTASK_WAIT 'w'
00572 #define CCtsp_BBTASK_EXIT 'x'
00573 #define CCtsp_BBREQ_EXIT 'X'
00574
00575 #define CCtsp_BBTASK_TENTATIVE_CUT 'i'
00576 #define CCtsp_BBREQ_TENTATIVE_CUTDONE 'I'
00577 #define CCtsp_BBTASK_TENTATIVE_BRANCH 'j'
00578 #define CCtsp_BBREQ_TENTATIVE_BRANCHDONE 'J'
00579
00580
00581 int CCtsp_bfs_brancher (char *probloc,
00582 int id,
00583 double lowerbound,
00584 CCtsp_cutselect * sel,
00585 CCtsp_cutselect * tsel,
00586 double *upbound,
00587 int *bbcount,
00588 int usecliques,
00589 CCdatagroup * mydat,
00590 int *ptour,
00591 CCtsp_lpcuts * pool,
00592 int ncount,
00593 int *besttour,
00594 unsigned short hostport,
00595 double *branchzeit,
00596 int save_proof,
00597 int tentative_branch_num,
00598 int longedge_branching,
00599 double *timebound,
00600 int *hit_timebound,
00601 int silent,
00602 CCrandstate * rstate),
00603 CCtsp_bfs_restart (char *probloc,
00604 char *restart_name,
00605 CCtsp_cutselect * sel,
00606 CCtsp_cutselect * tsel,
00607 double *upbound,
00608 int *bbcount,
00609 int usecliques,
00610 CCdatagroup * dat,
00611 int *ptour,
00612 CCtsp_lpcuts * pool,
00613 int ncount,
00614 int *besttour,
00615 unsigned short hostport,
00616 double *branchzeit,
00617 int save_proof,
00618 int tentative_branch_num,
00619 int longedge_branching,
00620 double *timebound,
00621 int *hit_timebound,
00622 int silent,
00623 CCrandstate * rstate),
00624 #ifdef CC_NETREADY
00625
00626 CCtsp_grunt (char *hostname,
00627 unsigned short hostport,
00628 char *poolfname,
00629 char *cutbossname,
00630 char *probloc,
00631 int silent,
00632 CCrandstate * rstate),
00633 #endif
00634
00635 CCtsp_easy_dfs_brancher (CCtsp_lp * lp,
00636 CCtsp_cutselect * sel,
00637 int depth,
00638 double *upbound,
00639 int *bbcount,
00640 int usecliques,
00641 int *besttour,
00642 int longedge_branching,
00643 int simple_branching,
00644 int silent,
00645 CCrandstate * rstate),
00646 CCtsp_do_interactive_branch (CCtsp_lp * lp,
00647 int silent,
00648 CCrandstate * rstate);
00649
00650
00651
00652
00653
00654
00655
00656
00657
00658
00659 int CCtsp_block_combs (CCtsp_lpcut_in ** cuts,
00660 int *cutcount,
00661 int ncount,
00662 int ecount,
00663 int *elist,
00664 double *x,
00665 int silent);
00666
00667
00668
00669
00670
00671
00672
00673
00674
00675
00676 int CCtsp_fastblossom (CCtsp_lpcut_in ** cuts,
00677 int *cutcount,
00678 int ncount,
00679 int ecount,
00680 int *elist,
00681 double *x),
00682 CCtsp_ghfastblossom (CCtsp_lpcut_in ** cuts,
00683 int *cutcount,
00684 int ncount,
00685 int ecount,
00686 int *elist,
00687 double *x),
00688 CCtsp_exactblossom (CCtsp_lpcut_in ** cuts,
00689 int *cutcount,
00690 int ncount,
00691 int ecount,
00692 int *elist,
00693 double *x,
00694 CCrandstate * rstate);
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705 int CCtsp_find_branch (CCtsp_lp * lp,
00706 int nwant,
00707 int *ngot,
00708 CCtsp_branchobj ** bobj,
00709 double *val,
00710 int **cyc,
00711 int usecliques,
00712 int longedge_branching,
00713 int silent),
00714 CCtsp_find_fast_branch (CCtsp_lp * lp,
00715 int *ngot,
00716 CCtsp_branchobj ** bobj,
00717 double *val,
00718 int **cyc,
00719 int usecliques,
00720 int longedge_branching,
00721 int silent),
00722 CCtsp_find_branch_edge (CCtsp_lp * lp,
00723 int *n0,
00724 int *n1,
00725 double *val,
00726 int **cyc,
00727 int branchtype,
00728 int silent),
00729 CCtsp_check_integral (CCtsp_lp * lp,
00730 double *val,
00731 int **cyc,
00732 int *yesno,
00733 int silent),
00734 CCtsp_find_branch_cliques (CCtsp_lp * lp,
00735 int nwant,
00736 int longedge_branching,
00737 int *ngot,
00738 CCtsp_lpclique ** bcliques,
00739 double **bval,
00740 int silent),
00741 CCtsp_execute_branch (CCtsp_lp * lp,
00742 CCtsp_branchobj * b,
00743 int silent,
00744 CCrandstate * rstate),
00745 CCtsp_execute_unbranch (CCtsp_lp * lp,
00746 CClp_warmstart * warmstart,
00747 int silent,
00748 CCrandstate * rstate),
00749 CCtsp_add_branchhistory_to_lp (CCtsp_lp * lp),
00750 CCtsp_bb_find_branch (char *probname,
00751 int probnum,
00752 int ncount,
00753 CCdatagroup * dat,
00754 int *ptour,
00755 double *upperbound,
00756 CCtsp_lpcuts * pool,
00757 int nwant,
00758 int *ngot,
00759 CCtsp_branchobj ** b,
00760 int usecliques,
00761 int longedge_branching,
00762 int *prune,
00763 int *foundtour,
00764 int *besttour,
00765 int silent,
00766 CCrandstate * rstate),
00767 CCtsp_splitprob (CCtsp_lp * lp,
00768 CCtsp_branchobj * b,
00769 int child0,
00770 int child1,
00771 int silent,
00772 CCrandstate * rstate),
00773 CCtsp_bb_splitprob (char *probname,
00774 int probnum,
00775 int ncount,
00776 CCdatagroup * dat,
00777 int *ptour,
00778 double initial_ub,
00779 CCtsp_lpcuts * pool,
00780 CCtsp_branchobj * b,
00781 int child0,
00782 int child1,
00783 double *val0,
00784 double *val1,
00785 int *prune0,
00786 int *prune1,
00787 int silent,
00788 CCrandstate * rstate),
00789 CCtsp_dumptour (int ncount,
00790 CCdatagroup * dat,
00791 int *perm,
00792 char *probname,
00793 int *tour,
00794 int silent);
00795
00796 void CCtsp_init_branchobj (CCtsp_branchobj * b),
00797 CCtsp_free_branchobj (CCtsp_branchobj * b),
00798 CCtsp_print_branchhistory (CCtsp_lp * lp);
00799
00800
00801
00802
00803
00804
00805
00806
00807
00808 int CCtsp_init_cliquehash (CCtsp_lpcuts * cuts,
00809 int size),
00810 CCtsp_register_clique (CCtsp_lpcuts * cuts,
00811 CCtsp_lpclique * c);
00812
00813 unsigned int CCtsp_hashclique (CCtsp_lpclique * c);
00814
00815 void CCtsp_free_cliquehash (CCtsp_lpcuts * cuts),
00816 CCtsp_unregister_clique (CCtsp_lpcuts * cuts,
00817 int c),
00818 CCtsp_clique_eq (CCtsp_lpclique * c,
00819 CCtsp_lpclique * d,
00820 int *yes_no);
00821
00822 int CCtsp_init_dominohash (CCtsp_lpcuts * cuts,
00823 int size),
00824 CCtsp_register_domino (CCtsp_lpcuts * cuts,
00825 CCtsp_lpdomino * c);
00826
00827 unsigned int CCtsp_hashdomino (CCtsp_lpdomino * d);
00828
00829 void CCtsp_free_dominohash (CCtsp_lpcuts * cuts),
00830 CCtsp_domino_eq (CCtsp_lpdomino * c,
00831 CCtsp_lpdomino * d,
00832 int *yes_no),
00833 CCtsp_unregister_domino (CCtsp_lpcuts * cuts,
00834 int c);
00835
00836
00837
00838
00839
00840
00841
00842
00843
00844 typedef struct CCtsp_cutinfo
00845 {
00846 CC_SRKexpinfo expand;
00847 CCtsp_lpcut_in **clist;
00848 CCtsp_lpcut_in *current;
00849 int *cutcount;
00850 }
00851 CCtsp_cutinfo;
00852
00853
00854 int CCtsp_clique_to_array (CCtsp_lpclique * c,
00855 int **ar,
00856 int *count),
00857 CCtsp_clique_delta (CCtsp_lpgraph * g,
00858 double *x,
00859 CCtsp_lpclique * c,
00860 double *delta),
00861 CCtsp_copy_lpcut_in (CCtsp_lpcut_in * c,
00862 CCtsp_lpcut_in * new),
00863 CCtsp_segment_to_subtour (CCtsp_lpcut_in ** cut,
00864 int a,
00865 int b,
00866 int ncount),
00867 CCtsp_array_to_subtour (CCtsp_lpcut_in ** cut,
00868 int *ar,
00869 int acount,
00870 int ncount),
00871 CCtsp_array_to_lpclique (int *ar,
00872 int acount,
00873 CCtsp_lpclique * cliq),
00874 CCtsp_seglist_to_lpclique (int nseg,
00875 int *list,
00876 CCtsp_lpclique * cliq),
00877 CCtsp_shrunk_set_to_lpclique (int cnt,
00878 int *set,
00879 int *wset,
00880 CC_SRKexpinfo * expand,
00881 CCtsp_lpclique * cliq),
00882 CCtsp_add_nodes_to_lpclique (CCtsp_lpclique * cin,
00883 CCtsp_lpclique * cout,
00884 int addcount,
00885 int *adda),
00886 CCtsp_delete_nodes_from_lpclique (CCtsp_lpclique * cin,
00887 CCtsp_lpclique * cout,
00888 int delcount,
00889 int *del),
00890 CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts * cuts,
00891 CCtsp_lpcut * c,
00892 CCtsp_lpcut_in * new),
00893 CCtsp_copy_lpclique (CCtsp_lpclique * c,
00894 CCtsp_lpclique * new),
00895 CCtsp_copy_lpdomino (CCtsp_lpdomino * c,
00896 CCtsp_lpdomino * new),
00897 CCtsp_create_lpcliques (CCtsp_lpcut_in * c,
00898 int cliquecount),
00899 CCtsp_max_node (CCtsp_lpcut_in * c),
00900 CCtsp_build_dp_cut (CCtsp_lpcut_in ** cut,
00901 int ndomino,
00902 int *Acount,
00903 int **A,
00904 int *Bcount,
00905 int **B,
00906 int handlecount,
00907 int *handle);
00908
00909 void CCtsp_mark_clique (CCtsp_lpclique * c,
00910 int *marks,
00911 int marker),
00912 CCtsp_mark_domino (CCtsp_lpdomino * c,
00913 int *marks,
00914 int marker),
00915 CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph * g,
00916 CCtsp_lpclique * c,
00917 int *marks,
00918 int marker),
00919 CCtsp_mark_domino_and_neighbors (CCtsp_lpgraph * g,
00920 CCtsp_lpdomino * c,
00921 int *marks,
00922 int marker),
00923 CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph * g,
00924 CCtsp_lpclique * c,
00925 double *marks,
00926 double marker),
00927 CCtsp_mark_cut (CCtsp_lpcut_in * c,
00928 int *marks,
00929 int marker),
00930 CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph * g,
00931 CCtsp_lpcut_in * c,
00932 int *marks,
00933 int marker),
00934 CCtsp_is_clique_marked (CCtsp_lpclique * c,
00935 int *marks,
00936 int marker,
00937 int *yes_no),
00938 CCtsp_clique_count (CCtsp_lpclique * c,
00939 int *count),
00940 CCtsp_clique_marked_count (CCtsp_lpclique * c,
00941 int *marks,
00942 int marker,
00943 int *count),
00944 CCtsp_init_lpcut_in (CCtsp_lpcut_in * c),
00945 CCtsp_init_lpcut (CCtsp_lpcut * c),
00946 CCtsp_init_lpclique (CCtsp_lpclique * c),
00947 CCtsp_init_lpdomino (CCtsp_lpdomino * c),
00948 CCtsp_print_lpcut_in (CCtsp_lpcut_in * c),
00949 CCtsp_print_lpclique (CCtsp_lpclique * c),
00950 CCtsp_print_lpdomino (CCtsp_lpdomino * d),
00951 CCtsp_lpclique_compare (CCtsp_lpclique * a,
00952 CCtsp_lpclique * b,
00953 int *diff);
00954
00955
00956
00957
00958
00959
00960
00961
00962
00963
00964 int CCtsp_cutting_multiple_loop (CCtsp_lp * lp,
00965 CCtsp_cutselect * sel,
00966 int savelp,
00967 int maxlocal,
00968 int update_tol,
00969 const char *dombossname,
00970 int silent,
00971 CCrandstate * rstate),
00972 CCtsp_cutting_loop (CCtsp_lp * lp,
00973 CCtsp_cutselect * sel,
00974 int savelp,
00975 const char *dombossname,
00976 int silent,
00977 CCrandstate * rstate),
00978 CCtsp_subtour_loop (CCtsp_lp * lp,
00979 int silent,
00980 CCrandstate * rstate),
00981 CCtsp_blossom_loop (CCtsp_lp * lp,
00982 int silent,
00983 CCrandstate * rstate),
00984 CCtsp_subtour_and_blossom_loop (CCtsp_lp * lp,
00985 int silent,
00986 CCrandstate * rstate),
00987 CCtsp_pricing_loop (CCtsp_lp * lp,
00988 double *bnd,
00989 int silent,
00990 CCrandstate * rstate),
00991 CCtsp_call_x_heuristic (CCtsp_lp * lp,
00992 double *val,
00993 int *outcyc,
00994 int silent,
00995 CCrandstate * rstate),
00996 CCtsp_bb_cutting (char *probname,
00997 int probnum,
00998 int prob_newnum,
00999 int ncount,
01000 CCdatagroup * dat,
01001 int *ptour,
01002 double *upbound,
01003 CCtsp_lpcuts * pool,
01004 CCtsp_cutselect * sel,
01005 double *val,
01006 int *prune,
01007 int *foundtour,
01008 int *besttour,
01009 int level,
01010 int silent,
01011 CCrandstate * rstate),
01012 CCtsp_cutselect_set_tols (CCtsp_cutselect * s,
01013 CCtsp_lp * lp,
01014 int level,
01015 int silent);
01016
01017 void CCtsp_init_cutselect (CCtsp_cutselect * s),
01018 CCtsp_init_tentative_cutselect (CCtsp_cutselect * s),
01019 CCtsp_init_simple_cutselect (CCtsp_cutselect * s),
01020 CCtsp_init_fast_cutselect (CCtsp_cutselect * s);
01021
01022
01023
01024
01025
01026
01027
01028
01029
01030 int CCtsp_connect_cuts (CCtsp_lpcut_in ** cuts,
01031 int *cutcount,
01032 int ncount,
01033 int ecount,
01034 int *elist,
01035 double *x),
01036 CCtsp_segment_cuts (CCtsp_lpcut_in ** cuts,
01037 int *cutcount,
01038 int ncount,
01039 int ecount,
01040 int *elist,
01041 double *x),
01042 CCtsp_shrink_subtours (CCtsp_lpcut_in ** cuts,
01043 int *cutcount,
01044 int ncount,
01045 int ecount,
01046 int *elist,
01047 double *x),
01048 CCtsp_exact_subtours (CCtsp_lpcut_in ** cuts,
01049 int *cutcount,
01050 int ncount,
01051 int ecount,
01052 int *elist,
01053 double *x),
01054 CCtsp_tighten_lp (CCtsp_lpcuts * cuts,
01055 CCtsp_tighten_info * stats,
01056 CCtsp_lpcut_in ** cutsout,
01057 int *cutcount,
01058 int ncount,
01059 int ecount,
01060 int *elist,
01061 double *x,
01062 double testtol,
01063 int maxcuts,
01064 double *viol,
01065 CCrandstate * rstate),
01066 CCtsp_double_decker_lp (CCtsp_lpcuts * cuts,
01067 CCtsp_tighten_info * stats,
01068 CCtsp_lpcut_in ** cutsout,
01069 int *cutcount,
01070 int ncount,
01071 int ecount,
01072 int *elist,
01073 double *x,
01074 double testtol,
01075 int maxcuts,
01076 double *viol,
01077 CCrandstate * rstate),
01078 CCtsp_cliquetree_lp (CCtsp_lpcuts * cuts,
01079 CCtsp_tighten_info * stats,
01080 CCtsp_lpcut_in ** cutsout,
01081 int *cutcount,
01082 int ncount,
01083 int ecount,
01084 int *elist,
01085 double *x,
01086 double testtol,
01087 int maxcuts,
01088 double *viol,
01089 CCrandstate * rstate),
01090 CCtsp_star_lp (CCtsp_lpcuts * cuts,
01091 CCtsp_tighten_info * stats,
01092 CCtsp_lpcut_in ** cutsout,
01093 int *cutcount,
01094 int ncount,
01095 int ecount,
01096 int *elist,
01097 double *x,
01098 double testtol,
01099 int maxcuts,
01100 double *viol,
01101 CCrandstate * rstate),
01102 CCtsp_handling_lp (CCtsp_lpcuts * cuts,
01103 CCtsp_tighten_info * stats,
01104 CCtsp_lpcut_in ** cutsout,
01105 int *cutcount,
01106 int ncount,
01107 int ecount,
01108 int *elist,
01109 double *x,
01110 double testtol,
01111 int maxcuts,
01112 double *viol,
01113 CCrandstate * rstate),
01114 CCtsp_teething_lp (CCtsp_lpcuts * cuts,
01115 CCtsp_tighten_info * stats,
01116 CCtsp_lpcut_in ** cutsout,
01117 int *cutcount,
01118 int ncount,
01119 int ecount,
01120 int *elist,
01121 double *x,
01122 double testtol,
01123 int maxcuts,
01124 double *viol,
01125 CCrandstate * rstate),
01126 CCtsp_domino_trial (CCtsp_lpcut_in ** cuts,
01127 int *cutcount,
01128 int ncount,
01129 int ecount,
01130 int *elist,
01131 double *x,
01132 CCrandstate * rstate),
01133 CCtsp_file_cuts (char *cutfile,
01134 CCtsp_lpcut_in ** cuts,
01135 int *cutcount,
01136 int ncount,
01137 int *tour),
01138 CCtsp_file_cuts_write (const char *cutfile,
01139 CCtsp_lpcuts * cuts,
01140 int *tour),
01141 CCtsp_test_pure_comb (int ncount,
01142 CCtsp_lpcut_in * c,
01143 int *yes_no,
01144 int *handle),
01145 CCtsp_test_pseudocomb (int ncount,
01146 CCtsp_lpcut_in * c,
01147 int handle,
01148 int *yes_no),
01149 CCtsp_test_teeth_disjoint (int ncount,
01150 CCtsp_lpcut_in * c,
01151 int handle,
01152 int *yes_no),
01153 CCtsp_find_pure_handle (int ncount,
01154 CCtsp_lpcut_in * c,
01155 int *handle),
01156 CCtsp_truncate_cutlist (CCtsp_lpcut_in ** cuts,
01157 int ncount,
01158 int ecount,
01159 int *elist,
01160 double *x,
01161 int maxcuts,
01162 CCrandstate * rstate),
01163 CCtsp_buildcut_begin (CCtsp_cutinfo * cuts,
01164 int init_cliquecount),
01165 CCtsp_buildcut_addclique (CCtsp_cutinfo * cuts,
01166 int *arr,
01167 int size),
01168 CCtsp_buildcut_finish (CCtsp_cutinfo * cuts,
01169 int rhs),
01170 CCtsp_new_domino (CCtsp_lpcut_in ** cuts,
01171 int *cutcount,
01172 int ncount,
01173 int ecount,
01174 int *elist,
01175 double *x,
01176 const char *bossname);
01177
01178 void CCtsp_buildcut_abort (CCtsp_cutinfo * cuts);
01179
01180
01181
01182
01183
01184
01185
01186
01187
01188 #define CCtsp_POOL_GETCUTS 'G'
01189 #define CCtsp_POOL_PUTCUTS 'P'
01190 #define CCtsp_POOL_SAVECUTS 'S'
01191 #define CCtsp_POOL_EXIT 'X'
01192
01193
01194 int CCtsp_init_cutpool (int *ncount,
01195 char *poolfilename,
01196 CCtsp_lpcuts ** pool),
01197 CCtsp_write_cutpool (int ncount,
01198 const char *poolfilename,
01199 CCtsp_lpcuts * pool),
01200 CCtsp_search_cutpool (CCtsp_lpcuts * pool,
01201 CCtsp_lpcut_in ** cuts,
01202 int *cutcount,
01203 double *maxviol,
01204 int ncount,
01205 int ecount,
01206 int *elist,
01207 double *x,
01208 int nthreads,
01209 CCrandstate * rstate),
01210 CCtsp_search_remotepool (char *remotehost,
01211 unsigned short remoteport,
01212 CCtsp_lpcut_in ** cuts,
01213 int *cutcount,
01214 double *maxviol,
01215 int ncount,
01216 int ecount,
01217 int *elist,
01218 double *x),
01219 CCtsp_read_cuts (CC_SFILE * f,
01220 int *ncount,
01221 CCtsp_lpcuts * cuts,
01222 int readmods,
01223 int buildhash),
01224 CCtsp_read_lpcut_in (CC_SFILE * f,
01225 CCtsp_lpcut_in * c,
01226 int ncount),
01227 CCtsp_read_lpclique (CC_SFILE * f,
01228 CCtsp_lpclique * c,
01229 int ncount),
01230 CCtsp_read_lpdomino (CC_SFILE * f,
01231 CCtsp_lpdomino * d,
01232 int ncount),
01233 CCtsp_write_cuts (CC_SFILE * f,
01234 int ncount,
01235 CCtsp_lpcuts * cuts,
01236 int writemods),
01237 CCtsp_send_newcuts (int ncount,
01238 CCtsp_lpcuts * pool,
01239 char *remotehost,
01240 unsigned short remoteport),
01241 CCtsp_write_lpcut_in (CC_SFILE * f,
01242 CCtsp_lpcut_in * c,
01243 int ncount),
01244 CCtsp_write_lpcut (CC_SFILE * f,
01245 CCtsp_lpcuts * cuts,
01246 CCtsp_lpcut * c,
01247 int ncount),
01248 CCtsp_write_lpclique (CC_SFILE * f,
01249 CCtsp_lpclique * c,
01250 int ncount),
01251 CCtsp_write_lpdomino (CC_SFILE * f,
01252 CCtsp_lpdomino * c,
01253 int ncount),
01254 CCtsp_copy_cuts (CC_SFILE * f,
01255 CC_SFILE * t,
01256 int copymods),
01257 CCtsp_search_cutpool_cliques (CCtsp_lpcuts * pool,
01258 CCtsp_lpclique ** cliques,
01259 int *cliquecount,
01260 int ncount,
01261 int ecount,
01262 int *elist,
01263 double *x,
01264 double maxdelta,
01265 int maxcliques,
01266 double **cliquevals,
01267 CCrandstate * rstate),
01268 CCtsp_branch_cutpool_cliques (CCtsp_lpcuts * pool,
01269 CCtsp_lpclique ** cliques,
01270 int *cliquecount,
01271 int ncount,
01272 int ecount,
01273 int *elist,
01274 double *x,
01275 int nwant,
01276 double **cliquevals,
01277 int silent),
01278 CCtsp_get_clique_prices (CCtsp_lpcuts * pool,
01279 int **p_cliquenums,
01280 double **p_cliquevals,
01281 double mindelta,
01282 double maxdelta,
01283 int *p_cliquecount,
01284 int ncount,
01285 int ecount,
01286 int *elist,
01287 double *x),
01288 CCtsp_get_clique (CCtsp_lpcuts * pool,
01289 int cliquenum,
01290 CCtsp_lpclique ** p_clique),
01291 CCtsp_add_to_cutpool (CCtsp_lpcuts * pool,
01292 CCtsp_lpcuts * cuts,
01293 CCtsp_lpcut * c),
01294 CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts * pool,
01295 CCtsp_lpcut_in * cut),
01296 CCtsp_display_cutpool (CCtsp_lpcuts * pool),
01297 CCtsp_price_cuts (CCtsp_lpcuts * pool,
01298 int ncount,
01299 int ecount,
01300 int *elist,
01301 double *x,
01302 double *cutval),
01303 CCtsp_price_cuts_threaded (CCtsp_lpcuts * pool,
01304 int ncount,
01305 int ecount,
01306 int *elist,
01307 double *x,
01308 double *cutval,
01309 int numthreads),
01310 CCtsp_register_cliques (CCtsp_lpcuts * cuts,
01311 CCtsp_lpcut_in * c,
01312 CCtsp_lpcut * new),
01313 CCtsp_register_dominos (CCtsp_lpcuts * cuts,
01314 CCtsp_lpcut_in * c,
01315 CCtsp_lpcut * new),
01316 CCtsp_add_cut_to_cutlist (CCtsp_lpcuts * cuts,
01317 CCtsp_lpcut * c);
01318
01319 void CCtsp_free_cutpool (CCtsp_lpcuts ** pool),
01320 CCtsp_free_lpcut_in (CCtsp_lpcut_in * c),
01321 CCtsp_free_lpclique (CCtsp_lpclique * c),
01322 CCtsp_free_lpdomino (CCtsp_lpdomino * c),
01323 CCtsp_unregister_cliques (CCtsp_lpcuts * cuts,
01324 CCtsp_lpcut * c),
01325 CCtsp_unregister_dominos (CCtsp_lpcuts * cuts,
01326 CCtsp_lpcut * c),
01327 CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts * cuts,
01328 int ind);
01329
01330
01331
01332
01333
01334
01335
01336
01337
01338 int CCtsp_test_pure_double_decker (CCtsp_lpcut_in * c,
01339 int *yes_no,
01340 int *handle1,
01341 int *handle2),
01342 CCtsp_comb_to_double_decker (CCtsp_lpgraph * g,
01343 CC_GCgraph * h,
01344 double *x,
01345 CCtsp_lpcut_in * c,
01346 CCtsp_lpcut_in ** d),
01347 CCtsp_comb_to_star (CCtsp_lpgraph * g,
01348 CC_GCgraph * h,
01349 double *x,
01350 CCtsp_lpcut_in * c,
01351 CCtsp_lpcut_in ** d),
01352 CCtsp_test_pure_simple_cliquetree (int ncount,
01353 CCtsp_lpcut_in * c,
01354 int *yes_no),
01355 CCtsp_comb_to_cliquetree (CCtsp_lpgraph * g,
01356 CC_GCgraph * h,
01357 double *x,
01358 CCtsp_lpcut_in * c,
01359 CCtsp_lpcut_in ** d),
01360 CCtsp_comb_handling (CCtsp_lpgraph * g,
01361 CC_GCgraph * h,
01362 double *x,
01363 CCtsp_lpcut_in * c,
01364 CCtsp_lpcut_in ** d);
01365
01366
01367
01368
01369
01370
01371
01372
01373
01374
01375 int CCtsp_exact_price (CCtsp_lp * lp,
01376 CCbigguy * bound,
01377 int complete_price,
01378 int phase1,
01379 int silent),
01380 CCtsp_edge_elimination (CCtsp_lp * lp,
01381 int eliminate_sparse,
01382 int silent),
01383 CCtsp_exact_dual (CCtsp_lp * lp),
01384 CCtsp_verify_infeasible_lp (CCtsp_lp * lp,
01385 int *yesno,
01386 int silent),
01387 CCtsp_verify_lp_prune (CCtsp_lp * lp,
01388 int *yesno,
01389 int silent);
01390
01391 void CCtsp_free_bigdual (CCtsp_bigdual ** d);
01392
01393
01394
01395
01396
01397
01398
01399
01400
01401 #define CCtsp_PRICE_COMPLETE_GRAPH -1
01402 #define CCtsp_GEN_PRICE_EPSILON 0.0001
01403 #define CCtsp_GEN_USE_ADJ 50
01404
01405
01406 void CCtsp_free_edgegenerator (CCtsp_edgegenerator * eg);
01407
01408 int CCtsp_init_edgegenerator (CCtsp_edgegenerator * eg,
01409 int ncount,
01410 CCdatagroup * dg,
01411 CCtsp_genadj * adj,
01412 int nneighbors,
01413 int silent,
01414 CCrandstate * rstate),
01415 CCtsp_reset_edgegenerator (CCtsp_edgegenerator * eg,
01416 double *node_piest,
01417 int silent),
01418 CCtsp_generate_edges (CCtsp_edgegenerator * eg,
01419 int nwant,
01420 int *pngot,
01421 int *elist,
01422 int *elen,
01423 int *finished,
01424 int silent,
01425 CCrandstate * rstate),
01426 CCtsp_edgelist_to_genadj (int ncount,
01427 int ecount,
01428 int *elist,
01429 int *elen,
01430 CCtsp_genadj ** adj,
01431 CCtsp_genadjobj ** adjobjspace);
01432
01433
01434
01435
01436
01437
01438
01439
01440
01441
01442 int CCtsp_edge_comb_grower (CCtsp_lpcut_in ** cuts,
01443 int *cutcount,
01444 int ncount,
01445 int ecount,
01446 int *elist,
01447 double *x,
01448 CCtsp_tighten_info * stats);
01449
01450
01451
01452
01453
01454
01455
01456
01457
01458
01459 int CCtsp_pr_cliquetree (CCtsp_lpcut_in ** cuts,
01460 int *cutcount,
01461 int ncount,
01462 int ecount,
01463 int *elist,
01464 double *x,
01465 CCtsp_tighten_info * stats);
01466
01467
01468
01469
01470
01471
01472
01473
01474
01475 #define CCtsp_PROB_FILE_NAME_LEN 128
01476
01477 #define CCtsp_Pdelete 'D'
01478 #define CCtsp_Pread 'R'
01479 #define CCtsp_Pwrite 'W'
01480 #define CCtsp_Pmaster 'M'
01481 #define CCtsp_Pexit 'X'
01482 #define CCtsp_Pcuts 'c'
01483 #define CCtsp_Pdual 'd'
01484 #define CCtsp_Pedges 'e'
01485 #define CCtsp_Pfixed 'f'
01486 #define CCtsp_Pfull 'g'
01487 #define CCtsp_Pheader 'h'
01488 #define CCtsp_Phistory 'i'
01489 #define CCtsp_Ptour 't'
01490 #define CCtsp_Pwarmstart 'w'
01491
01492 typedef struct CCtsp_PROB_FILE
01493 {
01494 CC_SFILE *f;
01495 int type;
01496 char name[CCtsp_PROB_FILE_NAME_LEN];
01497 int id;
01498 int parent;
01499 double ub;
01500 double lb;
01501 CCbigguy exactlb;
01502 int nnodes;
01503 int child0;
01504 int child1;
01505 int real;
01506 int processed;
01507 int infeasible;
01508 struct
01509 {
01510 int dat;
01511 int edge;
01512 int fulladj;
01513 int cut;
01514 int tour;
01515 int basis;
01516 int norms;
01517 int fix;
01518 int exactdual;
01519 int history;
01520 int warmstart;
01521 }
01522 offsets;
01523 }
01524 CCtsp_PROB_FILE;
01525
01526
01527 CCtsp_PROB_FILE *CCtsp_prob_read (char *f,
01528 int n),
01529 *CCtsp_prob_read_name (char *f),
01530 *CCtsp_prob_write (char *f,
01531 int n),
01532 *CCtsp_prob_write_name (char *fname);
01533
01534 int CCtsp_prob_file_delete (char *f,
01535 int n),
01536 CCtsp_prob_getname (CCtsp_PROB_FILE * p,
01537 char *name),
01538 CCtsp_prob_getid (CCtsp_PROB_FILE * p,
01539 int *id),
01540 CCtsp_prob_getparent (CCtsp_PROB_FILE * p,
01541 int *parent),
01542 CCtsp_prob_getub (CCtsp_PROB_FILE * p,
01543 double *ub),
01544 CCtsp_prob_getlb (CCtsp_PROB_FILE * p,
01545 double *lb),
01546 CCtsp_prob_getexactlb (CCtsp_PROB_FILE * p,
01547 CCbigguy * lb),
01548 CCtsp_prob_getnnodes (CCtsp_PROB_FILE * p,
01549 int *nnodes),
01550 CCtsp_prob_getchildren (CCtsp_PROB_FILE * p,
01551 int *child0,
01552 int *child1),
01553 CCtsp_prob_getreal (CCtsp_PROB_FILE * p,
01554 int *real),
01555 CCtsp_prob_getprocessed (CCtsp_PROB_FILE * p,
01556 int *processed),
01557 CCtsp_prob_getinfeasible (CCtsp_PROB_FILE * p,
01558 int *infeasible),
01559 CCtsp_prob_gettour (CCtsp_PROB_FILE * p,
01560 int ncount,
01561 int **tour,
01562 int silent),
01563 CCtsp_prob_getedges (CCtsp_PROB_FILE * p,
01564 int ncount,
01565 int *nedges,
01566 int **elist,
01567 int **elen,
01568 int silent),
01569 CCtsp_prob_getcuts (CCtsp_PROB_FILE * p,
01570 int *ncount,
01571 CCtsp_lpcuts * cuts,
01572 int silent),
01573 CCtsp_prob_getwarmstart (CCtsp_PROB_FILE * p,
01574 CClp_warmstart ** w,
01575 int silent),
01576 CCtsp_prob_getfulladj (CCtsp_PROB_FILE * p,
01577 int ncount,
01578 int *fullcount,
01579 CCtsp_genadj ** adj,
01580 CCtsp_genadjobj ** adjspace,
01581 int silent),
01582 CCtsp_prob_getfixed (CCtsp_PROB_FILE * p,
01583 int ncount,
01584 int *ecount,
01585 int **elist,
01586 int silent),
01587 CCtsp_prob_getexactdual (CCtsp_PROB_FILE * p,
01588 int ncount,
01589 CCtsp_bigdual ** d,
01590 int silent),
01591 CCtsp_prob_gethistory (CCtsp_PROB_FILE * p,
01592 int *depth,
01593 CCtsp_branchobj ** history,
01594 int silent),
01595 CCtsp_prob_rclose (CCtsp_PROB_FILE * p),
01596 CCtsp_prob_putname (CCtsp_PROB_FILE * p,
01597 char *name),
01598 CCtsp_prob_putid (CCtsp_PROB_FILE * p,
01599 int id),
01600 CCtsp_prob_putparent (CCtsp_PROB_FILE * p,
01601 int parent),
01602 CCtsp_prob_putub (CCtsp_PROB_FILE * p,
01603 double ub),
01604 CCtsp_prob_putlb (CCtsp_PROB_FILE * p,
01605 double lb),
01606 CCtsp_prob_putexactlb (CCtsp_PROB_FILE * p,
01607 CCbigguy lb),
01608 CCtsp_prob_putnnodes (CCtsp_PROB_FILE * p,
01609 int nnodes),
01610 CCtsp_prob_putchildren (CCtsp_PROB_FILE * p,
01611 int child0,
01612 int child1),
01613 CCtsp_prob_putreal (CCtsp_PROB_FILE * p,
01614 int real),
01615 CCtsp_prob_putprocessed (CCtsp_PROB_FILE * p,
01616 int processed),
01617 CCtsp_prob_putinfeasible (CCtsp_PROB_FILE * p,
01618 int infeasible),
01619 CCtsp_prob_puttour (CCtsp_PROB_FILE * p,
01620 int ncount,
01621 int *tour),
01622 CCtsp_prob_putedges (CCtsp_PROB_FILE * p,
01623 int ncount,
01624 int nedges,
01625 int *elist,
01626 int *elen),
01627 CCtsp_prob_putcuts (CCtsp_PROB_FILE * p,
01628 int ncount,
01629 CCtsp_lpcuts * cuts),
01630 CCtsp_prob_putwarmstart (CCtsp_PROB_FILE * p,
01631 CClp_warmstart * w),
01632 CCtsp_prob_putfulladj (CCtsp_PROB_FILE * p,
01633 int ncount,
01634 int fullcount,
01635 CCtsp_genadj * adj),
01636 CCtsp_prob_putfixed (CCtsp_PROB_FILE * p,
01637 int ncount,
01638 int ecount,
01639 int *elist),
01640 CCtsp_prob_putexactdual (CCtsp_PROB_FILE * p,
01641 CCtsp_bigdual * d,
01642 int ncount),
01643 CCtsp_prob_puthistory (CCtsp_PROB_FILE * p,
01644 int depth,
01645 CCtsp_branchobj * history),
01646 CCtsp_prob_wclose (CCtsp_PROB_FILE * p),
01647 CCtsp_prob_copy_section (CCtsp_PROB_FILE * f,
01648 CCtsp_PROB_FILE * t,
01649 char section,
01650 int silent);
01651
01652 char *CCtsp_problabel (const char *probloc);
01653
01654 #ifdef CC_NETREADY
01655 CCtsp_PROB_FILE *CCtsp_prob_read_remote (char *hname,
01656 char *pname,
01657 int n),
01658 *CCtsp_prob_write_remote (char *hname,
01659 char *pname,
01660 int n),
01661 *CCtsp_prob_server (CC_SFILE * s);
01662
01663 int CCtsp_prob_delete_remote (char *hname,
01664 char *pname,
01665 int n);
01666 #endif
01667
01668
01669
01670
01671
01672
01673
01674
01675
01676
01677 typedef struct CCtsp_qsparsegroup
01678 {
01679 CCdheap *add_queue;
01680 CCdheap *sub_queue;
01681 int *count_m1;
01682 int *count_non0;
01683 int *count_1;
01684 int *on_add_queue;
01685 int *on_sub_queue;
01686 int *mults;
01687 }
01688 CCtsp_qsparsegroup;
01689
01690
01691 void CCtsp_free_qsparsify (CCtsp_qsparsegroup ** pqs);
01692
01693 int CCtsp_qsparsify (CCtsp_qsparsegroup ** pqs,
01694 struct CCtsp_lpgraph *g,
01695 int *pnzlist,
01696 int *scount,
01697 struct CCtsp_sparser **slist,
01698 int *savedcount);
01699
01700
01701
01702
01703
01704
01705
01706
01707
01708 int CCtsp_copy_skeleton (CCtsp_skeleton * old,
01709 CCtsp_skeleton * new),
01710 CCtsp_construct_skeleton (CCtsp_lpcut_in * c,
01711 int nodecount),
01712 CCtsp_read_skeleton (CC_SFILE * f,
01713 CCtsp_skeleton * skel,
01714 int ncount),
01715 CCtsp_write_skeleton (CC_SFILE * f,
01716 CCtsp_skeleton * skel,
01717 int ncount);
01718
01719 void CCtsp_init_skeleton (CCtsp_skeleton * skel),
01720 CCtsp_free_skeleton (CCtsp_skeleton * skel),
01721 CCtsp_compare_skeletons (CCtsp_skeleton * a,
01722 CCtsp_skeleton * b,
01723 int *diff);
01724
01725
01726
01727
01728
01729
01730
01731
01732
01733
01734 int CCtsp_teething (CCtsp_lpgraph * g,
01735 double *x,
01736 CCtsp_lpcut_in * cut,
01737 CCtsp_lpcut_in ** newcut),
01738 CCtsp_teething_list (CCtsp_lpgraph * g,
01739 double *x,
01740 CCtsp_lpclique * handle,
01741 int nbig,
01742 CCtsp_lpclique ** bigteeth,
01743 CCtsp_lpcut_in ** newcut);
01744
01745
01746
01747
01748
01749
01750
01751
01752
01753
01754 int CCtsp_tighten_lpcut_in (CCtsp_lpgraph * g,
01755 CCtsp_lpcut_in * c,
01756 double *x,
01757 CCtsp_lpcut_in * d,
01758 CCtsp_tighten_info * stats,
01759 double *pimprove),
01760 CCtsp_tighten_lpcut (CCtsp_lpgraph * g,
01761 CCtsp_lpclique * cliques,
01762 CCtsp_lpcut * c,
01763 double *x,
01764 CCtsp_lpcut_in * d,
01765 CCtsp_tighten_info * stats,
01766 double *pimprove);
01767
01768 void CCtsp_init_tighten_info (CCtsp_tighten_info * stats),
01769 CCtsp_print_tighten_info (CCtsp_tighten_info * stats);
01770
01771
01772
01773
01774
01775
01776
01777
01778
01779 int CCtsp_bb_init_lp (CCtsp_lp ** lp,
01780 char *probname,
01781 int probnum,
01782 int ncount,
01783 CCdatagroup * dat,
01784 int *ptour,
01785 double initial_ub,
01786 CCtsp_lpcuts * pool,
01787 int silent,
01788 CCrandstate * rstate),
01789 CCtsp_init_lp (CCtsp_lp ** lp,
01790 char *probname,
01791 int probnum,
01792 char *probfilename,
01793 int ncount,
01794 CCdatagroup * dat,
01795 int ecount,
01796 int *elist,
01797 int *elen,
01798 int excount,
01799 int *exlist,
01800 int *exlen,
01801 int exvalid,
01802 int *ptour,
01803 double initial_ub,
01804 CCtsp_lpcuts * pool,
01805 int silent,
01806 CCrandstate * rstate),
01807 CCtsp_build_lpgraph (CCtsp_lpgraph * g,
01808 int ncount,
01809 int ecount,
01810 int *elist,
01811 int *elen),
01812 CCtsp_build_lpadj (CCtsp_lpgraph * g,
01813 int estart,
01814 int eend),
01815 CCtsp_find_edge (CCtsp_lpgraph * g,
01816 int from,
01817 int to),
01818 CCtsp_inspect_full_edges (CCtsp_lp * lp),
01819 CCtsp_resparsify_lp (CCtsp_lp * lp,
01820 int silent),
01821 CCtsp_lpcut_nzlist (CCtsp_lpgraph * g,
01822 CCtsp_lpcut * c,
01823 CCtsp_lpclique * cliques,
01824 CCtsp_lpdomino * dominos,
01825 int do_mods),
01826 CCtsp_update_result (CCtsp_lp * lp),
01827 CCtsp_get_lp_result (CCtsp_lp * lp,
01828 double *lb,
01829 double *ub,
01830 int *ecount,
01831 int **elist,
01832 double **x,
01833 double **rc,
01834 double **node_pi,
01835 double **cut_pi),
01836 CCtsp_lpcut_in_nzlist (CCtsp_lpgraph * g,
01837 CCtsp_lpcut_in * c),
01838 CCtsp_process_cuts (CCtsp_lp * lp,
01839 int *pnadded,
01840 int tighten,
01841 int silent,
01842 CCrandstate * rstate),
01843 CCtsp_infeas_recover (CCtsp_lp * lp,
01844 int silent,
01845 CCrandstate * rstate),
01846 CCtsp_add_cut (CCtsp_lp * lp,
01847 CCtsp_lpcut_in * d,
01848 CCtsp_lprow * cr),
01849 CCtsp_add_nzlist_to_lp (CCtsp_lp * lp,
01850 int nzlist,
01851 int rhs,
01852 char sense,
01853 CCtsp_lprow * cr),
01854 CCtsp_addbad_variables (CCtsp_lp * lp,
01855 CCtsp_edgegenerator * eg,
01856 double *ppenalty,
01857 int *pnadded,
01858 double rcthresh,
01859 double maxpenalty,
01860 int phase1,
01861 int *feasible,
01862 int silent,
01863 CCrandstate * rstate),
01864 CCtsp_eliminate_variables (CCtsp_lp * lp,
01865 int eliminate_sparse,
01866 int silent),
01867 CCtsp_add_vars_to_lp (CCtsp_lp * lp,
01868 CCtsp_predge * prlist,
01869 int n),
01870 CCtsp_add_multiple_rows (CCtsp_lp * lp,
01871 CCtsp_lprow * cr),
01872 CCtsp_delete_cut (CCtsp_lp * lp,
01873 int i),
01874 CCtsp_reduced_cost_nearest (CCtsp_lp * lp,
01875 int k,
01876 int *ecount,
01877 int **elist,
01878 double **elen,
01879 int sparse),
01880 CCtsp_write_probfile_sav (CCtsp_lp * lp),
01881 CCtsp_write_probfile_id (CCtsp_lp * lp),
01882 CCtsp_write_probroot_id (char *probloc,
01883 CCtsp_lp * lp),
01884 CCtsp_write_probleaf_id (CCtsp_lp * lp),
01885 CCtsp_read_probfile (CCtsp_lp * lp,
01886 char *fname,
01887 char *probloc,
01888 int *ncount,
01889 int silent),
01890 CCtsp_read_probfile_id (CCtsp_lp * lp,
01891 char *fname,
01892 int id,
01893 int *ncount,
01894 int silent),
01895 CCtsp_dump_rc_nearest (CCtsp_lp * lp,
01896 int k,
01897 char *fname,
01898 int sparse),
01899 CCtsp_dump_x (CCtsp_lp * lp,
01900 char *fname),
01901 CCtsp_depot_valid (CCtsp_lp * lp,
01902 int ndepot,
01903 int *yesno);
01904
01905 double CCtsp_cutprice (CCtsp_lpgraph * g,
01906 CCtsp_lpcut_in * c,
01907 double *x);
01908
01909 void CCtsp_init_tsp_lpcuts_struct (CCtsp_lpcuts * c),
01910 CCtsp_init_tsp_lp_struct (CCtsp_lp * lp),
01911 CCtsp_free_tsp_lp_struct (CCtsp_lp ** lp),
01912 CCtsp_init_lpgraph_struct (CCtsp_lpgraph * g),
01913 CCtsp_free_lpgraph (CCtsp_lpgraph * g),
01914 CCtsp_init_statistics (CCtsp_statistics * stats),
01915 CCtsp_output_statistics (CCtsp_statistics * stats),
01916 CCtsp_add_cuts_to_queue (CCtsp_lp * lp,
01917 CCtsp_lpcut_in ** c),
01918 CCtsp_init_lprow (CCtsp_lprow * cr),
01919 CCtsp_free_lprow (CCtsp_lprow * cr);
01920
01921
01922
01923
01924
01925
01926
01927
01928 int CCtsp_solve_sparse (int ncount,
01929 int ecount,
01930 int *elist,
01931 int *elen,
01932 int *in_tour,
01933 int *out_tour,
01934 double *in_val,
01935 double *optval,
01936 int *success,
01937 int *foundtour,
01938 char *name,
01939 double *timebound,
01940 int *hit_timebound,
01941 int silent,
01942 CCrandstate * rstate),
01943 CCtsp_solve_dat (int ncount,
01944 CCdatagroup * indat,
01945 int *in_tour,
01946 int *out_tour,
01947 double *in_val,
01948 double *optval,
01949 int *success,
01950 int *foundtour,
01951 char *name,
01952 double *timebound,
01953 int *hit_timebound,
01954 int silent,
01955 CCrandstate * rstate);
01956
01957
01958
01959
01960
01961
01962
01963
01964
01965
01966 int CCtsp_x_greedy_tour (CCdatagroup * dat,
01967 int ncount,
01968 int ecount,
01969 int *elist,
01970 double *x,
01971 int *cyc,
01972 double *val,
01973 int silent),
01974 CCtsp_x_greedy_tour_lk (CCdatagroup * dat,
01975 int ncount,
01976 int ecount,
01977 int *elist,
01978 double *x,
01979 int *cyc,
01980 double *val,
01981 int silent,
01982 CCrandstate * rstate);
01983
01984
01985
01986
01987
01988
01989
01990
01991 #define CCtsp_DOMINO_WORK 'A'
01992 #define CCtsp_DOMINO_GRAPH 'G'
01993 #define CCtsp_DOMINO_NO 'N'
01994 #define CCtsp_DOMINO_RECEIVE 'R'
01995 #define CCtsp_DOMINO_SEND 'S'
01996 #define CCtsp_DOMINO_WAIT 'W'
01997 #define CCtsp_DOMINO_YES 'Y'
01998 #define CCtsp_DOMINO_EXIT 'X'
01999
02000 #endif
