Concorde tsp.h functions
CCtsp_x_greedy_tour
File:
TSP/xtour.c
Header:
tsp.h
Prototype:
int CCtsp_x_greedy_tour (CCdatagroup *dat, int ncount, int ecount,
int *elist, double *x, int *cyc, double *val, int silent)
Description:
FINDS a tour by adding in edges by nonincreasing x-value.
-cyc should be an array of length at least ncount
-val returns the length of the tour
CCtsp_x_greedy_tour_lk
File:
TSP/xtour.c
Header:
tsp.h
Prototype:
int CCtsp_x_greedy_tour_lk (CCdatagroup *dat, int ncount, int ecount,
int *elist, double *x, int *cyc, double *val, int silent,
CCrandstate *rstate)
Description:
FINDS the x-greedy tour then calls a short LK.
CCtsp_init_tsp_lp_struct
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_init_tsp_lp_struct (CCtsp_lp *lp)
Description:
INITIALIZES the CCtsp_lp struture with NULL values
CCtsp_free_tsp_lp_struct
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_free_tsp_lp_struct (CCtsp_lp **lp)
Description:
free a CCtsp_lp
CCtsp_init_lp
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_init_lp (CCtsp_lp **lp, char *probloc, int probnum,
char *probfilename, int ncount, CCdatagroup *dat, int ecount,
int *elist, int *elen, int excount, int *exlist, int *exlen,
int exvalid, int *ptour, double initial_ub,
CCtsp_lpcuts *pool, int silent, CCrandstate *rstate)
Description:
BUILDS/READS the problem, and loads it into the LP solver. If
probnum < 0, init_lp will build an initial problem according to
elist and elen; otherwise it will read the problem from disk. If
the problem is read from disk, then the elist is ignored.
-lp is a handle to the tsp lp (filled in by init_lp)
-probname is the name for the problem
-probnum is the number for the problem
-ncount is the number of nodes
-dat is a handle on the complete graph
-ecount, elist, elen specify an initial edge set; if a prob is
read from a file, then this list is ignored
-excount, exlist, exlen specify an full edge set (they can be
0, NULL, NULL); if the probfile already has an full edge set,
then this values are ignored.
-exvalid indicates whether or not the edges specified in exlist
are a valid complete set of edges (0 no, 1 yes)
-pool is a pointer to a cutpool (can be NULL)
-silent will suppress print messages if set to a nonzero value
NOTES: If init_lp returns 2, then the LP is infeasible (even after
considering the full edge set).
CCtsp_bb_init_lp
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_bb_init_lp (CCtsp_lp **lp, char *probname, int probnum,
int ncount, CCdatagroup *dat, int *ptour, double initial_ub,
CCtsp_lpcuts *pool, int silent, CCrandstate *rstate)
Description:
SHORT form of CCtsp_init_lp for use in the branch and bound.
CCtsp_get_lp_result
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_get_lp_result (CCtsp_lp *lp, double *lb, double *ub,
int *ecount, int **elist, double **x, double **rc,
double **node_pi, double **cut_pi)
Description:
RETURNS a copy of the values cached in lp->result. However, it
allows a single point of locking for the threaded version. Any
return argument can be NULL.
-lp is a pointer to the tsp lp
-obj returns the location for the current objective value
-ecount returns the location for the number of nonzero edges
-elist returns the location for the nonzero edges in end1 end2
format
-x returns location for the edge values
-rc returns location for the edge values
-node_pi returns the values on the degree constraints
-cut_pi returns the dual values on the cuts
NOTES: node_pi and cut_pi go to the LP to fetch the results.
CCtsp_lpcut_in_nzlist
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_lpcut_in_nzlist (CCtsp_lpgraph *g, CCtsp_lpcut_in *c)
Description:
MISSING
CCtsp_add_cut
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_add_cut (CCtsp_lp *lp, CCtsp_lpcut_in *d, CCtsp_lprow *cr)
Description:
ADDS cut d to the lp structure and to cr (a call to
CCtsp_add_multiple will put the cut into the lp solver)
CCtsp_add_nzlist_to_lp
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_add_nzlist_to_lp (CCtsp_lp *lp, int nzlist, int nrhs,
char sense, CCtsp_lprow *cr)
Description:
MISSING
CCtsp_add_multiple_rows
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_add_multiple_rows (CCtsp_lp *lp, CCtsp_lprow *cr)
Description:
HANDS the cuts in cr to the lp solver.
CCtsp_delete_cut
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_delete_cut (CCtsp_lp *lp, int i)
Description:
MISSING
CCtsp_write_probfile_sav
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_write_probfile_sav (CCtsp_lp *lp)
Description:
MISSING
CCtsp_write_probfile_id
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_write_probfile_id (CCtsp_lp *lp)
Description:
MISSING
CCtsp_write_probroot_id
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_write_probroot_id (char *probloc, CCtsp_lp *lp)
Description:
MISSING
CCtsp_add_cuts_to_queue
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_add_cuts_to_queue (CCtsp_lp *lp, CCtsp_lpcut_in **clist)
Description:
ADDS clist to the queue of cuts to be processed by the lp solver;
clist will be set to NULL
-lp is a pointer to the tsp lp
-clist is the head of a NULL terminated linked list of cuts
CCtsp_process_cuts
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_process_cuts (CCtsp_lp *lp, int *pnadded, int tighten,
int silent, CCrandstate *rstate)
Description:
-lp is a pointer to the tsp lp
-pnadded returns the location for the number of cuts added
-tighten is a flag to indicate whether or not the tighten routine
should be called for each cut before it is added to the LP
NOTES: process_cuts runs through all the cuts in the queue;
process_cuts also calls add_to_cutpool(). If process_cuts
returns 2, then the LP is infeasible, even after considering
the full edge set.
CCtsp_addbad_variables
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_addbad_variables (CCtsp_lp *lp, CCtsp_edgegenerator *eg,
double *ppenalty, int *pnadded, double rcthresh,
double maxpenalty, int phase1, int *feasible, int silent,
CCrandstate *rstate)
Description:
ADDS negative reduced cost edges to the LP; if phase1 is nonzero
then the added edges attempt to make a feasible LP (in this
case the eg variable is ignored and the edges are taked either
from fulladj (if they are valid) or from dat)
-lp is a pointer to the tsp lp
-eg is a generator for the edges to check
-ppenalty is the penalty from the last pass of pricing
-pnadded is the number of negative reduced cost edges added
-rcthresh is the threshold on the reduced cost of edges to be
added (it should be something <= 0.0)
-maxpenalty is the maximum sum of penalties that is permitted
before the rounds of pricing stop
-phase1 should be 0 for normal column generation, and nonzero
to try to fix an infeasible LP
-feasible can be NULL, otherwise it is set to 1 if phase 1
gets to a feasible LP and 0 if the LP really is infeasible
CCtsp_eliminate_variables
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_eliminate_variables (CCtsp_lp *lp, int eliminate_sparse,
int silent)
Description:
SETS edges to 0 or 1 if possible, based on reduced costs
-lp is a pointer to the tsp lp
-if eliminate_sparse is nonzero and the full edge list in lp is
present and valid, eliminate variables from that list. Otherwise
eliminate from the complete graph
CCtsp_cutprice
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
double CCtsp_cutprice (CCtsp_lpgraph *g, CCtsp_lpcut_in *c,
double *x)
Description:
RETURNS the slack of cut c
-g is a pointer to an CCtsp_lpgraph that matches the vector x
CCtsp_add_vars_to_lp
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_add_vars_to_lp (CCtsp_lp *lp, CCtsp_predge *prlist, int n)
Description:
ADDS the columns to the lp.
-n the number of edges listed in prlist
CCtsp_update_result
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_update_result (CCtsp_lp *lp)
Description:
UPDATES the solution information in the lp structure
CCtsp_infeas_recover
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_infeas_recover (CCtsp_lp *lp, int silent,
CCrandstate *rstate)
Description:
TRIES to add columns to lp to regain feasibiblity
NOTES: Returns 2 if the full lp is infeasible
CCtsp_build_lpgraph
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_build_lpgraph (CCtsp_lpgraph *g, int ncount, int ecount,
int *elist, int *elen)
Description:
BUILDS the node and edge lists for the CCtsp_lpgraph pointed to by
g.
-elen contains the edge lengths (it can be NULL, in which case
the lengths are set to 0).
CCtsp_build_lpadj
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_build_lpadj (CCtsp_lpgraph *g, int estart, int eend)
Description:
BUILDS the incidence list for the graph *g
-estart is the index of the first edge to include in the list
-eend is the index of the last edge + 1
CCtsp_find_edge
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_find_edge (CCtsp_lpgraph *g, int from, int to)
Description:
MISSING
CCtsp_init_lpgraph_struct
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_init_lpgraph_struct (CCtsp_lpgraph *g)
Description:
INITIALIZES the CCtsp_lpgraph struct pointed to by g.
CCtsp_free_lpgraph
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_free_lpgraph (CCtsp_lpgraph *g)
Description:
FREES the fields in the CCtsp_lpgraph pointed to by g.
CCtsp_init_lprow
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_init_lprow (CCtsp_lprow *cr)
Description:
MISSING
CCtsp_free_lprow
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
void CCtsp_free_lprow (CCtsp_lprow *cr)
Description:
MISSING
CCtsp_inspect_full_edges
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_inspect_full_edges (CCtsp_lp *lp)
Description:
CHECKS that full edge set contains the current LP edge set; it
returns 0 if it is okay and 1 if some edge is not present
-lp is the CCtsp_lp
CCtsp_resparsify_lp
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_resparsify_lp (CCtsp_lp *lp, int silent)
Description:
MISSING
CCtsp_read_probfile
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_read_probfile (CCtsp_lp *lp, char *fname, char *probloc,
int *ncount, int silent)
Description:
READS a tsp file and loads the results into lp
-lp is an initialized lp (via a call to init_tsp_lp_struct; the
results are returned in this struct
-fname is the tsp file
-probloc is the problem location. If probloc == NULL, then the
this is derived from fname.
-ncount is a pointer to the number of nodes; if it is nonnull and
*ncount != 0, it is used as a check to see if the tsp file
matches. If it is nonnull and *ncount == 0, it returns the
from the tsp file.
CCtsp_read_probfile_id
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_read_probfile_id (CCtsp_lp *lp, char *fname, int id,
int *ncount, int silent)
Description:
READS a tsp file and loads the results into lp, where the filename
is obtained by using the id.
CCtsp_dump_x
File:
TSP/tsp_lp.c
Header:
tsp.h
Prototype:
int CCtsp_dump_x (CCtsp_lp *lp, char *fname)
Description:
WRITES the lp solution to fname.
NOTES: The vector contains the original node names.
CCtsp_solve_sparse
File:
TSP/tsp_call.c
Header:
tsp.h
Prototype:
int CCtsp_solve_sparse (int ncount, int ecount, int *elist,
int *elen, int *in_tour, int *out_tour, double *in_val,
double *optval, int *success, int *foundtour, char *name,
double *timebound, int *hit_timebound, int silent,
CCrandstate *rstate)
Description:
SOLVES the TSP over the graph specfied in the edgelist.
-elist is an array giving the ends of the edges (in pairs)
-elen is an array giving the weights of the edges.
-in_tour gives a starting tour in node node node format (it can
be NULL)
-out_tour will return the optimal tour (it can be NULL, if it is
not NULL then it should point to an array of length at least
ncount.
-in_val can be used to specify an initial upperbound (it can be
NULL)
-optval will return the value of the optimal tour.
-success will be set to 1 if the run finished normally, and set to
if the search was terminated early (by hitting some predefined
limit)
-foundtour will be set to 1 if a tour has been found (if success
is 0, then it may not be the optimal tour)
-name specifes a char string that will be used to name various
files that are written during the branch and bound search (if it
is NULL, then "noname" will be used - this will cause problems
in a multithreaded program, so specify a distinct name in that
case).
-silent will suppress most output if set to a nonzero value.
CCtsp_solve_dat
File:
TSP/tsp_call.c
Header:
tsp.h
Prototype:
int CCtsp_solve_dat (int ncount, CCdatagroup *indat, int *in_tour,
int *out_tour, double *in_val, double *optval, int *success,
int *foundtour, char *name, double *timebound, int *hit_timebound,
int silent, CCrandstate *rstate)
Description:
SOLVES the TSP over the graph specified in the datagroup.
LIKE CCtsp_solve_sparse.
CCtsp_teething
File:
TSP/teething.c
Header:
tsp.h
Prototype:
int CCtsp_teething (CCtsp_lpgraph *g, double *x,
CCtsp_lpcut_in *cut, CCtsp_lpcut_in **newcut)
Description:
CALLS teething with the handle and bigteeth of the comb given by
cut (the code will test that it really is a comb or subtour).
-g is the graph of the active edges in the LP
-x is an LP solution
-cut is the base comb
-newcut returns the comb found after teething
NOTES:
The new cut may be just a subtour inequality. This code is based
on the "Teething" section of the tsp notes.
CCtsp_teething_list
File:
TSP/teething.c
Header:
tsp.h
Prototype:
int CCtsp_teething_list (CCtsp_lpgraph *g, double *x,
CCtsp_lpclique *handle, int nbig, CCtsp_lpclique **bigteeth,
CCtsp_lpcut_in **newcut)
Description:
CALLS teething with the given handle and bigteeth.
NOTES: bigteeth should be filled in from 1 to nbig (not 0 to
nbig-1).
CCtsp_init_skeleton
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
void CCtsp_init_skeleton (CCtsp_skeleton *skel)
Description:
INITIALIZES a skeleton (to the NULL skeleton)
CCtsp_free_skeleton
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
void CCtsp_free_skeleton (CCtsp_skeleton *skel)
Description:
FREES the memory used by skel
CCtsp_copy_skeleton
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
int CCtsp_copy_skeleton (CCtsp_skeleton *old, CCtsp_skeleton *new)
Description:
COPIES a skeleton
CCtsp_read_skeleton
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
int CCtsp_read_skeleton (CC_SFILE *f, CCtsp_skeleton *skel,
int ncount)
Description:
READS a skeleton from f
CCtsp_write_skeleton
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
int CCtsp_write_skeleton (CC_SFILE *f, CCtsp_skeleton *skel,
int ncount)
Description:
WRITES a skeleton to f
CCtsp_construct_skeleton
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
int CCtsp_construct_skeleton (CCtsp_lpcut_in *c, int nodecount)
Description:
CONSTRUCTS a skeleton for c, representing all atoms in c
CCtsp_compare_skeletons
File:
TSP/skeleton.c
Header:
tsp.h
Prototype:
void CCtsp_compare_skeletons (CCtsp_skeleton *a, CCtsp_skeleton *b,
int *diff)
Description:
COMPARES two skeletons, setting *diff=0 if they are the same, and
*diff=1 if they are not.
CCtsp_qsparsify
File:
TSP/qsparse.c
Header:
tsp.h
Prototype:
int CCtsp_qsparsify (CCtsp_qsparsegroup **pqs, CCtsp_lpgraph *g,
int *pnzlist, int *scount, CCtsp_sparser **slist,
int *savedcount)
Description:
-pqs (if *pqs is NULL, then it will be initialized)
-g (the graph)
-pnzlist (pointer to an int that is the start of a linked list
of edges that is a superset of the nonzeros in the cut, it
returns a pointer to a superset of the nonzeros in the
sparsified cut. The links are via the coefnext field of
CCtsp_lpedge, and the coef field gives the actual nonzero
coefs.)
-scount (returns the number of CCtsp_sparsers in slist)
-slist (returns an array of CCtsp_sparsers)
-savedcount (returns the number of nonzeros that were saved)
RETURNS 0 is it worked and 1 if it failed (probably due to
running out of memory). CCtsp_free_qsparsify will free the
allocated memory (it is not freed after each call since the
mallocs and initialization require too much time).
NOTES:
This functions uses priorty queues to line up the stars that
would decrease the number of nonzeros if they were added or
subtracted there are separate add and subtract queues).
CCtsp_free_qsparsify
File:
TSP/qsparse.c
Header:
tsp.h
Prototype:
void CCtsp_free_qsparsify (CCtsp_qsparsegroup **pqs)
Description:
-pqs (will free the queues and arrays in the struct pointed to
by *pqs, and sets *pqs to NULL)
CCtsp_prob_read
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_read (char *f, int n)
Description:
NONE
CCtsp_prob_read_name
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_read_name (char *f)
Description:
NONE
CCtsp_prob_write
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_write (char *f, int n)
Description:
NONE
CCtsp_prob_write_name
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_write_name (char *fname)
Description:
NONE
CCtsp_prob_file_delete
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_file_delete (char *f, int n)
Description:
NONE
CCtsp_prob_getname
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getname (CCtsp_PROB_FILE *p, char *name)
Description:
NONE
CCtsp_prob_getid
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getid (CCtsp_PROB_FILE *p, int *id)
Description:
NONE
CCtsp_prob_getparent
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getparent (CCtsp_PROB_FILE *p, int *parent)
Description:
NONE
CCtsp_prob_getub
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getub (CCtsp_PROB_FILE *p, double *ub)
Description:
NONE
CCtsp_prob_getlb
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getlb (CCtsp_PROB_FILE *p, double *lb)
Description:
NONE
CCtsp_prob_getexactlb
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getexactlb (CCtsp_PROB_FILE *p, CCbigguy *lb)
Description:
NONE
CCtsp_prob_getnnodes
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getnnodes (CCtsp_PROB_FILE *p, int *nnodes)
Description:
NONE
CCtsp_prob_getchildren
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getchildren (CCtsp_PROB_FILE *p, int *child0,
int *child1)
Description:
NONE
CCtsp_prob_getreal
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getreal (CCtsp_PROB_FILE *p, int *real)
Description:
NONE
CCtsp_prob_getprocessed
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getprocessed (CCtsp_PROB_FILE *p, int *processed)
Description:
NONE
CCtsp_prob_getinfeasible
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getinfeasible (CCtsp_PROB_FILE *p, int *infeasible)
Description:
NONE
CCtsp_prob_gettour
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_gettour (CCtsp_PROB_FILE *p, int ncount, int **tour,
int silent)
Description:
NONE
CCtsp_prob_getedges
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getedges (CCtsp_PROB_FILE *p, int ncount, int *nedges,
int **elist, int **elen, int silent)
Description:
NONE
CCtsp_prob_getcuts
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getcuts (CCtsp_PROB_FILE *p, int *ncount,
CCtsp_lpcuts *cuts, int silent)
Description:
NONE
CCtsp_prob_getwarmstart
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getwarmstart (CCtsp_PROB_FILE *p, CClp_warmstart **w,
int silent)
Description:
NONE
CCtsp_prob_getfulladj
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getfulladj (CCtsp_PROB_FILE *p, int ncount,
int *fullcount, CCtsp_genadj **adj,
CCtsp_genadjobj **adjspace, int silent)
Description:
NONE
CCtsp_prob_getfixed
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getfixed (CCtsp_PROB_FILE *p, int ncount, int *ecount,
int **elist, int silent)
Description:
NONE
CCtsp_prob_getexactdual
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_getexactdual (CCtsp_PROB_FILE *p, ncount,
CCtsp_bigdual **d, int silent)
Description:
NONE
CCtsp_prob_gethistory
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_gethistory (CCtsp_PROB_FILE *p, int *depth,
CCtsp_branchobj **history, int silent)
Description:
NONE
CCtsp_prob_rclose
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_rclose (CCtsp_PROB_FILE *p)
Description:
NONE
CCtsp_prob_putname
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putname (CCtsp_PROB_FILE *p, char *name)
Description:
NONE
CCtsp_prob_putid
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putid (CCtsp_PROB_FILE *p, int id)
Description:
NONE
CCtsp_prob_putparent
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putparent (CCtsp_PROB_FILE *p, int parent)
Description:
NONE
CCtsp_prob_putub
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putub (CCtsp_PROB_FILE *p, double ub)
Description:
NONE
CCtsp_prob_putlb
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putlb (CCtsp_PROB_FILE *p, double lb)
Description:
NONE
CCtsp_prob_putexactlb
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putexactlb (CCtsp_PROB_FILE *p, CCbigguy lb)
Description:
NONE
CCtsp_prob_putnnodes
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putnnodes (CCtsp_PROB_FILE *p, int nnodes)
Description:
NONE
CCtsp_prob_putchildren
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putchildren (CCtsp_PROB_FILE *p, int child0,
int child1)
Description:
NONE
CCtsp_prob_putreal
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putreal (CCtsp_PROB_FILE *p, int real)
Description:
NONE
CCtsp_prob_putprocessed
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putprocessed (CCtsp_PROB_FILE *p, int processed)
Description:
NONE
CCtsp_prob_putinfeasible
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putinfeasible (CCtsp_PROB_FILE *p, int infeasible)
Description:
NONE
CCtsp_prob_puttour
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_puttour (CCtsp_PROB_FILE *p, int ncount, int *tour)
Description:
NONE
CCtsp_prob_putedges
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putedges (CCtsp_PROB_FILE *p, int ncount, int nedges,
int *elist, int *elen)
Description:
NONE
CCtsp_prob_putcuts
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putcuts (CCtsp_PROB_FILE *p, int ncount,
CCtsp_lpcuts *cuts)
Description:
NONE
CCtsp_prob_putwarmstart
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putwarmstart (CCtsp_PROB_FILE *p, CClp_warmstart *w)
Description:
NONE
CCtsp_prob_putfulladj
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putfulladj (CCtsp_PROB_FILE *p, int ncount,
int fullcount, CCtsp_genadj *adj)
Description:
MISSING
CCtsp_prob_putfixed
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putfixed (CCtsp_PROB_FILE *p, int ncount,
int ecount, int *elist)
Description:
MISSING
CCtsp_prob_putexact_dual
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_putexact_dual (CCtsp_PROB_FILE *p,
CCtsp_bigdual *exact_dual, int ncount)
Description:
NONE
CCtsp_prob_puthistory
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_puthistory (CCtsp_PROB_FILE *p, int depth,
CCtsp_branchobj *history)
Description:
NONE
CCtsp_prob_wclose
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_wclose (CCtsp_PROB_FILE *p)
Description:
NONE
CCtsp_prob_copy_section
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_copy_section (CCtsp_PROB_FILE *f, CCtsp_PROB_FILE *t,
char section, int silent)
Description:
NONE
CCtsp_problabel
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
char *CCtsp_problabel (const char *probloc)
Description:
-RETURNS a copy of the probname portion of probfile, or NULL if
unable to allocate space for the copy.
CCtsp_prob_read_remote
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_read_remote (char *hname, char *pname,
int n)
Description:
Only exists if CC_NETREADY is defined
CCtsp_prob_write_remote
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_write_remote (char *hname, char *pname,
int n)
Description:
Only exists if CC_NETREADY is defined
CCtsp_prob_server
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
CCtsp_PROB_FILE *CCtsp_prob_server (CC_SFILE *s)
Description:
Only exists if CC_NETREADY is defined
CCtsp_prob_delete_remote
File:
TSP/prob_io.c
Header:
tsp.h
Prototype:
int CCtsp_prob_delete_remote (char *hname, char *pname, int n)
Description:
Only exists if CC_NETREADY is defined
CCtsp_pr_cliquetree
File:
TSP/prclique.c
Header:
tsp.h
Prototype:
int CCtsp_pr_cliquetree (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x,
CCtsp_tighten_info *stats)
Description:
BUILDS clique trees based on the conected compenents of x-1.
-cuts (new cutting plans will be added to front of this list)
-cutcount will return the number of new cuts found (can be NULL)
-ncount is the number of nodes
-ecount is the number of edges
-elist is the edge list in node node format
-x is an lp solution vector
-stats is used to monitor tighten
CCtsp_edge_comb_grower
File:
TSP/growcomb.c
Header:
tsp.h
Prototype:
int CCtsp_edge_comb_grower (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x,
CCtsp_tighten_info *stats)
Description:
BUILDS combs with 1 inverted tooth using greedy cut.
-cuts (new cutting plans will be added to front of this list)
-cutcount will return the number of new cuts found (can be NULL)
-ncount is the number of nodes
-ecount is the number of edges
-elist is the edge list in node node format
-x is an lp solution vector
-stats is used to monitor tighten
CCtsp_init_edgegenerator
File:
TSP/generate.c
Header:
tsp.h
Prototype:
int CCtsp_init_edgegenerator (CCtsp_edgegenerator *eg, int ncount,
CCdatagroup *dg, CCtsp_genadj *adj, int nneighbors,
int silent, CCrandstate *rstate)
Description:
SETS UP the CCtsp_edgegenerator structure. Must be called before
calls to the other CCtsp_edgegenerator functions.
-eg must point to an CCtsp_edgegenerator struct.
-ncount is the number of nodes.
-dg will not be copied, only the pointer is recorded.
-adj will be used as the edgelist if it is nonnull (in this case
dg can be NULL).
-nneighbors is the number of neighbors that will be considered
from each node. To consider all edges, this should be set to
CCtsp_PRICE_COMPLETE_GRAPH.
CCtsp_free_edgegenerator
File:
TSP/generate.c
Header:
tsp.h
Prototype:
void CCtsp_free_edgegenerator (CCtsp_edgegenerator *eg)
Description:
FREES the space used by the structures in eg (but not eg itself).
CCtsp_reset_edgegenerator
File:
TSP/generate.c
Header:
tsp.h
Prototype:
int CCtsp_reset_edgegenerator (CCtsp_edgegenerator *eg,
double *node_piest, int silent)
Description:
ADDS the pi values to the eg and records the starting position in
the loop through the edges (so we can determine when we have
circled through all edges with a single set of pi values). This
must be called before the first call to CCtsp_generate_edges.
-eg must have been set up with a call to
CCtsp_init_edgegenerator.
-node_piest is pi values "estimates" on the nodes.
CCtsp_generate_edges
File:
TSP/generate.c
Header:
tsp.h
Prototype:
int CCtsp_generate_edges (CCtsp_edgegenerator *eg, int nwant,
int *pngot, int *elist, int *elen, int *finished,
int silent, CCrandstate *rstate)
Description:
RETURNS a list of edges that have a chance of having negative
reduced costs in that len(i,j) - pi[i] - pi[j] is negative. If an
entire pass has been made through the edgeset since the last call
to CCtsp_reset_edgegenerator, then finished is set to 1
(otherwise 0).
-eg must have been initialized with a call to
CCtsp_init_edgegenerator followed by a call to
CCtsp_reset_edgegenerator.
-nwant is the maximum number of edges that should be returned.
-pngot returns the number of edges found.
-elist returns the edges in node node format (this must have
been allocated by the calling routine and should be at least
2*nwant long.
-elen returns the lengths of the edges in elist (this must have
been allocated by the calling routine and have nwant entries).
-finished is set to 1 if an entire loop through the edges has
been made since the last call to CCtsp_reset_edgegenerator.
CCtsp_edgelist_to_genadj
File:
TSP/generate.c
Header:
tsp.h
Prototype:
int CCtsp_edgelist_to_genadj (int ncount, int ecount, int *elist,
int *elen, CCtsp_genadj **adj, CCtsp_genadjobj **adjobjspace)
Description:
RETURNS the CCtsp_genadj struct corresponding the list of edges.
-ncount is the number of nodes.
-ecount is the number of edges.
-elist is the array of edges in end1 end2 format.
-elen is the array of edge lengths.
-adj is a pointer to an CCtsp_genadj struct address; upon return
it will point to the filled in adj struct.
-adjobjspace will return a pointer to the list of
CCtsp_genadjobj's used in adj (this can be used to free the
objects)
CCtsp_exact_price
File:
TSP/ex_price.c
Header:
tsp.h
Prototype:
int CCtsp_exact_price (CCtsp_lp *lp, CCbigguy *bound,
int complete_price, int phase1, int silent)
Description:
RETURNS a bound that is valid for the entire edge set; the values
of the dual variables will be stored in lp->exact_dual unless
the existing lp->exact_dual's cutcount agrees with the
cutcount for lp
-lp is a pointer to the tsp lp
-bound returns the LP bound
-if complete_price is nonzero, then price over the complete
graph, even if a valid full edge set is present
-phase1 is either 0 or 1, with 1 indicating that the pricing
should be to determine a Farkas' lemma bound to prove that the
LP is infeasbile
CCtsp_edge_elimination
File:
TSP/ex_price.c
Header:
tsp.h
Prototype:
int CCtsp_edge_elimination (CCtsp_lp *lp, int eliminate_sparse,
int silent)
Description:
USES the bound information to elimination edges and set edges to 1;
the remaining edges are placed into lp->fulladj (the old adj
is freed) and the fixed edges are placed on the list
lp->fixededges; the dual values are taken from lp->exact_dual
-lp is a pointer to the tsp lp; lp->exact_lowerbound will be used
together with lp->upperbound to determine the cutoff to elim
and fix edges
-if eliminate_sparse is nonzero and lp->full_edges_valid, then
the elimination is based on the lp->fulladj list. Otherwise
the elimination is based on the lp->dat.
NOTES: this function does not alter the LP or lp->graph
CCtsp_exact_dual
File:
TSP/ex_price.c
Header:
tsp.h
Prototype:
int CCtsp_exact_dual (CCtsp_lp *lp)
Description:
RETURNS the dual values as bigguys (used to store the info used
to establish the exact lower bound); the values will be
stored in lp->exact_dual (and the existing values freed)
-lp is the CCtsp_lp
CCtsp_verify_infeasible_lp
File:
TSP/ex_price.c
Header:
tsp.h
Prototype:
int CCtsp_verify_infeasible_lp (CCtsp_lp *lp, int *yesno, int silent)
Description:
VERIFIES that the lp is infeasible using exact pricing.
-yesno is set to 1 if the lp is infeasible and 0 otherwise.
CCtsp_verify_lp_prune
File:
TSP/ex_price.c
Header:
tsp.h
Prototype:
int CCtsp_verify_lp_prune (CCtsp_lp *lp, int *yesno, int silent)
Description:
VERIFIES that the lp bound is less than the lp upperbound - 1.
-yesno is set to 1 if bound < upperbound - 1 and 0 otherwise.
CCtsp_test_pure_double_decker
File:
TSP/ddecker.c
Header:
tsp.h
Prototype:
int CCtsp_test_pure_double_decker (CCtsp_lpcut_in *c, int *yes_no,
int *handle1, int *handle2)
Description:
TESTS if cut is a pure double decker (no flips permitted)
-yes_no will be set to either 0 or 1, with 1 meaning yes.
-handle1 and handle2 will be set to the handles (they can be NULL)
CCtsp_comb_to_double_decker
File:
TSP/ddecker.c
Header:
tsp.h
Prototype:
int CCtsp_comb_to_double_decker (CCtsp_lpgraph *g, CC_GCgraph *h,
double *x, CCtsp_lpcut_in *c, CCtsp_lpcut_in **d)
Description:
ATTEMPTS to build a double decker from the comb by adding a second
handle.
-x is an lp vector (it should match the edge set of the graph g)
-c is the comb (it will be tested)
-d returns a NULL terminated list of any new double deckers that
were found
CCtsp_comb_to_star
File:
TSP/ddecker.c
Header:
tsp.h
Prototype:
int CCtsp_comb_to_star (CCtsp_lpgraph *g, CC_GCgraph *h, double *x,
CCtsp_lpcut_in *c, CCtsp_lpcut_in **d)
Description:
ATTEMPTS to build a star inequalite from the comb using the
lcm method of Naddef and Thienel.
-x is an lp vector (it should match the edge set of the graph g)
-c is the comb (it will be tested)
-d returns a NULL terminated list of any new stars that were found
CCtsp_comb_handling
File:
TSP/ddecker.c
Header:
tsp.h
Prototype:
int CCtsp_comb_handling (CCtsp_lpgraph *g, CC_GCgraph *h, double *x,
CCtsp_lpcut_in *c, CCtsp_lpcut_in **d)
Description:
ATTEMPTS to build star inequalities by adding nested handles and
possibly stretching the teeth.
-arguments are the same as above.
CCtsp_init_cutpool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_init_cutpool (int *ncount, char *poolfilename,
CCtsp_lpcuts **pool)
Description:
-ncount is a pointer to the number of nodes in the problem
-poolfilename is a file containing an cutpool (it can be NULL)
-CCtsp_lpcuts will return the pool
NOTES: poolfilename must be non-NULL or ncount must be
non-NULL and *ncount nonzero. If ncount is non-NULL but
*ncount == zero, then *ncount will be set to the number of
nodes in the cutpool in poolfilename
NOTES:
This version does not use the compressed set references. Notes
on the representation are given in "Chapter 4: The Linear
Programming Problems".
CCtsp_search_cutpool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts,
int *cutcount, double *maxviol, int ncount, int ecount,
int *elist, double *x, int nthreads, CCrandstate *rstate)
Description:
RETURNS an array of cuts having x(delta(C)) < rhs(C)
-pool points to a cutpool (or cuts of an lp)
-cuts will return the array of cuts
-cutcount with return the length of the array
-ncount is the number of nodes in the problem
-ecount is the number of edges in elist
-elist is a list of edges in end end format
-x is an ecount-long array of weights
-nthreads is the number of threads to use. 0 ==> sequential code
threads are only used if CC_POSIXTHREADS is defined
CCtsp_search_remotepool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_search_remotepool (char *remotehost,
unsigned short remoteport, CCtsp_lpcut_in **cuts,
int *cutcount, double *maxviol, int ncount, int ecount,
int *elist, double *x)
Description:
RETURNS an array of cuts having x(delta(C)) < rhs(C) from a remote
cutpool
-remotehost is the host with the cuts
-remoteport is the port on which to contact the remote server
(if remoteport == 0, use CCtsp_CUT_PORT)
-cuts will return the array of cuts
-cutcount with return the length of the array
-ncount is the number of nodes in the problem
-ecount is the number of edges in elist
-elist is a list of edges in end end format
-x is an ecount-long array of weights
CCtsp_search_cutpool_cliques
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool,
CCtsp_lpclique **cliques, int *cliquecount, int ncount,
int ecount, int *elist, double *x, double maxdelta,
int maxcliques, double **cliquevals, CCrandstate *rstate)
Description:
RETURNS an array of cliques having x(delta(C)) < maxdelta
-pool points to a cutpool (or cuts of an lp)
-cliques will return the array of cliques
-cliquecount with return the length of the array
-ncount is the number of nodes in the problem
-ecount is the number of edges in elist
-elist is a list of edges in end end format
-x is an ecount-long array of weights
-maxdelta is a bound on x(delta(C))
-maxcliques is an upperbound on the number of cliques that should
be returned
-cliquevals will return the values of x(delta(C)) for the cliques
(this parameter can be NULL)
CCtsp_add_cut_to_cutlist
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_add_cut_to_cutlist (CCtsp_lpcuts *cuts, CCtsp_lpcut *c)
Description:
NONE
CCtsp_delete_cut_from_cutlist
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
void CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts *cuts, int ind)
Description:
NONE
CCtsp_free_cutpool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
void CCtsp_free_cutpool (CCtsp_lpcuts **pool)
Description:
FREES the pool of cuts.
CCtsp_write_cutpool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_write_cutpool (int ncount, const char *poolfilename,
CCtsp_lpcuts *pool)
Description:
WRITES pool to poolfilename.
CCtsp_branch_cutpool_cliques
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool,
CCtsp_lpclique **cliques, int *cliquecount, int ncount,
int ecount, int *elist, double *x, int nwant,
double **cliquevals, int silent)
Description:
RETURNS an array of cliques having x(delta(C)) as close to 3.0 as
possible.
-the parmeters are like those used by search_cutpool_cliques,
where nwant is the number of cliques we would like to have in
the array.
CCtsp_price_cuts
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount,
int *elist, double *x, double *cutval)
Description:
COMPUTES the slack on each cut in the pool
-ecount, elist, and x give an x-vector
-cutval returns the array of slack values (it should be passed in
as an array of length at least pool->cutcount)
CCtsp_price_cuts_threaded
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_price_cuts_threaded (CCtsp_lpcuts *pool, int ncount,
int ecount, int *elist, double *x, double *cutval,
int numthreads)
Description:
COMPUTES the slack on each cut in the pool in parallel
-ecount, elist, and x give an x-vector
-cutval returns the array of slack values (it should be passed in
as an array of length at least pool->cutcount)
-nthreads is the number of parallel threads to use.
CCtsp_get_clique_prices
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_get_clique_prices (CCtsp_lpcuts *pool, int **p_cliquenums,
double **p_cliquevals, double mindelta, double maxdelta,
int *p_cliquecount, int ncount, int ecount, int *elist,
double *x)
Description:
RETURNS the id's and x(delta(C)) for cliques in the pool.
-the parameters pool, ncount, ecount, elist, and x are like those
used by search_cutpool_cliques.
-mindelta and maxdelta are bounds on x(delta(C))
-cliquenums and cliquevals return id's and x(delta(C)) for
cliques with x(delta(C)) between mindelta and maxdelta
-cliquecount returns the number of cliques in cliquenums/vals
-use CCtsp_get_clique to retrive specific cliques.
CCtsp_get_clique
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_get_clique (CCtsp_lpcuts *pool, int cliquenum,
CCtsp_lpclique **p_clique)
Description:
RETURNS p_clique, a pointer to the clique numbered clqiuenum in
the pool. Note that this clique is not a copy, and thus should
not be freed.
CCtsp_display_cutpool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_display_cutpool (CCtsp_lpcuts *pool)
Description:
DISPLAYS the contents of a cutpool.
CCtsp_add_to_cutpool
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts,
CCtsp_lpcut *c)
Description:
-pool is the pool to add the cut to
-cuts is the lpcuts the cut is from
-c is the cut
ADDS a cut to a pool
CCtsp_add_to_cutpool_lpcut_in
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool,
CCtsp_lpcut_in *c)
Description:
-pool is the pool to add the cut to
-c is the cut
ADDS a cut to a pool
CCtsp_free_lpcut_in
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
void CCtsp_free_lpcut_in (CCtsp_lpcut_in *c)
Description:
FREES the fields in the CCtsp_lpcut pointed to by c.
CCtsp_free_lpclique
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
void CCtsp_free_lpclique (CCtsp_lpclique *c)
Description:
FREES the fields in the CCtsp_lpclique pointed to by c.
CCtsp_read_cuts
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_read_cuts (CC_SFILE *f, int *ncount, CCtsp_lpcuts *cuts,
int readmods, int buildhash)
Description:
READS the cuts from f into cuts.
-readmods indicates whether or not the file contains sparser mods
CCtsp_read_lpcut_in
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_read_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount)
Description:
MISSING
CCtsp_read_lpclique
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_read_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount)
Description:
MISSING
CCtsp_send_newcuts
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_send_newcuts (int ncount, CCtsp_lpcuts *pool,
char *remotehost, unsigned short remoteport)
Description:
SENDS the new cuts from pool to the remote host
CCtsp_write_cuts
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_write_cuts (CC_SFILE *f, int ncount, CCtsp_lpcuts *cuts,
int writemods)
Description:
WRITES the cuts from cuts to f.
-writemods indicates whether or not the file should contain
sparser mods
CCtsp_write_lpcut_in
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_write_lpcut_in (CC_SFILE *f, CCtsp_lpcut_in *c, int ncount)
Description:
MISSING
CCtsp_write_lpcut
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_write_lpcut (CC_SFILE *f, CCtsp_lpcuts *cuts,
CCtsp_lpcut *c, int ncount)
Description:
MISSING
CCtsp_write_lpclique
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_write_lpclique (CC_SFILE *f, CCtsp_lpclique *c, int ncount)
Description:
MISSING
CCtsp_copy_cuts
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_copy_cuts (CC_SFILE *f, CC_SFILE *t, int copymods)
Description:
COPIES the cuts from f to t.
CCtsp_register_cliques
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
int CCtsp_register_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c,
CCtsp_lpcut *new)
Description:
BUILDS the references to the cliques in c into the cut strucure
pointed to by cuts and creates an array of the indices of the
the cliques in CCtsp_lpcut new
-cuts is the structure holding the set of cuts
-c describes the cut to be added to the structure
-new returns the array of clique indices
CCtsp_unregister_cliques
File:
TSP/cutpool.c
Header:
tsp.h
Prototype:
void CCtsp_unregister_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut *c)
Description:
REMOVES the references to the cliques in cut c (and deletes the
cliques if they have no more references) and frees the array
of clique indices in c
-cuts is the structure holding the set of cuts
-c is the cut containing the cliques to be removed
CCtsp_connect_cuts
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_connect_cuts (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x)
Description:
FINDS violated subtour inequalities via connectivity.
-cuts will return any new cuts found (they will be added to the
head of the linked list)
-cutcount will return the number of new cuts added
-ncount is the number of nodes
-ecount is the number of edges
-elist contains the LP edges in node node format
-x is an LP solution
CCtsp_segment_cuts
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_segment_cuts (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x)
Description:
FINDS violated subtour inequalities via linsub.
CCtsp_exact_subtours
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_exact_subtours (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x)
Description:
FINDS violated subtour inequalities via a mincut algorithm.
CCtsp_tighten_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_tighten_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
CCtsp_lpcut_in **cutsout, int *cutcount, int ncount,
int ecount, int *elist, double *x, double testtol,
int maxcuts, double *viol, CCrandstate *rstate)
Description:
CALLS tighten for each cut in the cuts.
-stats contains some running statistics of tighten
-cutsout returns the tightened cuts that are violated (they are
added to the tail of the linked list)
-cutcount is the number of cuts in cutsout
-testtol is a tolerance for calling tighten (call only when the
cut has slack value within testtol)
-maxcuts is a bound on the number of cuts to be returned
CCtsp_double_decker_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_double_decker_lp (CCtsp_lpcuts *cuts,
CCtsp_tighten_info *stats, CCtsp_lpcut_in **cutsout,
int *cutcount, int ncount, int ecount, int *elist, double *x,
double testtol, int maxcuts, double *viol, CCrandstate *rstate)
Description:
MISSING
CCtsp_cliquetree_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_cliquetree_lp (CCtsp_lpcuts *cuts,
CCtsp_tighten_info *stats, CCtsp_lpcut_in **cutsout,
int *cutcount, int ncount, int ecount, int *elist, double *x,
double testtol, int maxcuts, double *viol, CCrandstate *rstate)
Description:
MISSING
CCtsp_star_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_star_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
CCtsp_lpcut_in **cutsout, int *cutcount, int ncount,
int ecount, int *elist, double *x, double testtol,
int maxcuts, double *viol, CCrandstate *rstate)
Description:
MISSING
CCtsp_handling_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_handling_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
CCtsp_lpcut_in **cutsout, int *cutcount, int ncount,
int ecount, int *elist, double *x, double testtol,
int maxcuts, double *viol, CCrandstate *rstate)
Description:
CALLS CCtsp_comb_handling for each comb in cuts.
-agruments as in CCtsp_tighten_lp.
CCtsp_handling_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_handling_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
CCtsp_lpcut_in **cutsout, int *cutcount, int ncount,
int ecount, int *elist, double *x, double testtol,
int maxcuts, double *viol, CCrandstate *rstate)
Description:
MISSING
CCtsp_teething_lp
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_teething_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
CCtsp_lpcut_in **cutsout, int *cutcount, int ncount,
int ecount, int *elist, double *x, double testtol,
int maxcuts, double *viol, CCrandstate *rstate)
Description:
MISSING
CCtsp_file_cuts
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_file_cuts (char *cutfile, CCtsp_lpcut_in **cuts,
int *cutcount, int ncount, int *tour)
Description:
READS a set of cuts from a file; the format of the cuts can be
found by examining the code
-cutfile is an asci file with a list of cuts
-cuts will return any new cuts found (they will be added to the
tail of the linked list)
-cutcount with return the number of new cuts added
-ncount is the number of nodes
-tour the permutation tour (used to map the incoming nodes)
CCtsp_file_cuts_write
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_file_cuts_write (const char *cutfile, CCtsp_lpcuts *cuts,
int *tour)
Description:
WRITES a set of cuts in a text file that can be read by
tsp_file_cuts
-cutfile is the name of the file to be written
-cuts is the set of cuts to be written
-tour is a permutation tour (used to map the outgoing nodes)
CCtsp_test_pure_comb
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_test_pure_comb (int ncount, CCtsp_lpcut_in *c, int *yes_no,
int *handle)
Description:
TEST if the cut is a comb (without flipped teeth or intersections)
-ncount is the number of nodes in the TSP
-yes_no will be set to either 0 or 1, with 1 meaning yes
-handle with return the index of the handle if the cut is a comb
(handle can be NULL)
CCtsp_test_pseudocomb
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_test_pseudocomb (int ncount, CCtsp_lpcut_in *c, int handle,
int *yes_no)
Description:
TEST if the cut is a pseudocomb.
-handle gives the index of the handle of the pseudocomb
CCtsp_test_teeth_disjoint
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_test_teeth_disjoint (int ncount, CCtsp_lpcut_in *c,
int handle, int *yes_no)
Description:
TEST if the cliques other than handle are pairwise disjoint.
-yes_no is 1 if disjoint and 0 otherwise.
CCtsp_find_pure_handle
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_find_pure_handle (int ncount, CCtsp_lpcut_in *c,
int *handle)
Description:
FINDS a clique that is c's handle if c is a comb; the search
assumes that the teeth are disjoint, so if the comb has
extra intersections then a tooth may be returned.
-handle returns the potential handle (it will return -1 if no
clique is a potential handle)
CCtsp_buildcut_begin
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_buildcut_begin (CCtsp_cutinfo *cuts, int init_cliquecount)
Description:
MISSING
CCtsp_buildcut_addclique
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_buildcut_addclique (CCtsp_cutinfo *cuts, *arr, int size)
Description:
MISSING
CCtsp_buildcut_finish
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
int CCtsp_buildcut_finish (CCtsp_cutinfo *cuts, int rhs)
Description:
MISSING
CCtsp_buildcut_abort
File:
TSP/cutcall.c
Header:
tsp.h
Prototype:
void CCtsp_buildcut_abort (CCtsp_cutinfo *cuts)
Description:
MISSING
CCtsp_init_cutselect
File:
TSP/control.c
Header:
tsp.h
Prototype:
void CCtsp_init_cutselect (CCtsp_cutselect *s)
Description:
INITIALIZES the cut selections
CCtsp_init_tentative_cutselect
File:
TSP/control.c
Header:
tsp.h
Prototype:
void CCtsp_init_tentative_cutselect (CCtsp_cutselect *s)
Description:
MISSING
CCtsp_cutselect_set_tols
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_cutselect_set_tols (CCtsp_cutselect *s, CCtsp_lp *lp,
int level, int silent)
Description:
SETS the tolerances for the cut selections
-level should be set to 0 for tentative cutting
NOTES: The lp should be solved before this call.
CCtsp_cutting_loop
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_cutting_loop (CCtsp_lp *lp, CCtsp_cutselect *sel,
int savelp, int silent, CCrandstate *rstate)
Description:
CALLS the cutting plane and pricing routines.
-sel should be set with the desired cut selection.
-savelp should be set to a nonzero value to write the lps to after
rounds of cuts
-silent turns off most output if set to a nonzero value
NOTES: It returns a 2 if the lp becomes infeasible
CCtsp_subtour_loop
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_subtour_loop (CCtsp_lp *lp, int silent,
CCrandstate *rstate)
Description:
CALLS the cutting and pricing to optimize over the subtour polytope.
CCtsp_blossom_loop
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_blossom_loop (CCtsp_lp *lp, int silent,
CCrandstate *rstate)
Description:
CALLS the cutting and pricing to optimize over the blossom polytope.
CCtsp_subtour_and_blossom_loop
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_subtour_and_blossom_loop (CCtsp_lp *lp, int silent,
CCrandstate *rstate)
Description:
CALLS the cutting and princing to optimize over subtours and
trivial blossoms.
CCtsp_pricing_loop
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_pricing_loop (CCtsp_lp *lp, double *bnd, int silent,
CCrandstate *rstate)
Description:
ADDS negative reduced costs edges to lp and returns the current
lowerbound.
-bnd can be NULL
NOTES: The LP must have full_edges_valid.
CCtsp_call_x_heuristic
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_call_x_heuristic (CCtsp_lp *lp, double *val, int *outcyc,
int silent, CCrandstate *rstate)
Description:
CALLS the x-greedy LK heuristic with the current LP solution.
-val returns the length of the tour.
-outcyc will return the tour in node-node-node format if the
length of the tour is less than lp->upperbound; the array should
at least of length ncount (it can be NULL)
CCtsp_bb_cutting
File:
TSP/control.c
Header:
tsp.h
Prototype:
int CCtsp_bb_cutting (char *probname, int probnum, int prob_newnum,
int ncount, CCdatagroup *dat, int *ptour, double *upbound,
CCtsp_lpcuts *pool, CCtsp_cutselect *sel, double *val,
int *prune, int *foundtour, int *besttour, int level,
int silent, CCrandstate *rstate)
Description:
CALLS the cutting loop after reading the lp; writes the result to
prob file prob_newnum; using exact price to verify pruned runs
-upbound should be passed in as the current bound; if a better
tour is found then upbound will be updated
-val returns the lp bound; it is CCtsp_LP_MAXDOUBLE if infeasible
-prune is set to 1 if bbnode can be pruned
-foundtour is set to 1 if a better tour is found.
-besttour (if not NULL) will return a better tour if one is found.
-level should be set to 0 for tentative cutting
CCtsp_test_pure_simple_cliquetree
File:
TSP/combcliq.c
Header:
tsp.h
Prototype:
int CCtsp_test_pure_simple_cliquetree (int ncount,
CCtsp_lpcut_in *c, int *yes_no)
Description:
TEST if cut is a two handled cliquetree (assumes first two cliques
cliques in the cut are the handles).
-ncount is the number of nodes in the graph.
-c points to the cut.
-yes_no will be set to either 0 or 1, with 1 meaning yes.
CCtsp_comb_to_cliquetree
File:
TSP/combcliq.c
Header:
tsp.h
Prototype:
int CCtsp_comb_to_cliquetree (CCtsp_lpgraph *g, CC_GCgraph *h,
double *x, CCtsp_lpcut_in *c, CCtsp_lpcut_in **d)
Description:
ATTEMPTS to build a cliquetree from the comb by adding a bunny.
-x is an lp vector (it should match the edge set of the graph g)
-c is the comb (it will be tested)
-d returns the double decker or NULL if none is found
CCtsp_mark_clique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_mark_clique (CCtsp_lpclique *c, int *marks, int marker)
Description:
MARKS the nodes in clique c
-marks an array of length at least ncount
-marker an int that is used to mark the clique entries in marks
CCtsp_mark_clique_and_neighbors
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph *g,
CCtsp_lpclique *c, int *marks, int marker)
Description:
MARKS the clique and the neighbors of the clique
CCtsp_mark_clique_and_neighbors_double
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph *g,
CCtsp_lpclique *c, double *marks, double marker)
Description:
MARKS the clique and the neighbors of the clique in a double array.
CCtsp_mark_cut
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_mark_cut (CCtsp_lpcut_in *c, int *marks, int marker)
Description:
MARKS the nodes in the cut.
CCtsp_mark_cut_and_neighbors
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph *g,
CCtsp_lpcut_in *c, int *marks, int marker)
Description:
MARKS the nodes in the cut and their neighbors
CCtsp_is_clique_marked
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_is_clique_marked (CCtsp_lpclique *c, int *marks,
int marker, int *yes_no)
Description:
CHECKS if a node in the clique is marked with the value marker.
-yesno returns the result (1 is yes and 0 is no)
CCtsp_clique_count
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_clique_count (CCtsp_lpclique *c, int *count)
Description:
COUNTS the nodes in the clique.
CCtsp_clique_marked_count
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_clique_marked_count (CCtsp_lpclique *c, int *marks,
int marker, int *count)
Description:
COUNTS the nodes in the clique have mark equal to marker.
CCtsp_clique_to_array
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_clique_to_array (CCtsp_lpclique *c, int **ar, int *count)
Description:
EXPANDS a clique into an array of integers.
CCtsp_clique_delta
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_clique_delta (CCtsp_lpgraph *g, double *x,
CCtsp_lpclique *c, double *delta)
Description:
COMPUTES the sum of the x-edges in the coboundary of the clique,
that is, x(delta(c)).
-delta returns the sum
CCtsp_segment_to_subtour
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b,
int ncount)
Description:
BUILDS a subtour CCtsp_lpcut_in from an the segment.
-cut will return the subtour (it will be allocated).
CCtsp_array_to_subtour
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar,
int acount, int ncount)
Description:
BUILDS a subtour CCtsp_lpcut_in from an array.
-cut will return the subtour (it will be allocated).
CCtsp_init_lpcut_in
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_init_lpcut_in (CCtsp_lpcut_in *c)
Description:
INITIALIZE the fields of the CCtsp_lpcut_in structure
CCtsp_init_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_init_lpclique (CCtsp_lpclique *c)
Description:
INITIALIZE the fields of the CCtsp_lpclique structure
CCtsp_array_to_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_array_to_lpclique (int *ar, int acount,
CCtsp_lpclique *cliq)
Description:
BUILDS an CCtsp_lpclique represented the nodes in an array.
-ar is an array of node numbers
-acount is the length of ar
-cliq's segcount and nodes will be filled with the compressed
version of the nodes in ar
CCtsp_seglist_to_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_seglist_to_lpclique (int nseg, int *list,
CCtsp_lpclique *cliq)
Description:
BUILDS the CCtsp_lpclique represented by a list of segments (it
will sort the segments before it puts them into the CCtsp_segment
structures)
-list is an array of segments in lo-hi-lo-hi format
-clig's segcount and nodes will be filled in (nodes will be
allocated)
CCtsp_shrunk_set_to_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_shrunk_set_to_lpclique (int cnt, int *set, int *wset,
CC_SRKexpinfo *expand, CCtsp_lpclique *cliq)
Description:
BUILDS an lpclique by exanding a shrunk set of nodes.
-cnt is the number of nodes in set
-set is an array of the nodes
-wset is a working array, it should be ncount long and the values
may be changed by this function
-expand contains the info to expand the nodes
-cliq returns the clique
CCtsp_add_nodes_to_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_add_nodes_to_lpclique (CCtsp_lpclique *cin,
CCtsp_lpclique *cout, int addcount, int *adda)
Description:
ADDS nodes to clique cin, and returns the new clique in cout
-addcount has number of nodes to be added.
-adda has the indices of the addcount nodes to be added.
CCtsp_delete_nodes_from_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_delete_nodes_from_lpclique (CCtsp_lpclique *cin,
CCtsp_lpclique *cout, int delcount, int *del)
Description:
DELETES nodes from clique cin, and returns the new clique in cout
-delcount has number of nodes to be deleted.
-del has the indices of the delcount nodes to be deleted.
CCtsp_print_lpcut_in
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_print_lpcut_in (CCtsp_lpcut_in *c)
Description:
PRINTS the CCtsp_lpcut_in
CCtsp_print_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_print_lpclique (CCtsp_lpclique *c)
Description:
PRINTS the segments in the clique to stdout.
CCtsp_copy_lpcut_in
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new)
Description:
COPIES an CCtsp_lpcut_in
-c is a pointer to an CCtsp_lpcut_in
-new returns the copied CCtsp_lpcut_in
CCtsp_lpcut_to_lpcut_in
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c,
CCtsp_lpcut_in *new)
Description:
COPIES an CCtsp_lpcut to an CCtsp_lpcut_in
-cuts is a pointer to the structure holding the set of cuts
-c is the cut to be copied
-new returns the copied cut
CCtsp_lpclique_compare
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
void CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b,
int *diff)
Description:
COMPARES two CCtsp_lpcliques.
-diff is set to 1 if they differ and 0 if they are the same
NOTES: Assumes segments are ordered.
CCtsp_copy_lpclique
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new)
Description:
COPIES an CCtsp_lpclique
-c is a pointer to an CCtsp_lpclique
-new returns the copied clique
CCtsp_create_lpcliques
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_create_lpcliques (CCtsp_lpcut_in *c, int cliquecount)
Description:
ALLOCATES and INITIALIZES the cliques space for c.
CCtsp_max_node
File:
TSP/cliqwork.c
Header:
tsp.h
Prototype:
int CCtsp_max_node (CCtsp_lpcut_in *c)
Description:
MISSING
CCtsp_init_cliquehash
File:
TSP/cliqhash.c
Header:
tsp.h
Prototype:
int CCtsp_init_cliquehash (CCtsp_lpcuts *cuts, int size)
Description:
initializes the clique hash storage in cuts.
int size is an estimate of the number of cliques
CCtsp_register_clique
File:
TSP/cliqhash.c
Header:
tsp.h
Prototype:
int CCtsp_register_clique (CCtsp_lpcuts *cuts, CCtsp_lpclique *c)
Description:
returns an integer index for c, adding c to cuts if necessary
-1 ==> failure
CCtsp_free_cliquehash
File:
TSP/cliqhash.c
Header:
tsp.h
Prototype:
void CCtsp_free_cliquehash (CCtsp_lpcuts *cuts)
Description:
frees the clique hashtable space
CCtsp_unregister_clique
File:
TSP/cliqhash.c
Header:
tsp.h
Prototype:
void CCtsp_unregister_clique (CCtsp_lpcuts *cuts, int c)
Description:
deletes a reference to clique c, and deletes the clique if no
references remain
CCtsp_clique_eq
File:
TSP/cliqhash.c
Header:
tsp.h
Prototype:
void CCtsp_clique_eq (CCtsp_lpclique *c, CCtsp_lpclique *d,
int *yes_no)
Description:
MISSING
CCtsp_hashclique
File:
TSP/cliqhash.c
Header:
tsp.h
Prototype:
unsigned int CCtsp_hashclique (CCtsp_lpclique *c)
Description:
RETURNS a hash value for the clique.
CCtsp_find_branch
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_find_branch (CCtsp_lp *lp, int nwant, int *ngot,
CCtsp_branchobj **bobj, double *val, int **cyc,
int usecliques, int longedge_branching, int silent)
Description:
FINDS a set of branching edges and cliques.
-usecliques should be set to 1 to allow branching on cliques
-val returns the length of a tour if one is detected.
-cyc returns the tour (it can be NULL)
-longedge_branching if nonzero selects the alternative longedge
branching rule.
CCtsp_find_branch_edge
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_find_branch_edge (CCtsp_lp *lp, int *n0, int *n1,
double *val, int **cyc, int branchtype, int silent)
Description:
FINDS a branching edge or detects that solution is integral.
-lp points to an optimized lp.
-n0, n1 return the edges of the branching edge; n0 is set to -1
if the current lp solution is a tour
-val returns the value the tour if n0 is set to -1
-branchtype determines the strategy for choosing the branching
edge; choices for branchtype are given in tsp.h
CCtsp_check_integral
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_check_integral (CCtsp_lp *lp, double *val, int **cyc,
int *yesno, int silent)
Description:
TESTS if the current x-vector is a tour.
-yesno is set to 1 if it is a tour and 0 otherwise.
CCtsp_find_branch_cliques
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_find_branch_cliques (CCtsp_lp *lp, int nwant,
int longedge_branching, int *ngot, CCtsp_lpclique **bcliques,
double *bval, int silent)
Description:
FINDS branching cliques (it may return ngot == 0)
-bval will return the stongbranching function evaluation for
each clique (it can be NULL)
CCtsp_test_cut_branch
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_test_cut_branch (CCtsp_lp *lp, CCtsp_lpclique *c,
double *down, double *up, int iter, int silent)
Description:
ESTIMATES the bound shift from branching on clique c
-iter is the number of dual simplex pivots to try.
CCtsp_init_branchobj
File:
TSP/branch.c
Header:
tsp.h
Prototype:
void CCtsp_init_branchobj (CCtsp_branchobj *b)
Description:
INITITALIZES the fields in the CCtsp_branchobj pointed to by b.
CCtsp_free_branchobj
File:
TSP/branch.c
Header:
tsp.h
Prototype:
void CCtsp_free_branchobj (CCtsp_branchobj *b)
Description:
FREES the fields in the CCtsp_branchobj pointed to by b.
CCtsp_print_branchhistory
File:
TSP/branch.c
Header:
tsp.h
Prototype:
void CCtsp_print_branchhistory (CCtsp_lp *lp)
Description:
PRINT to stdout the branch history of the lp
CCtsp_execute_branch
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_execute_branch (CCtsp_lp *lp, CCtsp_branchobj *b,
int silent, CCrandstate *rstate)
Description:
SETS the lp to realize the branch described in b
NOTES: returns 2 if the LP becomes infeasible.
CCtsp_execute_unbranch
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_execute_unbranch (CCtsp_lp *lp, CClp_warmstart *warmstart,
int silent, CCrandstate *rstate)
Description:
UNDOS the changes to the lp caused by the most recent branch that
has not yet been unbranched (used in dfs)
-warmstart can specify a warmstart to help resolve the LP
(it can be NULL)
NOTES: returns 2 if the LP is infeasible.
CCtsp_add_branchhistory_to_lp
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_add_branchhistory_to_lp (CCtsp_lp *lp)
Description:
SETS the lp to realize the branches in branch history
CCtsp_bb_find_branch
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_bb_find_branch (char *probname, int probnum, int ncount,
CCdatagroup *dat, int *ptour, double *upperbound,
CCtsp_lpcuts *pool, int nwant, int *ngot, CCtsp_branchobj **b,
int usecliques, int longedge_branching, int *foundtour,
int *besttour, int silent, CCrandstate *rstate),
Description:
MISSING
CCtsp_splitprob
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_splitprob (CCtsp_lp *lp, CCtsp_branchobj *b, int child0,
int child1, int silent, CCrandstate *rstate)
Description:
EXECUTES a branch on the lp and writes to two child lps
-b contains the branching information (the rhs side value is set
by this function to give 0 and 1 for edge branches and 2 & 4 for
clique branches; the sense is set by this function for clique
branches to realize <= 2 and >= 4)
-child0 and child1 are the ids of the children
CCtsp_bb_splitprob
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_bb_splitprob (char *probname, int probnum, int ncount,
CCdatagroup *dat, int *ptour, double initial_ub,
CCtsp_lpcuts *pool, CCtsp_branchobj *b, int child0,
int child1, double *val0, double *val1, int *prune0,
int *prune1, int silent, CCranstate *rstate)
Description:
CALLS splitprob after reading the lp file and building an lp; this
function will also price the lp and attempt to verify infeasible
lps.
-val0 and val1 return the (priced) lp-bounds for the children; if
an lp is infeasible then the val is set to CCtsp_LP_MAXDOUBLE and
the lp is not written.
-prune0 and prune1 will be set to 1 if the child can be pruned
(in which case the lp is not written)
CCtsp_dumptour
File:
TSP/branch.c
Header:
tsp.h
Prototype:
int CCtsp_dumptour (int ncount, CCdatagroup *dat, int *perm,
char *probname, int *tour, int silent)
Description:
WRITES the tour file to probname.sol.
-dat is used to compute the length (it can be NULL)
-perm is a permutation tour
-tour gives the tour (perm[tour[i]] with be printed)
CCtsp_exactblossom
File:
TSP/blossom.c
Header:
tsp.h
Prototype:
int CCtsp_exactblossom (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x,
CCrandstate *rstate)
Description:
RUNS Padberg-Rao to seperate over blossom inequalities.
-cuts (new cutting plans will be added to front of this list)
-cutcount will return the number of new cuts found (can be NULL)
-ncount is the number of nodes
-ecount is the number of edges
-elist is the edge list in node node format
-x is an lp solution vector
NOTES:
The exactblossom code was written very early in our TSP project.
In January 1999 it was updated to fit into the current concorde,
but the guts of the code are still written in our old sloppy
style. This is a good candidate for a rewrite (big speedups are
probably possible without too much effort).
CCtsp_fastblossom
File:
TSP/blossom.c
Header:
tsp.h
Prototype:
int CCtsp_fastblossom (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x)
Description:
FINDS blossoms by looking at 0 < x < 1 graph for connected comps
meeting an odd number of 1 edges.
CCtsp_ghfastblossom
File:
TSP/blossom.c
Header:
tsp.h
Prototype:
int CCtsp_ghfastblossom (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x)
Description:
FINDS blossoms using a heuristic described by Groetschel and
Holland. It works with the 0 < x < 1-EPS (with EPS = .3) graph,
builds components, and picks a greedy set of teeth.
CCtsp_block_combs
File:
TSP/blkcomb.c
Header:
tsp.h
Prototype:
int CCtsp_block_combs (CCtsp_lpcut_in **cuts, int *cutcount,
int ncount, int ecount, int *elist, double *x, int silent)
Description:
-ncount is the number of nodes
-ecount is the number of edges
-elist is the edge list in node node format
-x is an lp solution vector
-silent turns off output if set to a nonzero value
CCtsp_bfs_brancher
File:
TSP/bcontrol.c
Header:
tsp.h
Prototype:
int CCtsp_bfs_brancher (char *probloc, int id, double lowerbound,
CCtsp_cutselect *sel, CCtsp_cutselect *tsel,
double *upbound, int *bbcount, int usecliques,
CCdatagroup *mydat, int *ptour, CCtsp_lpcuts *pool,
int ncount, int *besttour, unsigned short hostport,
double *branchzeit, int save_proof,
int tentative_branch_num, int longedge_branching,
double *timebound, int *hit_timebound, int silent,
CCrandstate *rstate)
Description:
PERFORMS a best-first (best-bound) branch and cut search for
an optimal tour.
-tentative_branch_num specifies the number of trial children
created (this should be set to 0 to run standard branching)
-timebound can specify an upperbound on the time to spend in the
bfs search (it can be NULL; does not work with netgrunts)
-hit_timebound will return 1 if timebound is reached (it can be
NULL)
-if longedge_branching is nonzero, longedge branching will be used
instead of the default branching
CCtsp_bfs_restart
File:
TSP/bcontrol.c
Header:
tsp.h
Prototype:
int CCtsp_bfs_restart (char *probloc, char *restart_name,
CCtsp_cutselect *sel, CCtsp_cutselect *tsel,
double *upbound, int *bbcount, int usecliques,
CCdatagroup *dat, int *ptour, CCtsp_lpcuts *pool,
int ncount, int *besttour, unsigned short hostport,
double *branchzeit, int save_proof,
int tentative_branch_num, int longedge_branching,
double *timebound, int *hit_timebound, int silent,
CCrandstate *rstate)
Description:
CONTINUES a best-first (best-bound) branch and cut search for
an optimal tour from the restart data in restart_name.
CCtsp_grunt
File:
TSP/bcontrol.c
Header:
tsp.h
Prototype:
int CCtsp_grunt (char *hostname, unsigned short hostport,
char *poolfname, char *cutbossname, char *probloc,
int silent, CCrandstate *rstate)
Description:
RUNS a grunt served by hostname at port hostport
If probloc is NULL, the probloc will be received from the boss.
Only exists if CC_NETREADY is defined
CCtsp_easy_dfs_brancher
File:
TSP/bcontrol.c
Header:
tsp.h
Prototype:
int CCtsp_easy_dfs_brancher (CCtsp_lp *lp, CCtsp_cutselect *sel,
int depth, double *upbound, int *bbcount, int usecliques,
int *besttour, int silent, CCrandstate *rstate)
Description:
PERFORMS a depth-first branch and cut search for an optimal tour.
NOTES: this will be very inefficient if upbound is not a good bound.
CCtsp_do_interactive_branch
File:
TSP/bcontrol.c
Header:
tsp.h
Prototype:
int CCtsp_do_interactive_branch (CCtsp_lp *lp, int silent,
CCrandstate *rstate)
Description:
SPLITS a problem into two subproblems, prompting the user for
information about what split to use.
CCtsp_tighten_lpcut_in
File:
TSP/tighten.c
Header:
tsp.h
Prototype:
int CCtsp_tighten_lpcut_in (CCtsp_lpgraph *g, CCtsp_lpcut_in *c,
double *x, CCtsp_lpcut_in *d, CCtsp_tighten_info *stats,
double *pimprove)
Description:
MISSING
CCtsp_tighten_lpcut
File:
TSP/tighten.c
Header:
tsp.h
Prototype:
int CCtsp_tighten_lpcut (CCtsp_lpgraph *g, CCtsp_lpclique *cliques,
CCtsp_lpcut *c, double *x, CCtsp_lpcut_in *d,
CCtsp_tighten_info *stats, double *pimprove)
Description:
MISSING
CCtsp_init_tighten_info
File:
TSP/tighten.c
Header:
tsp.h
Prototype:
void CCtsp_init_tighten_info (CCtsp_tighten_info *stats)
Description:
MISSING
CCtsp_print_tighten_info
File:
TSP/tighten.c
Header:
tsp.h
Prototype:
void CCtsp_print_tighten_info (CCtsp_tighten_info *stats)
Description:
MISSING