00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef _TREE_MANAGER
00016 #define _TREE_MANAGER
00017
00018 #define COMPILING_FOR_TM
00019
00020 #include "symphony.h"
00021 #include "sym_tm_params.h"
00022 #include "sym_types.h"
00023 #ifdef COMPILE_IN_CG
00024 #include "sym_cg.h"
00025 #endif
00026 #ifdef COMPILE_IN_CP
00027 #include "sym_cp.h"
00028 #endif
00029
00030
00031
00032 typedef struct PROCESS_SET{
00033 int procnum;
00034 int *procs;
00035 int free_num;
00036 int *free_ind;
00037 }process_set;
00038
00039
00040
00041 typedef struct TM_TEMP{
00042 int *i;
00043 int i_size;
00044 char *c;
00045 int c_size;
00046 double *d;
00047 int d_size;
00048 }tm_temp;
00049
00050
00051
00052
00053
00054 struct LP_PROB;
00055
00056 typedef struct TM_PROB{
00057 tm_params par;
00058 int master;
00059 char has_ub;
00060 char has_ub_estimate;
00061 double start_time;
00062 double ub;
00063 double lb;
00064 lp_sol best_sol;
00065 double obj_offset;
00066 char obj_sense;
00067 double ub_estimate;
00068 process_set lp;
00069 process_set cg;
00070 process_set cp;
00071
00072 #ifdef COMPILE_IN_LP
00073 struct LP_PROB **lpp;
00074 int opt_thread_num;
00075 #ifdef COMPILE_IN_CG
00076 cg_prob **cgp;
00077 #endif
00078 #endif
00079 #ifdef COMPILE_IN_CP
00080 cut_pool **cpp;
00081 #endif
00082
00083 int *nodes_per_cp;
00084
00085 int *active_nodes_per_cp;
00086
00087 bc_node *rootnode;
00088
00089 int bvarnum;
00090 int bcutnum;
00091
00092 int phase;
00093
00094 int active_node_num;
00095 bc_node **active_nodes;
00096
00097
00098 int samephase_candnum;
00099 bc_node **samephase_cand;
00100 int samephase_cand_size;
00101
00102 int nextphase_candnum;
00103 bc_node **nextphase_cand;
00104 int nextphase_cand_size;
00105
00106
00107 int cut_num;
00108 int allocated_cut_num;
00109 cut_data **cuts;
00110
00111 problem_stat stat;
00112
00113 node_times comp_times;
00114
00115
00116
00117 bc_node ***rpath;
00118 int *rpath_size;
00119 branch_desc **bpath;
00120 int *bpath_size;
00121
00122 #ifdef TRACE_PATH
00123 int feas_sol_size;
00124 int *feas_sol;
00125 #endif
00126
00127 tm_temp tmp;
00128 }tm_prob;
00129
00130
00131
00132
00133
00134 int tm_initialize PROTO((tm_prob *tm, base_desc *base,
00135 node_desc *root_desc));
00136 int solve PROTO((tm_prob *tm));
00137 void print_tree_status PROTO((tm_prob *tm));
00138 void calculate_widths PROTO((bc_node *node, int *widths));
00139 int start_node PROTO((tm_prob *tm, int thread_num));
00140 bc_node *del_best_node PROTO((tm_prob *tm));
00141 void insert_new_node PROTO((tm_prob *tm, bc_node *new_node));
00142 char node_compar PROTO((int rule, bc_node *node0, bc_node *node1));
00143 int assign_pool PROTO((tm_prob *tm, int oldpool, process_set *pools,
00144 int *active_nodes_per_pool, int *nodes_per_pool));
00145 int generate_children PROTO((tm_prob *tm, bc_node *node, branch_obj *bobj,
00146 double *objval, int *feasible, char *action,
00147 char olddive, int *keep, int new_branching_cut));
00148 char shall_we_dive PROTO((tm_prob *tm, double objval));
00149 int purge_pruned_nodes PROTO((tm_prob *tm, bc_node *node, int category));
00150 int find_process_index PROTO((process_set *pset, int tid));
00151 void mark_lp_process_free PROTO((tm_prob *tm, int lp, int cp));
00152 int add_cut_to_list PROTO((tm_prob *tm, cut_data *cut));
00153 int find_tree_lb PROTO((tm_prob *tm));
00154
00155
00156
00157 void merge_descriptions PROTO((node_desc *old_node, node_desc *new_node));
00158 void merge_base_stat PROTO((double_array_desc *dad,
00159 double_array_desc *moddad));
00160 void merge_extra_array_and_stat PROTO((array_desc *ad, double_array_desc *dad,
00161 array_desc *modad,
00162 double_array_desc *moddad));
00163 void merge_double_array_descs PROTO((double_array_desc *dad,
00164 double_array_desc *newdad));
00165 void merge_arrays PROTO((array_desc *array, array_desc *adesc));
00166 void modify_list PROTO((array_desc *origad, array_desc *modad));
00167 void modify_list_and_stat PROTO((array_desc *origad, int *origstat,
00168 array_desc *modad,
00169 double_array_desc *moddad));
00170
00171
00172
00173 int tasks_before_phase_two PROTO((tm_prob *tm));
00174 int trim_subtree PROTO((tm_prob *tm, bc_node *n));
00175 int mark_subtree PROTO((tm_prob *tm, bc_node *n));
00176 void propagate_nf_status PROTO((bc_node *n, int nf_status));
00177
00178
00179
00180 void write_log_files PROTO((tm_prob *tm));
00181 int write_pruned_nodes PROTO((tm_prob *tm, bc_node *node));
00182 int write_node PROTO((bc_node *node, char *file, FILE *f, char append));
00183 int write_subtree PROTO((bc_node *node, char *file, FILE* f, char append,
00184 int logging));
00185 int write_tm_cut_list PROTO((tm_prob *tm, char *file, char append));
00186 int write_tm_info PROTO((tm_prob *tm, char *file, FILE* f, char append));
00187 int write_base PROTO((base_desc *base, char *file, FILE* f, char append));
00188 int read_node PROTO((tm_prob *tm, bc_node *node, FILE *f, int **children));
00189 int read_subtree PROTO((tm_prob *tm, bc_node *node, FILE *f));
00190 int read_tm_cut_list PROTO((tm_prob *tm, char * file));
00191 int read_tm_info PROTO((tm_prob *tm, FILE *f));
00192 int read_base PROTO((base_desc *base, FILE *f));
00193
00194
00195
00196 void free_tm PROTO((tm_prob *tm));
00197 void free_subtree PROTO((bc_node *n));
00198 void free_tree_node PROTO((bc_node *n));
00199 void free_basis PROTO((basis_desc *basis));
00200 int tm_close PROTO((tm_prob *tm, int termcode));
00201
00202
00203
00204
00205
00206 process_set start_processes PROTO((tm_prob *tm,
00207 int procnum, char *procname, int procdebug,
00208 int machnum, char **mach));
00209 void stop_processes PROTO((process_set *pset));
00210 char processes_alive PROTO((tm_prob *tm));
00211 void send_active_node PROTO((tm_prob *tm, bc_node *node, char colgen_strat,
00212 int thread_num));
00213 void receive_node_desc PROTO((tm_prob *tm, bc_node *n));
00214 void process_branching_info PROTO((tm_prob *tm, bc_node *node));
00215 char process_messages PROTO((tm_prob *tm, int r_bufid));
00216 void process_ub_message PROTO((tm_prob *tm));
00217 void unpack_cut_set PROTO((tm_prob *tm, int sender, int cutnum,
00218 row_data *rows));
00219 int receive_lp_timing PROTO((tm_prob *tm));
00220
00221 void sym_catch_c PROTO((int num));
00222 #endif