00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef _LP_H
00016 #define _LP_H
00017
00018 #define COMPILING_FOR_LP
00019
00020 #include "symphony.h"
00021 #include "sym_timemeas.h"
00022 #include "sym_lp_params.h"
00023 #include "sym_types.h"
00024 #include "sym_lp_solver.h"
00025 #include "sym_lp_u.h"
00026
00027 #ifdef COMPILE_IN_CG
00028 #include "sym_cg.h"
00029 #endif
00030
00031 #ifdef COMPILE_IN_CP
00032 #include "sym_cp.h"
00033 #endif
00034
00035 #ifdef COMPILE_IN_LP
00036 #include "sym_tm.h"
00037 #endif
00038
00039
00040
00041 #ifdef PRINT
00042 #undef PRINT
00043 #endif
00044 #define PRINT(a, b, c) \
00045 if ((a) > (b)) printf c
00046
00047
00048
00049 typedef struct OUR_COL_SET{
00050 int dual_feas;
00051
00052 int rel_lb;
00053 int *rel_lb_ind;
00054 int rel_ub;
00055 int *rel_ub_ind;
00056
00057 int num_vars;
00058 int *userind;
00059
00060 double *objx;
00061 double *lb;
00062 double *ub;
00063 int *matbeg;
00064 int *matind;
00065 double *matval;
00066 int nzcnt;
00067 }our_col_set;
00068
00069
00070 typedef struct LP_PROB{
00071 int proc_index;
00072 void *user;
00073
00074 lp_params par;
00075
00076 char has_ub;
00077 double ub;
00078
00079 int phase;
00080
00081 double start_time;
00082
00083 base_desc base;
00084
00085 branch_desc *bdesc;
00086 int bdesc_size;
00087
00088 int master;
00089 int draw_graph;
00090 int tree_manager;
00091 int cut_pool;
00092 int cut_gen;
00093
00094 #ifdef COMPILE_IN_CG
00095 cg_prob *cgp;
00096 #endif
00097 #ifdef COMPILE_IN_LP
00098 tm_prob *tm;
00099 #endif
00100 lp_sol best_sol;
00101 double obj[2];
00102 double utopia[2];
00103 char has_mc_ub;
00104 double mc_ub;
00105
00106 double tt;
00107 node_times comp_times;
00108
00109 node_desc *desc;
00110 int bc_index;
00111 int bc_level;
00112 int vars_at_ub;
00113 int vars_at_lb;
00114 int vars_deletable;
00115
00116 char dive;
00117 char colgen_strategy;
00118 char colgen_happened;
00119 char colset_changed;
00120
00121 int iter_num;
00122 int node_iter_num;
00123 int vars_recently_fixed_to_ub;
00124 LPdata *lp_data;
00125 MIPdesc *mip;
00126
00127 double last_gap;
00128 double *obj_history;
00129
00130
00131
00132
00133
00134
00135 int waiting_row_num;
00136 waiting_row **waiting_rows;
00137 int waiting_rows_size;
00138
00139
00140
00141
00142
00143
00144 int slack_cut_num;
00145 cut_data **slack_cuts;
00146 int slack_cuts_size;
00147 }lp_prob;
00148
00149
00150
00151
00152
00153 lp_prob *get_lp_ptr PROTO((lp_prob **lp_list));
00154 int lp_initialize PROTO((lp_prob *p, int master_tid));
00155 int process_chain PROTO((lp_prob *p));
00156 int fathom_branch PROTO((lp_prob *p));
00157 int fathom PROTO((lp_prob *p, int primal_feasible));
00158 int repricing PROTO((lp_prob *p));
00159 int bfind PROTO((int key, int *table, int size));
00160 int collect_nonzeros PROTO((lp_prob *p, double *x, int *tind, double *tx));
00161 int collect_fractions PROTO((lp_prob *p, double *x, int *tind, double *tx));
00162 node_desc *create_explicit_node_desc PROTO((lp_prob *p));
00163 int check_tailoff PROTO((lp_prob *p));
00164 int round_solution PROTO((lp_prob *p, double *solution_value,
00165 double *betterSolution));
00166 int local_search PROTO((lp_prob *p, double *solution_value,
00167 double *col_solution, double *better_solution));
00168 void lp_exit PROTO((lp_prob *p));
00169 void lp_close PROTO((lp_prob *p));
00170
00171
00172
00173
00174
00175 void add_col_set PROTO((lp_prob *p, our_col_set *new_cols));
00176 void colind_sort_extra PROTO((lp_prob *p));
00177 void userind_sort_extra PROTO((lp_prob *p));
00178 void tighten_bounds PROTO((lp_prob *p));
00179 our_col_set *price_all_vars PROTO((lp_prob *p));
00180 int restore_lp_feasibility PROTO((lp_prob *p, our_col_set *new_cols));
00181 void userind_sort_extra PROTO((lp_prob *p));
00182 void colind_sort_extra PROTO((lp_prob *p));
00183 int var_uind_comp PROTO((const void *v0, const void *v1));
00184 int var_cind_comp PROTO((const void *v0, const void *v1));
00185
00186
00187
00188
00189
00190 int check_row_effectiveness PROTO((lp_prob *p));
00191 void add_row_set PROTO((lp_prob *p, waiting_row **wrows, int length));
00192 void add_new_rows_to_waiting_rows PROTO((lp_prob *p, waiting_row **new_rows,
00193 int new_row_num));
00194 void order_waiting_rows_based_on_sender PROTO((lp_prob *p));
00195 int add_best_waiting_rows PROTO((lp_prob *p));
00196 void add_waiting_rows PROTO((lp_prob *p, waiting_row **wrows,int add_row_num));
00197 int waiting_row_comp PROTO((const void *wr0, const void *wr1));
00198 int compute_violations PROTO((lp_prob *p,
00199 int new_row_num, waiting_row **new_rows));
00200 void compress_slack_cuts PROTO((lp_prob *p));
00201
00202
00203
00204
00205
00206 void add_slacks_to_matrix PROTO((lp_prob *p, int cand_num,
00207 branch_obj **candidates));
00208 int add_violated_slacks PROTO((lp_prob *p, int cand_num,
00209 branch_obj **candidates));
00210 int select_branching_object PROTO((lp_prob *p, int *cuts,
00211 branch_obj **can));
00212 int branch PROTO((lp_prob *p, int cuts));
00213 int col_gen_before_branch PROTO((lp_prob *p, int *new_vars));
00214
00215
00216
00217 void branch_close_to_half PROTO((lp_prob *p, int max_cand_num, int *cand_num,
00218 branch_obj ***candidates));
00219 void branch_close_to_half_and_expensive PROTO((lp_prob *p, int max_cand_num,
00220 int *cand_num,
00221 branch_obj ***candidates));
00222 void branch_close_to_one_and_cheap PROTO((lp_prob *p, int max_cand_num,
00223 int *cand_num,
00224 branch_obj ***candidates));
00225
00226
00227
00228
00229
00230 void check_ub PROTO((lp_prob *p));
00231 int process_message PROTO((lp_prob *p, int r_bufid, int *pindex, int *pitnum));
00232 void lp_process_ub_message PROTO((lp_prob *p));
00233 int receive_active_node PROTO((lp_prob *p));
00234 int receive_cuts PROTO((lp_prob *p, int first_lp, int no_more_cuts_count));
00235 void send_node_desc PROTO((lp_prob *p, char node_type));
00236 array_desc pack_array_desc_diff PROTO((array_desc *ad, array_desc *new_ad,
00237 int *itmp));
00238 basis_desc pack_basis_diff PROTO((node_desc *oldnode, node_desc *newnode,
00239 char uind_type, char cutind_type,
00240 int *itmp));
00241 char pack_base_diff PROTO((int *size, int *oldstat, int *newstat, int *itmp));
00242 char pack_extra_diff PROTO((array_desc *olddesc, int *oldstat,
00243 array_desc *newdesc, int *newstat,
00244 char oldbasis_type_in_tm, char newdesc_type_in_tm,
00245 int *itmp, int *size));
00246 void send_branching_info PROTO((lp_prob *p, branch_obj *can, char *action,
00247 int *keep));
00248 void send_lp_is_free PROTO((lp_prob *p));
00249 void send_cuts_to_pool PROTO((lp_prob *p, int eff_cnt_limit));
00250
00251
00252
00253
00254
00255 void free_cut PROTO((cut_data **lpcut));
00256 void free_waiting_row PROTO((waiting_row **wrow));
00257 void free_waiting_rows PROTO((waiting_row **rows, int row_num));
00258 void free_waiting_row_array PROTO((waiting_row ***rows, int row_num));
00259 void free_cuts PROTO((cut_data **lpcuts, int cut_num));
00260 void free_col_set PROTO((our_col_set **colset));
00261 void free_candidate PROTO((branch_obj **cand));
00262 void free_candidate_completely PROTO((branch_obj **cand));
00263 void free_node_dependent PROTO((lp_prob *p));
00264 void free_node_desc PROTO((node_desc **desc));
00265 void free_lp PROTO((lp_prob *p));
00266
00267
00268
00269
00270
00271 int receive_lp_data_u PROTO((lp_prob *p));
00272 void free_prob_dependent_u PROTO((lp_prob *p));
00273 int comp_cut_name PROTO((const void *c0, const void *c1));
00274 int create_subproblem_u PROTO((lp_prob *p));
00275 int is_feasible_u PROTO((lp_prob *p, char branching));
00276 void send_feasible_solution_u PROTO((lp_prob *p, int xlevel, int xindex,
00277 int xiter_num, double lpetol,
00278 double new_ub, int cnt, int *xind,
00279 double *xval));
00280 void display_lp_solution_u PROTO((lp_prob *p, int which_sol));
00281 int select_candidates_u PROTO((lp_prob *p, int *cuts, int *new_vars,
00282 int *cand_num, branch_obj ***candidates));
00283 int compare_candidates_u PROTO((lp_prob *p, double oldobjval,
00284 branch_obj *best,branch_obj *can));
00285 int select_child_u PROTO((lp_prob *p, branch_obj *can, char *action));
00286 void print_branch_stat_u PROTO((lp_prob *p, branch_obj *can, char *action));
00287 void add_to_desc_u PROTO((lp_prob *p, node_desc *desc));
00288 int same_cuts_u PROTO((lp_prob *p, waiting_row *wrow1, waiting_row *wrow2));
00289 void unpack_cuts_u PROTO((lp_prob *p, int from, int type,
00290 int cut_num, cut_data **cuts,
00291 int *new_row_num, waiting_row ***new_rows));
00292 int send_lp_solution_u PROTO((lp_prob *p, int tid));
00293 void logical_fixing_u PROTO((lp_prob *p));
00294 int generate_column_u PROTO((lp_prob *p, int lpcutnum, cut_data **cuts,
00295 int prevind, int nextind, int generate_what,
00296 double *colval, int *colind, int *collen,
00297 double *obj, double *ub, double *lb));
00298 void print_stat_on_cuts_added_u PROTO((lp_prob *p, int added_rows));
00299 void purge_waiting_rows_u PROTO((lp_prob *p));
00300 int generate_cuts_in_lp_u PROTO((lp_prob *p));
00301 char analyze_multicriteria_solution PROTO((lp_prob *p, int *indices,
00302 double *values, int length,
00303 double *true_objval, double etol,
00304 char branching));
00305 #endif
