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 _BB_TYPES_H 16 #define _BB_TYPES_H 17 18 #define MAX_CHILDREN_NUM 4 19 #define MAX_CHANGE_NUM 6 20 21 /*===========================================================================*\ 22 * This file contains those type definitions which are used in more than one 23 * process of the black box model. 24 \*===========================================================================*/ 25 26 #if !defined (_MSC_VER) 27 #include <unistd.h> /* this defines sleep() */ 28 #endif 29 30 #include "sym_proto.h" 31 #include "sym_constants.h" 32 33 typedef struct LP_SOL{ 34 int lp; /* the tid of the lp process asssociated with 35 the current solution */ 36 int has_sol; /* indicates whether a feasible solution 37 found*/ 38 int xlength; /* the number of nonzeros in the lp solution 39 currently being processed*/ 40 int xlevel; /* the level at which the current solution was 41 generated*/ 42 int xindex; 43 int xiter_num; 44 int max_sol_length; 45 int *xind; /* the indices of the nonzeros in the current 46 solution*/ 47 double *xval; /* the values of the nonzeros in the current 48 solution*/ 49 double objval; /* the objective function value of the current 50 relaxation*/ 51 double lpetol; 52 }lp_sol; 53 54 typedef struct BASE_DESC{ 55 int varnum; 56 int *userind; 57 #if 0 58 double *lb; /* even if there are global lb and ub, we */ 59 double *ub; /* fill these arrays out */ 60 #endif 61 int cutnum; 62 }base_desc; 63 64 /*===========================================================================*\ 65 * Stores the data corresponding to a particular cut 66 \*===========================================================================*/ 67 68 typedef struct CUT_DATA{ 69 int size; /* the size of the coef array */ 70 char *coef; /* an array which contains the data necessary to 71 construct the cut -- it is stored in a 72 packed form. The types of the cut tells how 73 to "unpack" it */ 74 double rhs; /* the right hand side for the constraint*/ 75 double range; 76 char type; /* the type of cut */ 77 char sense; /* sense of the cut constraint */ 78 char deletable; /* whether or not this cut should be removed 79 from the LP after being added */ 80 int branch; /* shows whether we can branch on its cut if 81 this row becomes slack */ 82 int name; /* internal to the BB. The identifier of the 83 cut. >=0 if exists, -1 if does not exist yet, 84 but the cuT is sent to the cutpool, -2 if 85 no name & no pool */ 86 }cut_data; 87 88 typedef struct ROW_DATA{ 89 cut_data *cut; 90 int ineff_cnt; 91 int eff_cnt; 92 char free; 93 char deletable; 94 }row_data; 95 96 typedef struct WAITING_ROW{ 97 int source_pid; 98 cut_data *cut; 99 int *matind; 100 double *matval; 101 int nzcnt; 102 double violation; 103 }waiting_row; 104 105 /*===========================================================================*\ 106 * The following three definitions are used to describe the search tree 107 * nodes. 108 \*===========================================================================*/ 109 110 typedef struct VAR_DESC{ 111 int userind; 112 int colind; 113 double lb; /* lb on var before we start processing lp_prob */ 114 double ub; /* ub on var before we start processing lp_prob */ 115 double new_lb; /* lb may change due to rc fixing or cuts */ 116 double new_ub; /* ub may change due to rc fixing or cuts */ 117 char is_int; /* whether or not the variable is integer */ 118 }var_desc; 119 120 /*========================================================================*\ 121 * changes in bounds of variables at a node are stored here. 122 * Only the changes pertaining to this node are stored here. changes in 123 * parents are not stored with children. Variable bounds can changed due to 124 * reduced cost fixing, cuts etc. 125 \*========================================================================*/ 126 typedef struct BOUNDS_CHANGE_DESC{ 127 int num_changes; /* how many bounds changed */ 128 int *index; /* max size 2*n */ 129 char *lbub; /* ub or lb? */ 130 double *value; /* new bound value */ 131 }bounds_change_desc; 132 133 134 typedef struct BRANCH_DESC{ 135 int name; /* the userind/cut name depending on the type */ 136 char type; /* description of the child. All of them are 137 natural for branching cuts. For branching 138 variables they should be interpreted as if 139 we were adding a cut with a single variable 140 on the left hand side */ 141 char sense; 142 double rhs; 143 double range; 144 int branch; 145 int sos_cnt; 146 int *sos_ind; 147 }branch_desc; 148 149 typedef struct ARRAY_DESC{ 150 char type; /* NO_DATA_STORED, EXPLICIT_LIST, WRT_PARENT */ 151 int size; 152 int added; 153 int *list; 154 }array_desc; 155 156 typedef struct DOUBLE_ARRAY_DESC{ 157 char type; /* NO_DATA_STORED, EXPLICIT_LIST, WRT_PARENT */ 158 int size; /* the size of list, stat */ 159 int *list; 160 int *stat; 161 }double_array_desc; 162 163 typedef struct BASIS_DESC{ 164 char basis_exists; 165 166 /*========================================================================*\ * Notes: 167 * 1) for base...: 168 * if list is non-NULL then it refers to col/row inds, not userinds 169 * or cut names. 170 * 2) the stat field of extra... ponts into the stat field of base... 171 * 3) if extra... is EXPLICIT_LIST then the node_desc structure's 172 * cutind/uind fields should be used. 173 * 4) EXPLICIT_LIST in uind implies that extravars is explicit, 174 * EXPLICIT_LIST in cutind implies that extrarows is explicit. 175 \*========================================================================*/ 176 double_array_desc basevars; 177 double_array_desc extravars; 178 double_array_desc baserows; 179 double_array_desc extrarows; 180 }basis_desc; 181 182 typedef struct NODE_DESC{ 183 /*========================================================================*\ 184 * The userindices of variables in this node (but not for the base 185 * variables); The basis header for this node; The not-yet-permanently-fixed 186 * variables (again, no base variable is listed here); and the cuts at 187 * this node 188 \*========================================================================*/ 189 array_desc uind; 190 basis_desc basis; 191 array_desc not_fixed; 192 int nf_status; /* NF_CHECK_ALL, NF_CHECK_AFTER_LAST, 193 NF_CHECK_UNTIL_LAST, NF_CHECK_NOTHING */ 194 array_desc cutind; 195 #if defined(COMPILING_FOR_LP) || defined(COMPILING_FOR_MASTER) || defined(COMPILE_IN_LP) 196 cut_data **cuts; /* this is not used in TM anyway. */ 197 #endif 198 199 bounds_change_desc *bnd_change; /* changes in variable bounds that happen 200 during the processing of the node */ 201 202 /* Any additional info the user might want to pass */ 203 int desc_size; 204 char *desc; 205 206 int frac_cnt; 207 int *frac_vars; 208 }node_desc; 209 210 typedef struct BRANCH_OBJ{ 211 char type; /* Type of the candidate */ 212 #if defined(COMPILING_FOR_LP) || defined(COMPILE_IN_LP) 213 int position; /* The position of the candidate */ 214 waiting_row *row; /* Description of the left hand side; makes 215 sense only for branching cuts */ 216 #endif 217 int child_num; /* Number of kids */ 218 #if defined(COMPILING_FOR_TM) || defined(COMPILING_FOR_MASTER) || defined(COMPILE_IN_LP) 219 int name; /* userind for VAR, the index for CUT */ 220 #endif 221 double value; /* for evaluating pcost */ 222 223 /*========================================================================* \ 224 * Description of the children. 225 * All of them are natural for branching cuts. 226 * For branching variables they should be interpreted as if we were adding 227 * a cut with a single variable on the left hand side 228 \*========================================================================*/ 229 /* regarding implicit sos1 branching */ 230 231 #ifdef MAX_CHILDREN_NUM 232 char sense[MAX_CHILDREN_NUM]; 233 double rhs[MAX_CHILDREN_NUM]; 234 double range[MAX_CHILDREN_NUM]; 235 int branch[MAX_CHILDREN_NUM]; 236 int sos_cnt[MAX_CHILDREN_NUM]; 237 int *sos_ind[MAX_CHILDREN_NUM]; 238 #ifdef COMPILE_FRAC_BRANCHING 239 int frac_num[MAX_CHILDREN_NUM]; 240 int *frac_ind[MAX_CHILDREN_NUM]; 241 double *frac_val[MAX_CHILDREN_NUM]; 242 #endif 243 #else 244 char *sense; 245 double *rhs; 246 double *range; 247 int *branch; 248 int *sos_cnt; 249 int **sos_ind; 250 #ifdef COMPILE_FRAC_BRANCHING 251 int *frac_num; 252 int **frac_ind; 253 double **frac_val; 254 #endif 255 #endif 256 257 #if defined(COMPILING_FOR_LP) || defined(COMPILE_IN_LP) 258 double lhs; /* purely for the user */ 259 260 #ifdef MAX_CHILDREN_NUM 261 double objval[MAX_CHILDREN_NUM]; /* arrays of size 'number' */ 262 int termcode[MAX_CHILDREN_NUM]; 263 int iterd[MAX_CHILDREN_NUM]; 264 int feasible[MAX_CHILDREN_NUM]; 265 int is_est[MAX_CHILDREN_NUM]; 266 267 #else 268 double *objval; /* arrays of size 'number' */ 269 int *termcode; 270 int *iterd; 271 int *feasible; 272 273 #endif 274 275 #endif 276 int *sol_sizes; 277 int **sol_inds; 278 double **solutions; 279 #ifdef SENSITIVITY_ANALYSIS 280 double **duals; 281 #endif 282 283 }branch_obj; 284 285 /*===========================================================================*/ 286 287 typedef struct STR_INT{ 288 char str[MAX_LINE_LENGTH +1]; 289 int code; 290 }str_int; 291 292 /*===========================================================================*\ 293 * This is the time measurement structure for an LP node 294 \*===========================================================================*/ 295 296 typedef struct NODE_TIMES{ 297 double communication; 298 double lp; 299 double lp_setup; 300 double separation; 301 double fixing; 302 double pricing; 303 double strong_branching; 304 double wall_clock_lp; 305 double ramp_up_tm; 306 double ramp_up_lp; 307 double ramp_down_time; 308 double idle_diving; 309 double idle_node; 310 double idle_names; 311 double idle_cuts; 312 double start_node; 313 double cut_pool; 314 315 /* cuts */ 316 double cuts; 317 double gomory_cuts; 318 double knapsack_cuts; 319 double oddhole_cuts; 320 double clique_cuts; 321 double probing_cuts; 322 double mir_cuts; 323 double twomir_cuts; 324 double flowcover_cuts; 325 double rounding_cuts; 326 double lift_and_project_cuts; 327 double landp_cuts; 328 double redsplit_cuts; 329 double dupes_and_bad_coeffs_in_cuts; 330 331 double fp; /* feasibility pump */ 332 double ls; /* local search */ 333 double ds; /* diving search */ 334 double ds_type[DIVING_HEURS_CNT]; 335 double rh; /* rounding */ 336 double sh; /* shifting */ 337 double fr; /* fix-and-relax */ 338 double rs; /* rins */ 339 double lb; /* local branching */ 340 double primal_heur; /* all primal heuristics */ 341 }node_times; 342 343 /*===========================================================================*\ 344 * Here we keep track of the computation time for each of the various 345 * parts of the computation 346 \*===========================================================================*/ 347 348 typedef struct PROB_TIMES{ 349 double readtime; /* time spent reading in the problem*/ 350 node_times bc_time; 351 double ub_overhead; /* overhead time used doing the upper bounding */ 352 double ub_heurtime; /* actual comp time doing the upper bounding */ 353 double lb_overhead; /* overhead time doing the lower bounding */ 354 double lb_heurtime; /* actual comp time doing the lower bounding */ 355 }prob_times; 356 357 /*===========================================================================*\ 358 * The bc_node data structure stores the information needed to 359 * process a node in the branch and cut tree 360 \*===========================================================================*/ 361 362 typedef struct BC_NODE{ 363 int bc_index; /* the identifier of the node */ 364 int bc_level; /* the level in the tree of the node */ 365 int iter_num; /* cuts/cgl iteration number */ 366 367 int lp; /* the tid of the lp processing the node */ 368 int cg; /* the tid of the cut generator serving the node */ 369 int cp; /* the tid of the cut pool assigned to the node */ 370 double lower_bound; /* the current best objective function value 371 obtained in the subproblem */ 372 int update_pc; /* whether the pseudo cost should be updated after 373 solving the LP */ 374 double opt_estimate; /* an estimate of the value of the best feasible 375 solution that could be obtained in this node */ 376 struct BC_NODE *parent; 377 struct BC_NODE **children; 378 branch_obj bobj; 379 380 node_desc desc; /* the description of the node, 381 defined in "sym_types.h" */ 382 char node_status; 383 384 int feasibility_status; 385 int sol_size; 386 int *sol_ind; 387 double *sol; 388 #ifdef SENSITIVITY_ANALYSIS 389 double *duals; 390 double C_LP; 391 double B_IP; 392 #endif 393 394 #ifdef TRACE_PATH 395 char optimal_path; 396 #endif 397 398 /* usage of different tools in process chain: fp, cuts, strong branching */ 399 int num_cut_iters_in_path; 400 int num_cuts_added_in_path; 401 int num_cuts_slacked_out_in_path; 402 double avg_cuts_obj_impr_in_path; 403 double start_objval; 404 double end_objval; 405 char cuts_tried; 406 char cuts_forced; 407 int num_str_br_cands_in_path; 408 double avg_br_obj_impr_in_path; 409 char used_str; 410 int t_cnt; 411 412 int num_fp_calls_in_path; 413 int frac_cnt; 414 double frac_avg; 415 }bc_node; 416 417 /*===========================================================================*\ 418 * Keeps problem statistics 419 \*===========================================================================*/ 420 421 typedef struct PROBLEM_STAT{ 422 double root_lb; 423 int cuts_in_pool; 424 int max_depth; /* keeps track of the deepest level reached 425 in the tree so far */ 426 int chains; /* the number of diving chains */ 427 int diving_halts; /* how many times was an already started 428 dive stopped */ 429 int tree_size; /* number of search tree nodes */ 430 int created; /* the number of created nodes (not 431 necessarily the same as tree_size 432 (trimming...) */ 433 int analyzed; /* the number of analyzed (i.e., CG-LP 434 iteration) nodes (not necessarily same 435 as created, leaves can be cut off 436 without analyzing; trimming) */ 437 int leaves_before_trimming; 438 int leaves_after_trimming; 439 int vars_not_priced; /* How many variables did not price out 440 after the first phase */ 441 int nf_status; /* nf_status of the root node after 442 repricing */ 443 double max_vsize; 444 int print_stats_cnt; 445 }problem_stat; 446 447 /*===========================================================================*/ 448 449 typedef struct LP_STAT{ 450 /* LP solver */ 451 int lp_calls; /* total lp_calls */ 452 int lp_node_calls; /* total lp_calls in node processing */ 453 int lp_sols; 454 int ip_sols; 455 int lp_iter_num; 456 int lp_total_iter_num; /* number of total simplex iterations */ 457 int lp_max_iter_num; /* max of lps' simplex iterations */ 458 int str_br_lp_calls; /* no of calls from strong branching */ 459 int str_br_bnd_changes; /* no of bounds changed due to strong br */ 460 int str_br_nodes_pruned; /* no of nodes pruned by strong br */ 461 int str_br_total_iter_num; /* number of total simplex iterations by 462 strong br*/ 463 int prep_bnd_changes; 464 int prep_nodes_pruned; 465 466 int rel_br_full_solve_num; 467 int rel_br_pc_up_num; 468 int rel_br_up_update; 469 int rel_br_pc_down_num; 470 int rel_br_down_update; 471 int rel_br_impr_num; 472 /* cuts */ 473 int cuts_generated; 474 int gomory_cuts; 475 int knapsack_cuts; 476 int oddhole_cuts; 477 int clique_cuts; 478 int probing_cuts; 479 int mir_cuts; 480 int twomir_cuts; 481 int flowcover_cuts; 482 int rounding_cuts; 483 int lift_and_project_cuts; 484 int landp_cuts; 485 int redsplit_cuts; 486 487 int cuts_root; 488 int gomory_cuts_root; 489 int knapsack_cuts_root; 490 int oddhole_cuts_root; 491 int clique_cuts_root; 492 int probing_cuts_root; 493 int mir_cuts_root; 494 int twomir_cuts_root; 495 int flowcover_cuts_root; 496 int rounding_cuts_root; 497 int lift_and_project_cuts_root; 498 int landp_cuts_root; 499 int redsplit_cuts_root; 500 501 int num_poor_cuts; 502 int num_duplicate_cuts; 503 int num_unviolated_cuts; 504 int cuts_added_to_lps; 505 int cuts_deleted_from_lps; 506 507 int gomory_calls; 508 int gomory_nz; 509 int knapsack_calls; 510 int oddhole_calls; 511 int clique_calls; 512 int probing_calls; 513 int mir_calls; 514 int twomir_calls; 515 int flowcover_calls; 516 int rounding_calls; 517 int lift_and_project_calls; 518 int landp_calls; 519 int redsplit_calls; 520 521 /* feasibility pump */ 522 int fp_calls; 523 int fp_lp_calls; 524 int fp_num_sols; 525 int fp_poor_sols; 526 int fp_lp_total_iter_num; 527 int fp_num_iter; 528 int fp_last_call_ind; 529 530 /* rounding heuristic*/ 531 int rh_calls; 532 int rh_num_sols; 533 int rh_last_call_ind; 534 535 /* shifting heuristic*/ 536 int sh_calls; 537 int sh_num_sols; 538 int sh_last_call_ind; 539 540 /* local search */ 541 int ls_calls; 542 int ls_num_sols; 543 int ls_last_call_ind; 544 545 /* diving */ 546 int ds_calls; 547 int ds_num_sols; 548 int ds_type_calls[DIVING_HEURS_CNT]; 549 int ds_type_num_sols[DIVING_HEURS_CNT]; 550 int ds_type_num_iter[DIVING_HEURS_CNT]; 551 int ds_num_iter; 552 int ds_last_call_ind; 553 554 /* fix-and-relax */ 555 int fr_calls; 556 int fr_num_sols; 557 int fr_last_call_ind; 558 int fr_analyzed_nodes; 559 int fr_last_sol_call; 560 561 /* rins search */ 562 int rs_calls; 563 int rs_num_sols; 564 int rs_last_call_ind; 565 int rs_analyzed_nodes; 566 int rs_last_sol_call; 567 568 /* local branching */ 569 int lb_calls; 570 int lb_num_sols; 571 int lb_last_call_ind; 572 int lb_analyzed_nodes; 573 int lb_last_sol_call; 574 575 /* usage of different tools in process chain: fp, cuts, strong branching */ 576 int num_cut_iters_in_path; 577 int num_cuts_added_in_path; 578 int num_cuts_slacked_out_in_path; 579 double avg_cuts_obj_impr_in_path; 580 double start_objval; 581 double end_objval; 582 int num_str_br_cands_in_path; 583 double avg_br_obj_impr_in_path; 584 585 int num_fp_calls_in_path; 586 int chain_cuts_trial_num; 587 int node_cuts_tried; 588 int node_cuts_forced; 589 }lp_stat_desc; 590 591 592 typedef struct RC_DESC{ 593 int size; 594 int num_rcs; 595 int **indices; 596 double **values; 597 double **ub; 598 double **lb; 599 double *obj; 600 int *cnt; 601 }rc_desc; 602 603 /*===========================================================================*/ 604 /* Implications */ 605 /*===========================================================================*/ 606 /*===========================================================================*/ 607 typedef struct COL_IMP{ 608 609 int col_ind; 610 struct COL_IMP *c_next; 611 612 }col_imp; 613 614 typedef struct IMPVAR{ 615 616 int type; /* ROW, COL */ 617 int ind; 618 int fix_type; /*'U', 'L, 'F' 619 for column: improve upper bound, lower bound or fix it 620 for row: all other variables need to be fixed to their 621 'U or 'L' or the row is infea'S'ible 622 however, right now it is same with fix_bounds */ 623 double val; /* if it is a column impl*/ 624 struct IMPVAR *right; 625 struct IMPVAR *left; 626 627 }IMPvar; 628 629 typedef struct IMPLIST{ 630 631 int size; 632 IMPvar * head; 633 IMPvar * tail; 634 }IMPlist; 635 636 /*===========================================================================*/ 637 /* Data structure to keep relevant info of a column */ 638 /*===========================================================================*/ 639 typedef struct COLINFO{ 640 int rank; 641 int coef_type; /* all integer, all binary, fractional 642 - considering the type of coefficients*/ 643 int sign_type; /* same below */ 644 char var_type; /* '*C'ontinuous, 645 *'B'inary, 646 *'general 'I'nteger, 647 *'F'ixed, 648 *'Z'-continous but can be integerized 649 650 -those should only appear during preprocessor stage- 651 *negative bina'R'y, 652 *fixable to its 'U'pper bound, 653 *fixable to its 'L'ower bound, 654 -for the last two, need to use is_int to see if 655 they are integer or not- 656 *'T'emporarily fixed, 657 * binary variable and temprarily fixed to 658 its 'l'ower bound, simiarly, 659 temporarily fixed to its 'u'pper bound 660 */ 661 int sos_num; /* #of sos rows that this var appears in */ 662 int col_size; /* col size */ 663 int nz; /* sum of row_sizes this var appears in */ 664 int fix_row_ind; /* state which row caused to fix this variable during 665 basic preprocessor */ 666 667 IMPlist *ulist; /* for binary variables: keeps the list of variables 668 fixed or bounds improved if this variable is fixed to 669 its upper bound */ 670 IMPlist *llist; /* same here - lower side */ 671 672 }COLinfo; 673 674 /*===========================================================================*/ 675 /* Data structure to keep relevant info of a row */ 676 /*===========================================================================*/ 677 typedef struct ROWINFO{ 678 int type; /* all mixed, binary, pure(not binary), cont_binary... */ 679 int bound_type; /* all_bounded, mixed 680 - considering the bounds of variables */ 681 int coef_type; /* all integer, all binary, fractional 682 - considering the type of coefficients*/ 683 int sign_type; /* all_pos, all_neg, mixed */ 684 685 char is_sos_row; 686 char * sos_rep; /* compact representation of the sos row for bitwise 687 operations */ 688 689 /* for preprocessor */ 690 691 double fixed_obj_offset; /* obtained from fixed vars */ 692 double fixed_lhs_offset; /* obtained from fixed vars */ 693 694 double ub; /* calculated using variable bounds */ 695 double lb; /* same above */ 696 697 double sr_ub; /* calculated using sr relaxations + bounds*/ 698 double sr_lb; /* same above */ 699 700 double orig_ub; /* for debugging purposes */ 701 double orig_lb; 702 703 int free_var_num; 704 705 int ub_inf_var_num; /* number of variables in this row those cause 706 ub to be infinite */ 707 int lb_inf_var_num; /* number of variables in this row those cause 708 lb to be infinite */ 709 int size; 710 int fixed_var_num; /* number of fixed variables on this row*/ 711 int fixable_var_num; /* number of fixable variables on this row*/ 712 int bin_var_num; /*not fixed binary variables */ 713 int cont_var_num; /*not fixed continuous variables */ 714 int frac_coef_num; /* not fixed, frac coeffs on this row */ 715 int row_coef_bin_cnt; 716 int row_sign_pos_cnt; 717 718 char is_redundant; 719 char is_updated; 720 char vars_checked; 721 722 }ROWinfo; 723 724 /*===========================================================================*/ 725 /* Data structure to collect information about the model */ 726 /*===========================================================================*/ 727 728 typedef struct MIPINFO{ 729 int prob_type; /* mixed, pure(not binary), binary... */ 730 int cont_var_num; 731 int binary_var_num; 732 int binary_var_nz; 733 int fixed_var_num; 734 int integerizable_var_num; 735 int max_row_size; 736 int max_col_size; 737 int obj_size; /* number of nonzeros in objective function */ 738 739 char is_opt_val_integral; /*is the optimal 740 solution value required to be integral, if one 741 exists*/ 742 743 double sum_obj_offset; /* from fixed variables*/ 744 745 int binary_sos_row_num; /* sos rows with binary vars count*/ 746 int binary_row_num; /* rows with binary vars*/ 747 int cont_row_num; /* rows with cont vars */ 748 int bin_cont_row_num; /* rows with both cont and bin vars */ 749 int row_bin_den; /* binary nz / number of rows */ 750 int col_bin_den; /* binary nz / number of binary columns */ 751 int row_bin_den_mean; /* 2*row_bin_den*max_row_size/ 752 row_bin_den+max_row_size */ 753 int col_bin_den_mean; /* same here for cols */ 754 755 double bin_var_ratio; 756 double cont_var_ratio; 757 double int_var_ratio; 758 double max_row_ratio; 759 double max_col_ratio; 760 double mat_density; 761 double row_density; 762 double col_density; 763 double sos_bin_row_ratio; 764 double bin_row_ratio; 765 766 int e_row_num; 767 int l_row_num; 768 int g_row_num; 769 int r_row_num; 770 771 ROWinfo *rows; 772 COLinfo *cols; 773 774 int c_alloc_size; 775 int c_alloc_num; 776 int *c_ind; 777 double *c_val; 778 int *c_beg; 779 char *c_sense; 780 double *c_rhs; 781 int c_num; 782 int c_nz; 783 int *c_tmp; 784 int prob_num; 785 786 }MIPinfo; 787 788 /*===========================================================================*/ 789 790 #if 0 791 /* not implemented yet */ 792 /* to keep the differences with the original model */ 793 typedef struct MIPDIFF 794 { 795 int rows_del_num; 796 int vars_fixed_num; 797 int coef_changed_num; 798 int bounds_tightened_num; 799 int bounds_integerized_num; 800 int *rows_deleted_ind; 801 int *vars_fixed_ind; 802 int *bounds_tightened_ind; 803 int *bounds_integerized_ind; 804 int *coef_changed_col_ind; 805 int *coef_changed_row_ind; 806 }MIPdiff; 807 808 #endif 809 810 /*===========================================================================*/ 811 /* This structure stores the user's description of the model */ 812 /*===========================================================================*/ 813 typedef struct MIPDESC{ 814 int n; /* number of columns */ 815 int m; /* number of rows */ 816 int nz; /* number of nonzeros */ 817 char *is_int; /* indicates whether a given variables is integer */ 818 int *matbeg; /* n */ 819 int *matind; /* nz */ 820 double *matval; /* nz */ 821 double *obj; /* n */ 822 double *obj1; /* n */ /* for bicriteria problems */ 823 double *obj2; /* n */ /* for bicriteria problems */ 824 double *rhs; /* m */ 825 double *rngval; /* m */ 826 char *sense; /* m */ 827 double *lb; /* n */ 828 double *ub; /* n */ 829 char **colname; /* column names */ 830 double obj_offset; /* constant to be added to the objective function.*/ 831 char obj_sense; /* objective sense. */ 832 833 int alloc_n; /* allocated dims */ 834 int alloc_m; 835 int alloc_nz; 836 837 int fixed_zero; /* only used if preprocessor is used - fixed vars*/ 838 int fixed_n; /* fixed vars to nonzero vals */ 839 int *fixed_ind; 840 double *fixed_val; 841 842 int subs_n; /* only used if preprocessor is used - substitutions*/ 843 int *subs_ind; 844 double *subs_aval; 845 double *subs_rhs; 846 847 int subs_alloc_size; 848 int *subs_rbeg; 849 int *subs_rind; 850 double *subs_rval; 851 852 int aggr_n; /* only used if preprocessor is used - aggregations*/ 853 int *aggr_ind; 854 int *aggr_to_ind; 855 856 /* Only to be allocated and used by SYMPHONY */ 857 858 int *col_lengths; 859 int *row_matbeg; /* m */ /* a row ordered desc for heuristics */ 860 int *row_matind; /* nz */ 861 double *row_matval; /* nz */ 862 int *row_lengths; 863 /* will keep the orig sense - if prep is used */ 864 char *orig_sense; 865 int *orig_ind; /*mapping of indices of presolved model into orig one 866 */ 867 868 int var_type_modified; /* number of updates on the mip desc */ 869 int change_num; /* number of updates on the mip desc */ 870 int change_type[MAX_CHANGE_NUM]; /* type of the mip desc. changes */ 871 int new_col_num; /* used only when new cols added */ 872 int cru_vars_num; 873 int *cru_vars; 874 char is_modified; 875 876 /* will be evaluated only if preprocessor is used */ 877 /* it is here to be carried later for further use */ 878 /* mip info */ 879 MIPinfo *mip_inf; 880 881 // MIPdiff *mip_diff; 882 double * opt_sol; 883 }MIPdesc; 884 885 /*===========================================================================*\ 886 * The warm start description contains all information needed to warm start 887 * the algorithm. 888 \*===========================================================================*/ 889 890 typedef struct WARM_START_DESC{ 891 bc_node *rootnode; 892 int cut_num; 893 int allocated_cut_num; 894 cut_data **cuts; 895 problem_stat stat; 896 node_times comp_times; 897 int phase; 898 double lb; 899 int has_ub; 900 double ub; 901 lp_sol best_sol; 902 char trim_tree; 903 int trim_tree_level; 904 int trim_tree_index; 905 }warm_start_desc; 906 907 /*===========================================================================*/ 908 /* solution pool */ 909 910 typedef struct SP_SOLUTION_DESC{ 911 double objval; 912 int xlength; 913 int *xind; 914 double *xval; 915 916 /* The bnb node where this solution was discoverd*/ 917 int node_index; 918 919 /* The level of the node in bnb tree where this solution was discovered */ 920 int node_level; 921 }sp_solution; 922 923 /*===========================================================================*/ 924 925 typedef struct SP_DESC{ 926 /* max. no. of solutions in the pool */ 927 int max_solutions; 928 /* no. of solutions in the pool */ 929 int num_solutions; 930 int total_num_sols_found; 931 /* array of those solutions */ 932 sp_solution **solutions; 933 }sp_desc; 934 #endif 935