1 /*===========================================================================*/ 2 /* */ 3 /* This file is part of the SYMPHONY MILP Solver Framework. */ 4 /* */ 5 /* SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and */ 6 /* Laci Ladanyi (ladanyi@us.ibm.com). */ 7 /* */ 8 /* (c) Copyright 2000-2019 Ted Ralphs. All Rights Reserved. */ 9 /* */ 10 /* This software is licensed under the Eclipse Public License. Please see */ 11 /* accompanying file for terms. */ 12 /* */ 13 /*===========================================================================*/ 14 15 #ifndef _LP_H 16 #define _LP_H 17 18 #define COMPILING_FOR_LP 19 20 #include "symphony.h" 21 #include "sym_timemeas.h" 22 #include "sym_lp_params.h" 23 #include "sym_types.h" 24 #include "sym_lp_solver.h" 25 #include "sym_lp_u.h" 26 27 #ifdef COMPILE_IN_CG 28 #include "sym_cg.h" 29 #endif 30 31 #ifdef COMPILE_IN_CP 32 #include "sym_cp.h" 33 #endif 34 35 #ifdef COMPILE_IN_LP 36 #include "sym_tm.h" 37 #endif 38 39 /*===========================================================================*/ 40 /*===========================================================================*/ 41 42 typedef struct OUR_COL_SET{ 43 int dual_feas; 44 45 int rel_lb; 46 int *rel_lb_ind; 47 int rel_ub; 48 int *rel_ub_ind; 49 50 int num_vars; 51 int *userind; 52 53 double *objx; 54 double *lb; 55 double *ub; 56 int *matbeg; 57 int *matind; 58 double *matval; 59 int nzcnt; 60 }our_col_set; 61 62 /*===========================================================================*/ 63 typedef struct LP_PROB{ 64 double str_time; 65 66 int proc_index; 67 void *user; 68 69 lp_params par; 70 71 int has_ub; 72 double ub; 73 74 double root_objval; 75 76 int phase; 77 78 double start_time; 79 80 base_desc base; 81 82 branch_desc *bdesc; /* there are p->bc_level branch_desc's */ 83 bounds_change_desc *bnd_changes; /* there are p->bc_level bnd_change's */ 84 int bdesc_size; 85 86 int master; 87 int draw_graph; 88 int tree_manager; 89 int cut_pool; 90 int cut_gen; 91 92 #ifdef COMPILE_IN_CG 93 cg_prob *cgp; 94 #endif 95 #ifdef COMPILE_IN_LP 96 tm_prob *tm; 97 #endif 98 lp_sol best_sol; 99 double obj[2]; 100 double utopia[2]; 101 int has_mc_ub; 102 double mc_ub; 103 104 double tt; 105 node_times comp_times; 106 lp_stat_desc lp_stat; 107 108 node_desc *desc; 109 int bc_index; 110 int bc_level; 111 int vars_at_ub; 112 int vars_at_lb; 113 int vars_deletable; /* a subset of vars at LB */ 114 115 int dive; 116 int colgen_strategy; 117 char colgen_happened; 118 char colset_changed; 119 120 int iter_num; 121 int node_iter_num; 122 int bound_changes_in_iter; 123 int vars_recently_fixed_to_ub; 124 LPdata *lp_data; 125 MIPdesc *mip; /* Holds the MIP description when read in from MPS */ 126 127 double last_gap; 128 double *obj_history; 129 int has_tailoff; 130 int obj_no_impr_iters; 131 132 //double str_br_impr_count; /* if we dont have 3 consequent 133 // improvements, return to initials */ 134 135 /*========================================================================*\ 136 * The following fields refer to the cuts/rows arrived to the LP, 137 * but not yet added 138 \*========================================================================*/ 139 140 int waiting_row_num; 141 waiting_row **waiting_rows; 142 int waiting_rows_size; 143 144 /*========================================================================*\ 145 * The following fields refer to the rows that once have been added to 146 * the problem, but became slack 147 \*========================================================================*/ 148 149 int slack_cut_num; 150 cut_data **slack_cuts; 151 int slack_cuts_size; 152 153 /* pseudo costs and reliability measures */ 154 double *pcost_down; 155 double *pcost_up; 156 int *br_rel_down; 157 int *br_rel_up; 158 int *br_inf_down; 159 int *br_inf_up; 160 int *br_rel_cand_list; 161 char str_br_check; 162 int *br_rel_down_min_level; 163 int *br_rel_up_min_level; 164 double str_check_obj; 165 int str_check_trial; 166 int str_check_freq; 167 int str_check_cnt; 168 169 int var_rank_cnt; 170 double *var_rank; 171 double *root_lp; 172 173 int *frac_var_cnt; 174 175 int branch_var; 176 char branch_dir; 177 178 double cgl_init_obj; 179 int cgl_chain_stop; 180 int cgl_chain_stop_cnt; 181 int cgl_chain_pause_cnt; 182 183 double cgl_impr; 184 int cgl_impr_cnt; 185 int is_diving; 186 }lp_prob; 187 188 /*===========================================================================*/ 189 /*============= LP general purpose functions (lp_genfunc.c) =================*/ 190 /*===========================================================================*/ 191 192 lp_prob *get_lp_ptr PROTO((lp_prob **lp_list)); 193 int lp_initialize PROTO((lp_prob *p, int master_tid)); 194 int process_chain PROTO((lp_prob *p)); 195 int fathom_branch PROTO((lp_prob *p)); 196 int check_bounds PROTO((lp_prob *p, int *termcode)); 197 int fathom PROTO((lp_prob *p, int primal_feasible, int time_limit_reached)); 198 int repricing PROTO((lp_prob *p)); 199 int bfind PROTO((int key, int *table, int size)); 200 int collect_nonzeros PROTO((lp_prob *p, double *x, int *tind, double *tx)); 201 int collect_fractions PROTO((lp_prob *p, double *x, int *tind, double *tx)); 202 int collect_int_fractions PROTO((lp_prob *p, double *x, int *tind, double *tx, int *int_cnt)); 203 node_desc *create_explicit_node_desc PROTO((lp_prob *p)); 204 int check_tailoff PROTO((lp_prob *p)); 205 void lp_exit PROTO((lp_prob *p)); 206 void lp_close PROTO((lp_prob *p)); 207 int generate_cgl_cuts_new PROTO((lp_prob *p, int *num_cuts, cut_data ***cuts, 208 int send_to_pool, int *bound_changes)); 209 int should_use_cgl_generator PROTO ((lp_prob *p, int *should_generate, 210 int which_generator, void *generator)); 211 int generate_cgl_cut_of_type PROTO((lp_prob *p, int i, OsiCuts *cutlist_p, 212 int *was_tried)); 213 int check_and_add_cgl_cuts PROTO((lp_prob *p, int i, cut_data ***cuts, int *num_cuts, int *bound_changes, OsiCuts *cutlist, int send_to_pool)); 214 int should_stop_adding_cgl_cuts PROTO((lp_prob *p, int i, int *should_stop)); 215 int add_col_cuts PROTO((lp_prob *p, OsiCuts *cutlist, int *bound_changes)); 216 int add_cut_to_mip_inf PROTO((lp_prob *p, int cut_n, int *cut_ind, double *cut_val, double cut_rhs, char cut_sense)); 217 int update_pcost PROTO ((lp_prob *p)); 218 int str_br_bound_changes PROTO((lp_prob *p, int num_bnd_changes, 219 double *bnd_val, int *bnd_ind, char *bnd_sense)); 220 221 /*===========================================================================*/ 222 /*======== LP functions related to variable management (lp_varfunc.c) =======*/ 223 /*===========================================================================*/ 224 225 void add_col_set PROTO((lp_prob *p, our_col_set *new_cols)); 226 void colind_sort_extra PROTO((lp_prob *p)); 227 void userind_sort_extra PROTO((lp_prob *p)); 228 void tighten_bounds PROTO((lp_prob *p)); 229 int save_root_reduced_costs(lp_prob *p); 230 //int tighten_root_bounds(lp_prob *p); 231 our_col_set *price_all_vars PROTO((lp_prob *p)); 232 int restore_lp_feasibility PROTO((lp_prob *p, our_col_set *new_cols)); 233 void userind_sort_extra PROTO((lp_prob *p)); 234 void colind_sort_extra PROTO((lp_prob *p)); 235 int var_uind_comp PROTO((const void *v0, const void *v1)); 236 int var_cind_comp PROTO((const void *v0, const void *v1)); 237 238 /*===========================================================================*/ 239 /*========== LP functions related to row management (lp_rowfunc.c) ==========*/ 240 /*===========================================================================*/ 241 242 int check_row_effectiveness PROTO((lp_prob *p)); 243 void add_row_set PROTO((lp_prob *p, waiting_row **wrows, int length)); 244 void add_new_rows_to_waiting_rows PROTO((lp_prob *p, waiting_row **new_rows, 245 int new_row_num)); 246 void order_waiting_rows_based_on_sender PROTO((lp_prob *p)); 247 int add_best_waiting_rows PROTO((lp_prob *p)); 248 void add_waiting_rows PROTO((lp_prob *p, waiting_row **wrows,int add_row_num)); 249 int waiting_row_comp PROTO((const void *wr0, const void *wr1)); 250 int compute_violations PROTO((lp_prob *p, 251 int new_row_num, waiting_row **new_rows)); 252 void compress_slack_cuts PROTO((lp_prob *p)); 253 254 /*===========================================================================*/ 255 /*================= LP branching functions (lp_branch.c) ====================*/ 256 /*===========================================================================*/ 257 258 void add_slacks_to_matrix PROTO((lp_prob *p, int cand_num, 259 branch_obj **candidates)); 260 int add_violated_slacks PROTO((lp_prob *p, int cand_num, 261 branch_obj **candidates)); 262 int select_branching_object PROTO((lp_prob *p, int *cuts, 263 branch_obj **can)); 264 int should_continue_strong_branching PROTO((lp_prob *p, int i, int cand_num, 265 double st_time, int total_iters, 266 int *should_continue)); 267 int strong_branch(lp_prob *p, int branch_var, double lb, double ub, 268 double new_lb, double new_ub, double *obj, int should_use_hot_starts, 269 int *termstatus, int *iterd, int sos_cnt, int *sos_ind); 270 int branch PROTO((lp_prob *p, int cuts)); 271 int col_gen_before_branch PROTO((lp_prob *p, int *new_vars)); 272 273 int prep_tighten_bounds PROTO((LPdata *lp_data, int *num_changes, double *bnd_val, int *bnd_ind, 274 char *bnd_sense, double *row_ub, double *row_lb, char *cand_fixed)); 275 int prep_row_violated PROTO((double row_lb, double row_ub, double si_row_lb, double si_row_ub, 276 double aval, double old_col_lb, double old_col_ub, 277 double new_col_lb, double new_col_ub, double lpetol, 278 double inf)); 279 int prep_col_fixable PROTO((double xval, double aval, double c_lb, double c_ub, 280 double row_lb, double row_ub, double si_row_lb, double si_row_ub, 281 double *col_fixed_lb, double *col_fixed_ub, double etol, 282 double inf)); 283 /*----------- Generic selection rules to be used by the user ----------------*/ 284 285 void branch_close_to_half PROTO((lp_prob *p, int max_cand_num, int *cand_num, 286 branch_obj ***candidates)); 287 void branch_close_to_half_and_expensive PROTO((lp_prob *p, int max_cand_num, 288 int *cand_num, 289 branch_obj ***candidates)); 290 void branch_close_to_one_and_cheap PROTO((lp_prob *p, int max_cand_num, 291 int *cand_num, 292 branch_obj ***candidates)); 293 /*===========================================================================*/ 294 /*================ LP communication functions (lp_proccomm.c) ===============*/ 295 /*===========================================================================*/ 296 297 void check_ub PROTO((lp_prob *p)); 298 int process_message PROTO((lp_prob *p, int r_bufid, int *pindex, int *pitnum)); 299 void lp_process_ub_message PROTO((lp_prob *p)); 300 int receive_active_node PROTO((lp_prob *p)); 301 int receive_cuts PROTO((lp_prob *p, int first_lp, int no_more_cuts_count)); 302 void send_node_desc PROTO((lp_prob *p, int node_type)); 303 array_desc pack_array_desc_diff PROTO((array_desc *ad, array_desc *new_ad, 304 int *itmp)); 305 basis_desc pack_basis_diff PROTO((node_desc *oldnode, node_desc *newnode, 306 char uind_type, char cutind_type, 307 int *itmp)); 308 char pack_base_diff PROTO((int *size, int *oldstat, int *newstat, int *itmp)); 309 char pack_extra_diff PROTO((array_desc *olddesc, int *oldstat, 310 array_desc *newdesc, int *newstat, 311 char oldbasis_type_in_tm, char newdesc_type_in_tm, 312 int *itmp, int *size)); 313 void send_branching_info PROTO((lp_prob *p, branch_obj *can, char *action, 314 int *keep)); 315 void send_lp_is_free PROTO((lp_prob *p)); 316 void send_cuts_to_pool PROTO((lp_prob *p, int eff_cnt_limit)); 317 int add_bound_changes_to_desc PROTO((node_desc *new_tm_desc, lp_prob *p)); 318 int update_cut_parameters(lp_prob *p); 319 int update_solve_parameters(lp_prob *p); 320 321 /*===========================================================================*/ 322 /*======================= Freeing things (lp_free.c) ========================*/ 323 /*===========================================================================*/ 324 325 void free_cut PROTO((cut_data **lpcut)); 326 void free_waiting_row PROTO((waiting_row **wrow)); 327 void free_waiting_rows PROTO((waiting_row **rows, int row_num)); 328 void free_waiting_row_array PROTO((waiting_row ***rows, int row_num)); 329 void free_cuts PROTO((cut_data **lpcuts, int cut_num)); 330 void free_col_set PROTO((our_col_set **colset)); 331 void free_candidate PROTO((branch_obj **cand)); 332 void free_candidate_completely PROTO((branch_obj **cand)); 333 void free_node_dependent PROTO((lp_prob *p)); 334 void free_node_desc PROTO((node_desc **desc)); 335 void free_lp PROTO((lp_prob *p)); 336 337 /*===========================================================================*/ 338 /*==================== LP wrapper functions (lp_wrapper.c) ==================*/ 339 /*===========================================================================*/ 340 341 int receive_lp_data_u PROTO((lp_prob *p)); 342 void free_prob_dependent_u PROTO((lp_prob *p)); 343 int comp_cut_name PROTO((const void *c0, const void *c1)); 344 int create_subproblem_u PROTO((lp_prob *p)); 345 int is_feasible_u PROTO((lp_prob *p, char branching, char is_last_iter)); 346 void send_feasible_solution_u PROTO((lp_prob *p, int xlevel, int xindex, 347 int xiter_num, double lpetol, 348 double new_ub, int cnt, int *xind, 349 double *xval)); 350 void display_lp_solution_u PROTO((lp_prob *p, int which_sol)); 351 int select_candidates_u PROTO((lp_prob *p, int *cuts, int *new_vars, 352 int *cand_num, branch_obj ***candidates)); 353 int compare_candidates_u PROTO((lp_prob *p, double oldobjval, 354 branch_obj *best,branch_obj *can)); 355 int select_child_u PROTO((lp_prob *p, branch_obj *can, char *action)); 356 void print_branch_stat_u PROTO((lp_prob *p, branch_obj *can, char *action)); 357 void add_to_desc_u PROTO((lp_prob *p, node_desc *desc)); 358 int same_cuts_u PROTO((lp_prob *p, waiting_row *wrow1, waiting_row *wrow2)); 359 void unpack_cuts_u PROTO((lp_prob *p, int from, int type, 360 int cut_num, cut_data **cuts, 361 int *new_row_num, waiting_row ***new_rows)); 362 int send_lp_solution_u PROTO((lp_prob *p, int tid)); 363 void logical_fixing_u PROTO((lp_prob *p)); 364 int generate_column_u PROTO((lp_prob *p, int lpcutnum, cut_data **cuts, 365 int prevind, int nextind, int generate_what, 366 double *colval, int *colind, int *collen, 367 double *obj, double *ub, double *lb)); 368 void print_stat_on_cuts_added_u PROTO((lp_prob *p, int added_rows)); 369 void purge_waiting_rows_u PROTO((lp_prob *p)); 370 int generate_cuts_in_lp_u PROTO((lp_prob *p)); 371 int analyze_multicriteria_solution PROTO((lp_prob *p, int *indices, 372 double *values, int length, 373 double *true_objval, double etol, 374 char branching, int feasible)); 375 #endif 376