00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of the SYMPHONY MILP Solver Framework. */ 00004 /* */ 00005 /* SYMPHONY was jointly developed by Ted Ralphs (tkralphs@lehigh.edu) and */ 00006 /* Laci Ladanyi (ladanyi@us.ibm.com). */ 00007 /* */ 00008 /* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved. */ 00009 /* */ 00010 /* This software is licensed under the Common Public License. Please see */ 00011 /* accompanying file for terms. */ 00012 /* */ 00013 /*===========================================================================*/ 00014 00015 #ifndef _BB_TYPES_H 00016 #define _BB_TYPES_H 00017 00018 #define MAX_CHILDREN_NUM 4 00019 #define MAX_CHANGE_NUM 6 00020 00021 /*===========================================================================*\ 00022 * This file contains those type definitions which are used in more than one 00023 * process of the black box model. 00024 \*===========================================================================*/ 00025 00026 #if !defined (_MSC_VER) 00027 #include <unistd.h> /* this defines sleep() */ 00028 #endif 00029 00030 #include "sym_proto.h" 00031 00032 typedef struct LP_SOL{ 00033 int lp; /* the tid of the lp process asssociated with 00034 the current solution */ 00035 int has_sol; /* indicates whether a feasible solution 00036 found*/ 00037 int xlength; /* the number of nonzeros in the lp solution 00038 currently being processed*/ 00039 int xlevel; /* the level at which the current solution was 00040 generated*/ 00041 int xindex; 00042 int xiter_num; 00043 int max_sol_length; 00044 int *xind; /* the indices of the nonzeros in the current 00045 solution*/ 00046 double *xval; /* the values of the nonzeros in the current 00047 solution*/ 00048 double objval; /* the objective function value of the current 00049 relaxation*/ 00050 double lpetol; 00051 }lp_sol; 00052 00053 typedef struct BASE_DESC{ 00054 int varnum; 00055 int *userind; 00056 #if 0 00057 double *lb; /* even if there are global lb and ub, we */ 00058 double *ub; /* fill these arrays out */ 00059 #endif 00060 int cutnum; 00061 }base_desc; 00062 00063 /*===========================================================================*\ 00064 * Stores the data corresponding to a particular cut 00065 \*===========================================================================*/ 00066 00067 typedef struct CUT_DATA{ 00068 int size; /* the size of the coef array */ 00069 char *coef; /* an array which contains the data necessary to 00070 construct the cut -- it is stored in a 00071 packed form. The types of the cut tells how 00072 to "unpack" it */ 00073 double rhs; /* the right hand side for the constraint*/ 00074 double range; 00075 char type; /* the type of cut */ 00076 char sense; /* sense of the cut constraint */ 00077 char deletable; /* whether or not this cut should be removed 00078 from the LP after being added */ 00079 char branch; /* shows whether we can branch on its cut if 00080 this row becomes slack */ 00081 int name; /* internal to the BB. The identifier of the 00082 cut. >=0 if exists, -1 if does not exist yet, 00083 but the cuT is sent to the cutpool, -2 if 00084 no name & no pool */ 00085 }cut_data; 00086 00087 typedef struct ROW_DATA{ 00088 cut_data *cut; 00089 int ineff_cnt; 00090 int eff_cnt; 00091 char free; 00092 char deletable; 00093 }row_data; 00094 00095 typedef struct WAITING_ROW{ 00096 int source_pid; 00097 cut_data *cut; 00098 int *matind; 00099 double *matval; 00100 int nzcnt; 00101 double violation; 00102 }waiting_row; 00103 00104 /*===========================================================================*\ 00105 * The following three definitions are used to describe the search tree 00106 * nodes. 00107 \*===========================================================================*/ 00108 00109 typedef struct VAR_DESC{ 00110 int userind; 00111 int colind; 00112 double lb; 00113 double ub; 00114 char is_int; /* whether or not the variable is integer */ 00115 }var_desc; 00116 00117 typedef struct BRANCH_DESC{ 00118 int name; /* the userind/cut name depending on the type */ 00119 char type; /* description of the child. All of them are 00120 natural for branching cuts. For branching 00121 variables they should be interpreted as if 00122 we were adding a cut with a single variable 00123 on the left hand side */ 00124 char sense; 00125 double rhs; 00126 double range; 00127 int branch; 00128 }branch_desc; 00129 00130 typedef struct ARRAY_DESC{ 00131 char type; /* NO_DATA_STORED, EXPLICIT_LIST, WRT_PARENT */ 00132 int size; 00133 int added; 00134 int *list; 00135 }array_desc; 00136 00137 typedef struct DOUBLE_ARRAY_DESC{ 00138 char type; /* NO_DATA_STORED, EXPLICIT_LIST, WRT_PARENT */ 00139 int size; /* the size of list, stat */ 00140 int *list; 00141 int *stat; 00142 }double_array_desc; 00143 00144 typedef struct BASIS_DESC{ 00145 char basis_exists; 00146 00147 /*========================================================================*\ * Notes: 00148 * 1) for base...: 00149 * if list is non-NULL then it refers to col/row inds, not userinds 00150 * or cut names. 00151 * 2) the stat field of extra... ponts into the stat field of base... 00152 * 3) if extra... is EXPLICIT_LIST then the node_desc structure's 00153 * cutind/uind fields should be used. 00154 * 4) EXPLICIT_LIST in uind implies that extravars is explicit, 00155 * EXPLICIT_LIST in cutind implies that extrarows is explicit. 00156 \*========================================================================*/ 00157 double_array_desc basevars; 00158 double_array_desc extravars; 00159 double_array_desc baserows; 00160 double_array_desc extrarows; 00161 }basis_desc; 00162 00163 typedef struct NODE_DESC{ 00164 /*========================================================================*\ 00165 * The userindices of variables in this node (but not for the base 00166 * variables); The basis header for this node; The not-yet-permanently-fixed 00167 * variables (again, no base variable is listed here); and the cuts at 00168 * this node 00169 \*========================================================================*/ 00170 array_desc uind; 00171 basis_desc basis; 00172 array_desc not_fixed; 00173 int nf_status; /* NF_CHECK_ALL, NF_CHECK_AFTER_LAST, 00174 NF_CHECK_UNTIL_LAST, NF_CHECK_NOTHING */ 00175 array_desc cutind; 00176 #if defined(COMPILING_FOR_LP) || defined(COMPILING_FOR_MASTER) || defined(COMPILE_IN_LP) 00177 cut_data **cuts; /* this is not used in TM anyway. */ 00178 #endif 00179 00180 /* Any additional info the user might want to pass */ 00181 int desc_size; 00182 char *desc; 00183 }node_desc; 00184 00185 typedef struct BRANCH_OBJ{ 00186 char type; /* Type of the candidate */ 00187 #if defined(COMPILING_FOR_LP) || defined(COMPILE_IN_LP) 00188 int position; /* The position of the candidate */ 00189 waiting_row *row; /* Description of the left hand side; makes 00190 sense only for branching cuts */ 00191 #endif 00192 int child_num; /* Number of kids */ 00193 #if defined(COMPILING_FOR_TM) || defined(COMPILING_FOR_MASTER) || defined(COMPILE_IN_LP) 00194 int name; /* userind for VAR, the index for CUT */ 00195 #endif 00196 00197 /*========================================================================*\ 00198 * Description of the children. 00199 * All of them are natural for branching cuts. 00200 * For branching variables they should be interpreted as if we were adding 00201 * a cut with a single variable on the left hand side 00202 \*========================================================================*/ 00203 00204 #ifdef MAX_CHILDREN_NUM 00205 char sense[MAX_CHILDREN_NUM]; 00206 double rhs[MAX_CHILDREN_NUM]; 00207 double range[MAX_CHILDREN_NUM]; 00208 int branch[MAX_CHILDREN_NUM]; 00209 #ifdef COMPILE_FRAC_BRANCHING 00210 int frac_num[MAX_CHILDREN_NUM]; 00211 int *frac_ind[MAX_CHILDREN_NUM]; 00212 double *frac_val[MAX_CHILDREN_NUM]; 00213 #endif 00214 #else 00215 char *sense; 00216 double *rhs; 00217 double *range; 00218 int *branch; 00219 #ifdef COMPILE_FRAC_BRANCHING 00220 int *frac_num; 00221 int **frac_ind; 00222 double **frac_val; 00223 #endif 00224 #endif 00225 00226 #if defined(COMPILING_FOR_LP) || defined(COMPILE_IN_LP) 00227 double lhs; /* purely for the user */ 00228 00229 #ifdef MAX_CHILDREN_NUM 00230 double objval[MAX_CHILDREN_NUM]; /* arrays of size 'number' */ 00231 int termcode[MAX_CHILDREN_NUM]; 00232 int iterd[MAX_CHILDREN_NUM]; 00233 int feasible[MAX_CHILDREN_NUM]; 00234 00235 #else 00236 double *objval; /* arrays of size 'number' */ 00237 int *termcode; 00238 int *iterd; 00239 int *feasible; 00240 00241 #endif 00242 00243 #endif 00244 int *sol_sizes; 00245 int **sol_inds; 00246 double **solutions; 00247 #ifdef SENSITIVITY_ANALYSIS 00248 double **duals; 00249 #endif 00250 00251 }branch_obj; 00252 00253 /*===========================================================================*/ 00254 00255 typedef struct STR_INT{ 00256 #ifdef _OPENMP 00257 char *str; 00258 #else 00259 char str[MAX_LINE_LENGTH +1]; 00260 #endif 00261 int code; 00262 }str_int; 00263 00264 /*===========================================================================*\ 00265 * This is the time measurement structure for an LP node 00266 \*===========================================================================*/ 00267 00268 typedef struct NODE_TIMES{ 00269 double communication; 00270 double lp; 00271 double separation; 00272 double fixing; 00273 double pricing; 00274 double strong_branching; 00275 double wall_clock_lp; 00276 double ramp_up_tm; 00277 double ramp_up_lp; 00278 double ramp_down_time; 00279 double idle_diving; 00280 double idle_node; 00281 double idle_names; 00282 double idle_cuts; 00283 double start_node; 00284 double cut_pool; 00285 }node_times; 00286 00287 /*===========================================================================*\ 00288 * Here we keep track of the computation time for each of the various 00289 * parts of the computation 00290 \*===========================================================================*/ 00291 00292 typedef struct PROB_TIMES{ 00293 double readtime; /* time spent reading in the problem*/ 00294 node_times bc_time; 00295 double ub_overhead; /* overhead time used doing the upper bounding */ 00296 double ub_heurtime; /* actual comp time doing the upper bounding */ 00297 double lb_overhead; /* overhead time doing the lower bounding */ 00298 double lb_heurtime; /* actual comp time doing the lower bounding */ 00299 }prob_times; 00300 00301 /*===========================================================================*\ 00302 * The bc_node data structure stores the information needed to 00303 * process a node in the branch and cut tree 00304 \*===========================================================================*/ 00305 00306 typedef struct BC_NODE{ 00307 int bc_index; /* the identifier of the node */ 00308 int bc_level; /* the level in the tree of the node */ 00309 00310 int lp; /* the tid of the lp processing the node */ 00311 int cg; /* the tid of the cut generator serving the node */ 00312 int cp; /* the tid of the cut pool assigned to the node */ 00313 double lower_bound; /* the current best objective function value 00314 obtained in the subproblem */ 00315 double opt_estimate; /* an estimate of the value of the best feasible 00316 solution that could be obtained in this node */ 00317 struct BC_NODE *parent; 00318 struct BC_NODE **children; 00319 branch_obj bobj; 00320 00321 node_desc desc; /* the description of the node, 00322 defined in "sym_types.h" */ 00323 char node_status; 00324 00325 int feasibility_status; 00326 int sol_size; 00327 int *sol_ind; 00328 double *sol; 00329 #ifdef SENSITIVITY_ANALYSIS 00330 double *duals; 00331 double C_LP; 00332 double B_IP; 00333 #endif 00334 00335 #ifdef TRACE_PATH 00336 char optimal_path; 00337 #endif 00338 }bc_node; 00339 00340 /*===========================================================================*\ 00341 * Keeps problem statistics 00342 \*===========================================================================*/ 00343 00344 typedef struct PROBLEM_STAT{ 00345 double root_lb; 00346 int cuts_in_pool; 00347 int max_depth; /* keeps track of the deepest level reached 00348 in the tree so far */ 00349 int chains; /* the number of diving chains */ 00350 int diving_halts; /* how many times was an already started 00351 dive stopped */ 00352 int tree_size; /* number of search tree nodes */ 00353 int created; /* the number of created nodes (not 00354 necessarily the same as tree_size 00355 (trimming...) */ 00356 int analyzed; /* the number of analyzed (i.e., CG-LP 00357 iteration) nodes (not necessarily same 00358 as created, leaves can be cut off 00359 without analyzing; trimming) */ 00360 int leaves_before_trimming; 00361 int leaves_after_trimming; 00362 int vars_not_priced; /* How many variables did not price out 00363 after the first phase */ 00364 char nf_status; /* nf_status of the root node after 00365 repricing */ 00366 }problem_stat; 00367 00368 00369 /* This structure stores the user's description of the model */ 00370 00371 typedef struct MIPDESC{ 00372 int n; /* number of columns */ 00373 int m; /* number of rows */ 00374 int nz; /* number of nonzeros */ 00375 char *is_int; /* indicates whether a given variables is integer */ 00376 int *matbeg; /* n */ 00377 int *matind; /* nz */ 00378 double *matval; /* nz */ 00379 double *obj; /* n */ 00380 double *obj1; /* n */ /* for bicriteria problems */ 00381 double *obj2; /* n */ /* for bicriteria problems */ 00382 double *rhs; /* m */ 00383 double *rngval; /* m */ 00384 char *sense; /* m */ 00385 double *lb; /* n */ 00386 double *ub; /* n */ 00387 char **colname; /* column names */ 00388 double obj_offset; /* constant to be added to the objective function.*/ 00389 char obj_sense; /* objective sense. */ 00390 00391 /* Only to be allocated and used by SYMPHONY */ 00392 00393 int *col_lengths; 00394 int *row_matbeg; /* m */ /* a row ordered desc for heuristics */ 00395 int *row_matind; /* nz */ 00396 double *row_matval; /* nz */ 00397 int *row_lengths; 00398 int var_type_modified; /* number of updates on the mip desc */ 00399 int change_num; /* number of updates on the mip desc */ 00400 int change_type[MAX_CHANGE_NUM]; /* type of the mip desc. changes */ 00401 00402 }MIPdesc; 00403 00404 /*===========================================================================*\ 00405 * The warm start description contains all information needed to warm start 00406 * the algorithm. 00407 \*===========================================================================*/ 00408 00409 typedef struct WARM_START_DESC{ 00410 bc_node *rootnode; 00411 int cut_num; 00412 int allocated_cut_num; 00413 cut_data **cuts; 00414 problem_stat stat; 00415 node_times comp_times; 00416 int phase; 00417 double lb; 00418 char has_ub; 00419 double ub; 00420 lp_sol best_sol; 00421 }warm_start_desc; 00422 00423 #endif
1.4.7