1 /*===========================================================================*/ 2 /* */ 3 /* This file is part of the SYMPHONY Branch, Cut, and Price Library. */ 4 /* */ 5 /* SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and */ 6 /* Laci Ladanyi (ladanyi@us.ibm.com). */ 7 /* */ 8 /* The author of this file is Menal Guzelsoy */ 9 /* */ 10 /* (c) Copyright 2006-2019 Lehigh University. All Rights Reserved. */ 11 /* */ 12 /* This software is licensed under the Eclipse Public License. Please see */ 13 /* accompanying file for terms. */ 14 /* */ 15 /*===========================================================================*/ 16 /* last modified: January 09, menal*/ 17 18 #ifndef SYM_PREP__H 19 #define SYM_PREP__H 20 21 /* return codes of the functions*/ 22 23 #define PREP_FUNC_SUCCESS 0 24 #define PREP_FUNC_ERROR -1 25 26 #include "symphony.h" 27 #include "sym_types.h" 28 #include "sym_constants.h" 29 #include "sym_prep_params.h" 30 31 #ifdef INF 32 #undef INF 33 #endif 34 #ifdef SYM_INFINITY 35 #define INF SYM_INFINITY 36 #else 37 #define INF 1e20 38 #endif 39 40 #define PREP_QUIT(f) \ 41 ((f != PREP_UNMODIFIED && f != PREP_MODIFIED) ? TRUE : FALSE) 42 43 /*===========================================================================*/ 44 45 /* for sr internal use */ 46 /* Menal's single-row (sr) stuff */ 47 48 #define SR_NO_UPDATES 0 49 #define SR_BOUNDS_UPDATED 1 50 #define SR_INFEAS 2 51 52 #define POS_VAL 0 53 #define ZERO_VAL 1 54 #define NEG_VAL 2 55 56 #define SR_MIN 0 57 #define SR_MAX 1 58 59 #define RND_FLOOR 0 60 #define RND_CEIL 1 61 62 #define VAR_NEW 0 63 #define VAR_IN_BOUND 1 64 65 #define UB_SIDE 0 66 #define LB_SIDE 1 67 #define BOTH_SIDE 2 68 69 /* status of a variable in sr problem */ 70 #define SR_VAR_IN 0 71 #define SR_VAR_IN_FIXED_UB 1 72 #define SR_VAR_IN_FIXED_LB 2 73 #define SR_VAR_IN_FRAC 3 74 #define SR_VAR_FIXED_UB 4 75 #define SR_VAR_FIXED_LB 5 76 77 /*===========================================================================*/ 78 79 /* modification types on a variable */ 80 81 #define FIX_NO_BOUND 0 82 #define FIX_BINARY 1 83 #define FIX_OTHER 2 84 #define FIX_FIXABLE 3 85 #define IMPROVE_UB 4 86 #define IMPROVE_LB 5 87 #define IMPROVE_COEF 6 88 #define FIX_AGGREGATE 7 89 90 /* for a range of variables */ 91 #define FIX_ROW_LB 8 92 #define FIX_ROW_UB 9 93 94 /*===========================================================================*/ 95 /* data structure to keep the statistics */ 96 /*===========================================================================*/ 97 typedef struct PREP_STATS 98 { 99 int rows_deleted; 100 int vars_fixed; 101 int coeffs_nulled; 102 int bounds_integerized; 103 int vars_aggregated; 104 int vars_integerized; 105 int vars_substituted; 106 107 /* regarding coeffs changes and bounds tightening */ 108 int coeffs_changed; 109 char *nz_coeff_changed; 110 111 int bounds_tightened; 112 113 /* regarding uboundedness and infeasiblity */ 114 int col_infeas_ind; 115 int row_infeas_ind; 116 int col_unbound_ind; 117 int col_numeric_ind; 118 }prep_stats; 119 120 /*===========================================================================*/ 121 /* Single Row Relaxation data structure */ 122 /* Under development */ 123 /*===========================================================================*/ 124 typedef struct SRDESC{ 125 126 int prob_type; 127 char sense; 128 double rhs; 129 130 int max_n; /* all variables which are not fixed yet */ 131 double *obj_max; 132 double *matval_max; 133 double *ratio_max; 134 int *matind_max; 135 char *reversed_max; 136 // int *ratio_type_max; 137 double ub_offset; 138 double rhs_max; 139 double sum_c_max; 140 double sum_a_max; 141 142 char ub_updated; 143 double ub; 144 145 int min_n; 146 double *obj_min; 147 double *matval_min; 148 double *ratio_min; 149 int *matind_min; 150 char *reversed_min; 151 // int *ratio_type_min; 152 double lb_offset; 153 double rhs_min; 154 double sum_c_min; 155 double sum_a_min; 156 157 char lb_updated; 158 double lb; 159 160 /* for sorting purposes */ 161 int * fixed_ind; 162 int * tmp_ind; 163 164 /* for variable fixing, bound tightening purpose*/ 165 166 int * var_stat_max; 167 int * var_stat_min; 168 169 double *var_obj_max; 170 double *var_matval_max; 171 172 double *var_obj_min; 173 double *var_matval_min; 174 175 double *var_min_opt; /* for solving the same problem for 176 each variable fixed 177 */ 178 double *var_max_opt; 179 180 }SRdesc; 181 182 /*===========================================================================*/ 183 /* Preprocessing data structure */ 184 /*===========================================================================*/ 185 typedef struct PREPDesc 186 { 187 MIPdesc * mip; 188 MIPdesc * orig_mip; 189 prep_stats stats; 190 prep_params params; 191 192 int has_ub; 193 double ub; 194 195 /* for logical fixing */ 196 int impl_limit; 197 //int impl_var_cnt; /* fixed ones */ 198 IMPlist *list; /* the list under inspection */ 199 int impl_col_ind; 200 prep_stats impl_stats; 201 int impl_row_cnt; 202 int impl_var_cnt; 203 char *impl_vars; 204 205 ROWinfo *impl_rows; 206 COLinfo *impl_cols; 207 208 double *impl_ub; 209 double *impl_lb; 210 211 char *ulist_checked; 212 char *llist_checked; 213 214 /* trying single/aggr row relaxations to improve bounds*/ 215 int max_sr_cnt; 216 int max_aggr_cnt; 217 SRdesc *sr; /* for 'L', 'G' constraints */ 218 SRdesc *d_sr; /* additionally, for 'E' constraints */ 219 /* for subproblems checking purposes */ 220 char *rows_checked; 221 double alloc_time; 222 223 /* will need for sorting etc */ 224 int * user_col_ind; 225 int * user_row_ind; 226 double alloc2_time; 227 double impl_array_time; 228 double impl_cols_time; 229 double impl_rows_time; 230 231 /* keep sol if prep solve the problem */ 232 int xlength; 233 int *xind; 234 double *xval; 235 236 /* temp arrays*/ 237 int *tmpi; /* size max(n,m) */ 238 double *tmpd; 239 char *tmpc; 240 241 }PREPdesc; 242 243 /*===========================================================================*/ 244 /* Data structure to keep relevant info of a column */ 245 246 /* User accessible environment to manage preprocessing 247 -added for user in another package 248 -not used in symphony */ 249 /*=========================================================================*/ 250 251 typedef struct PREP_ENVIRONMENT{ 252 PREPdesc * P; 253 prep_stats stats; 254 prep_params params; 255 int termcode; 256 }prep_environment; 257 258 /*===========================================================================*/ 259 /* Helper data structures */ 260 /* -to be used while searching duplicate rows and cols*/ 261 typedef struct RC_DUP_DESC{ 262 int check_rows; 263 int check_cols; 264 265 char *col_orig_type; 266 int *col_del_ind; 267 int *col_fix_type; 268 double *col_fix_val; 269 270 double *col_sum; 271 double *col_factor; 272 int *c_loc; 273 274 double *row_sum; 275 double *row_factor; 276 int *r_loc; 277 }rc_dup_desc; 278 279 /*===========================================================================*/ 280 281 /* presolve the MIP formulation stored in the current environment */ 282 int sym_presolve(sym_environment *env); 283 284 /* some data structures in root description are initialized before calling 285 * preprocessor. update these after the preprocessor has changed the problem 286 * size. */ 287 int prep_update_rootdesc(sym_environment *env); 288 289 /*load a problem through MIP model description arrays*/ 290 int prep_load_problem(prep_environment *prep, int numcols, int numrows, 291 int *start, int *index, double *value, 292 double *collb, double *colub, char *is_int, 293 double *obj, double obj_offset, char *rowsen, 294 double *rowrhs, double *rowrng, char make_copy); 295 296 /*==========================================================================*/ 297 /*==========================================================================*/ 298 /*==========================================================================*/ 299 300 /* internal functions */ 301 302 /*presolve the desc */ 303 int prep_solve_desc(PREPdesc *P); 304 305 /* initialize the presolve description */ 306 int prep_initialize_mipinfo(PREPdesc *P); 307 308 /* get the row oriented matrix description*/ 309 int prep_fill_row_ordered(PREPdesc *P); 310 311 /* final touchup on the description*/ 312 int prep_cleanup_desc(PREPdesc *P); 313 314 /* integerize the variable bounds */ 315 int prep_integerize_bounds(PREPdesc *P); 316 317 /* integerize a continuous variable */ 318 int prep_integerize_var(PREPdesc *P, int col_ind); 319 320 /* the main presolve loop*/ 321 int prep_basic(PREPdesc *P); 322 323 /* try to improve the bounds of a variable*/ 324 int prep_improve_variable(PREPdesc *P, int col_ind, int row_ind, int a_loc, 325 int dive_level, char check_improve, char impl_mode, 326 char use_sr_bounds, 327 double sr_ub, double sr_lb, int use_mip); 328 329 /* check if the given row is redundant */ 330 int prep_check_redundancy(PREPdesc *P, int row_ind, char use_sr_bounds, 331 double sr_ub, double sr_lb, char impl_mode, 332 int dive_level); 333 334 /* if a column is modified, then update the model*/ 335 int prep_modified_cols_update_info(PREPdesc *P, int col_cnt, int *col_start, 336 int row_ind, int dive_level, 337 double fixed_bound, int fix_type, 338 char check_redundancy, char impl_mode); 339 340 /* for the unbounded variables, check if we can tighten their bounds*/ 341 342 int prep_force_row_bounds(PREPdesc *P, int row_ind, int col_ind, int a_loc); 343 344 /* update the matrix when a row is proved to be redundant*/ 345 int prep_deleted_row_update_info(MIPdesc *mip, int row_ind); 346 347 /* try to find duplicate rows and columns */ 348 int prep_delete_duplicate_rows_cols(PREPdesc *P, char check_rows, 349 char check_cols); 350 /* try to substitute cols */ 351 int prep_substitute_cols(PREPdesc *P); 352 353 int prep_update_single_row_attributes(ROWinfo *rows, int row_ind, double a_val, 354 double obj, double c_lb, double c_ub, 355 int is_int, int var_type, double etol, 356 int entry_loc); 357 /* utility functions */ 358 void prep_sos_fill_var_cnt(PREPdesc *P); 359 void prep_sos_fill_row(ROWinfo *row, int alloc_size, int size, 360 int *ind); 361 362 double prep_rnd_integral(double val, double etol, char rnd_type); 363 int prep_get_row_bounds(MIPdesc *mip, int r_ind, double etol); 364 char prep_is_equal(double lval, double rval, double etol); 365 char prep_is_integral(double val, double etol); 366 367 /* reporting functions */ 368 int prep_declare_fixed_var(int col_ind, char *name, double fixed_bound); 369 int prep_declare_redundant_row(ROWinfo row, int row_ind, char sense, 370 double rhs); 371 int prep_declare_coef_change(int row_ind, int col_ind, 372 char *name, double a_val, 373 double rhs); 374 int prep_report(PREPdesc *P, int termcode); 375 376 int prep_merge_solution(MIPdesc *orig_mip, MIPdesc *prep_mip, int *sol_xlength, 377 int **sol_xind, double **sol_xval); 378 379 int prep_check_feasible(MIPdesc *mip, double *sol, double etol); 380 381 /* implications - under development*/ 382 int prep_add_to_impl_list(IMPlist *list, int ind, int fix_type, 383 double val); 384 int prep_initialize_impl_lists(PREPdesc *P); 385 386 /* experimental - under development */ 387 int prep_solve_sr_rlx(PREPdesc *P, int row_cnt, int *row_indices); 388 389 /*==========================================================================*/ 390 /*==========================================================================*/ 391 /*==========================================================================*/ 392 393 /* functions to solve single row relaxations of the model*/ 394 /* ---- under development ----- not entirely tested*/ 395 396 397 /* initialize/allocate SR description */ 398 void sr_initialize(SRdesc **sr, int n); 399 void sr_allocate(SRdesc **sr, int n); 400 401 /* solve the single row (indexed by row_ind) relaxation*/ 402 int sr_solve_bounded_prob(PREPdesc *P, SRdesc *sr, SRdesc *d_sr, 403 int obj_ind, int row_ind, 404 int *r_matbeg, int *r_matind, double *r_matval, 405 COLinfo *cols, double *ub, double *lb, double etol); 406 /* internal functions: */ 407 /* add a new column to the problem: the description of column is passed in 408 through function arguments*/ 409 int sr_add_new_col(SRdesc *sr, SRdesc *d_sr, double c_val, double a_val, 410 int col_ind, char col_var_type, double col_ub, 411 double col_lb, char sense, int col_type, 412 int col_bound_type); 413 /* add a new column to the problem: the description of column is passed in 414 through function arguments - here we know that it is bounded*/ 415 int sr_add_new_bounded_col(SRdesc *sr, double c_val, double a_val, 416 int col_ind, 417 double rhs_ub_offset, double rhs_lb_offset, 418 double obj_ub_offset, double obj_lb_offset, 419 double col_ub, double col_lb, int obj_sense, 420 char var_type); 421 /* helper functions */ 422 int sr_find_opt_bounded(PREPdesc *P, SRdesc *sr, int obj_ind, 423 double *ub, double *lb); 424 425 int sr_solve_open_prob(PREPdesc *P, SRdesc *sr, int obj_ind, 426 int row_ind, int *r_matbeg, 427 int *r_matind, double *r_matval, COLinfo *cols, 428 double *ub, double *lb, double etol); 429 430 void free_rc_dup_desc(rc_dup_desc *prep_desc); 431 void free_prep_desc(PREPdesc *P); 432 void free_sr_desc(SRdesc *sr); 433 void free_imp_list(IMPlist **list); 434 #endif 435