1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the HiGHS linear optimization suite */ 4 /* */ 5 /* Written and engineered 2008-2021 at the University of Edinburgh */ 6 /* */ 7 /* Available as open-source under the MIT License */ 8 /* */ 9 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 10 /**@file simplex/HCrash.h 11 * @brief Bixby and Maros-style crash for the HiGHS simplex solver 12 * @author Julian Hall, Ivet Galabova, Qi Huangfu and Michael Feldmeier 13 */ 14 #ifndef SIMPLEX_HCRASH_H_ 15 #define SIMPLEX_HCRASH_H_ 16 17 #include <string> 18 #include <vector> 19 20 #include "lp_data/HighsModelObject.h" 21 22 class HMatrix; 23 24 // LTSSF scalar parameters 25 const int crsh_vr_st_no_act = 0; 26 const int crsh_vr_st_act = 1; 27 28 // Crash variable types 29 // Basis-preserving crash: 30 const int crsh_vr_ty_non_bc = 0; 31 const int crsh_vr_ty_bc = 1; 32 // Standard crash: 33 const int crsh_vr_ty_fx = 0; 34 const int crsh_vr_ty_2_sd = 1; 35 const int crsh_vr_ty_1_sd = 2; 36 const int crsh_vr_ty_fr = 3; 37 38 // Null header for linked lists 39 const int no_lk = -1; 40 41 // Null value for chosen row/column index 42 const int no_ix = no_lk; 43 44 // LTSSF scalar control parameters 45 const double tl_crsh_abs_pv_v = 1e-4; 46 const double tl_crsh_rlv_pv_v = 1e-2; 47 // Switches for LTSSF checking and reporting 48 const int ltssf_ck_fq = 0; 49 #ifdef HiGHSDEV 50 const bool reportCrashData = false; 51 const bool reportBixbyPass = false; 52 #endif 53 54 /** 55 * @brief Bixby and Maros-style crash for the HiGHS simplex solver 56 */ 57 class HCrash { 58 public: HCrash(HighsModelObject & model_object)59 HCrash(HighsModelObject& model_object) : workHMO(model_object) {} 60 /** 61 * @brief Determine a particular crash basis for a given model instance 62 */ 63 void crash(const int pass_crash_strategy); 64 65 private: 66 // Internal methods 67 void bixby(); 68 bool bixby_iz_da(); 69 void bixby_rp_mrt(); 70 71 void ltssf(); 72 void ltssf_iz_mode(); 73 void ltssf_iz_da(); 74 void ltssf_iterate(); 75 void ltssf_u_da(); 76 void ltssf_u_da_af_bs_cg(); 77 void ltssf_u_da_af_no_bs_cg(); 78 #ifdef HiGHSDEV 79 void ltssf_ck_da(); 80 #endif 81 void ltssf_cz_r(); 82 void ltssf_cz_c(); 83 #ifdef HiGHSDEV 84 void tsSing(); 85 void ltssf_rp_r_k(); 86 void ltssf_rp_r_pri(); 87 void ltssf_rp_pri_k_da(); 88 #endif 89 90 void crsh_iz_vr_ty(); 91 92 #ifdef HiGHSDEV 93 void crsh_an_c_co(); 94 void crsh_rp_r_c_st(const int mode); 95 void crsh_an_r_c_st_af(); 96 std::string crsh_nm_o_crsh_vr_ty(const int vr_ty); 97 #endif 98 99 // Model to be crashed 100 HighsModelObject& workHMO; 101 102 // Crash strategy to be used 103 int crash_strategy; 104 105 // Model dimensions 106 int numCol; 107 int numRow; 108 int numTot; 109 110 // LTSSF arrays 111 std::vector<int> crsh_r_ty_pri_v; 112 std::vector<int> crsh_c_ty_pri_v; 113 std::vector<int> crsh_r_ty; 114 std::vector<int> crsh_c_ty; 115 std::vector<int> crsh_r_k; 116 std::vector<int> crsh_c_k; 117 118 std::vector<int> crsh_r_pri_k_hdr; 119 std::vector<int> crsh_r_pri_k_lkf; 120 std::vector<int> crsh_r_pri_k_lkb; 121 std::vector<int> crsh_r_pri_mn_r_k; 122 123 std::vector<int> crsh_r_pri_hdr; 124 std::vector<int> crsh_r_pri_lkb; 125 std::vector<int> crsh_r_pri_lkf; 126 127 std::vector<int> crsh_r_k_hdr; 128 std::vector<int> crsh_r_k_lkb; 129 std::vector<int> crsh_r_k_lkf; 130 131 #ifdef HiGHSDEV 132 std::vector<int> crsh_vr_ty_og_n_r; 133 std::vector<int> crsh_vr_ty_rm_n_r; 134 std::vector<int> crsh_vr_ty_og_n_c; 135 std::vector<int> crsh_vr_ty_add_n_c; 136 137 std::vector<int> crsh_bs_vr_ty_n_r; 138 std::vector<int> crsh_bs_vr_ty_n_c; 139 std::vector<int> crsh_nonbc_vr_ty_n_r; 140 std::vector<int> crsh_nonbc_vr_ty_n_c; 141 #endif 142 143 std::vector<double> crsh_mtx_c_mx_abs_v; 144 std::vector<double> CrshARvalue; 145 std::vector<int> CrshARindex; 146 std::vector<int> CrshARstart; 147 std::vector<int> crsh_act_r; 148 std::vector<int> crsh_act_c; 149 150 std::vector<double> bixby_mrt_v; 151 std::vector<double> heap_v; 152 std::vector<double> bixby_pseudo_pv_v; 153 std::vector<int> bixby_mrt_ix; 154 std::vector<int> heap_ix; 155 std::vector<int> bixby_pv_in_r; 156 std::vector<int> bixby_vr_in_r; 157 std::vector<int> bixby_r_k; 158 // std::vector<int> bixby_ze_r_k; 159 160 // LTSSF scalar identifiers 161 // int crsh_mode; 162 int crsh_f_vr_ty; 163 int crsh_l_vr_ty; 164 int crsh_num_vr_ty; 165 166 int crsh_mn_pri_v; // = 0; 167 int crsh_mx_pri_v; // = 3; 168 int crsh_no_act_pri_v; // = crsh_mn_pri_v; 169 170 int crsh_fn_cf_pri_v; 171 int crsh_fn_cf_k; 172 bool mn_co_tie_bk; 173 bool alw_al_bs_cg; 174 bool no_ck_pv; 175 double bixby_mu_a; 176 double bixby_mu_b; 177 178 // LTSSF scalar identifiers 179 int n_crsh_ps; 180 int n_crsh_bs_cg; 181 int cz_r_n; 182 int cz_r_pri_v; 183 int cz_c_n; 184 int n_eqv_c; 185 double pv_v; 186 double mn_abs_pv_v; 187 double mn_rlv_pv_v; 188 int mx_r_pri_v; 189 int n_abs_pv_no_ok; 190 int n_rlv_pv_no_ok; 191 int mx_r_pri; 192 int mx_c_pri; 193 int bixby_n_cdd_r; 194 bool bixby_no_nz_c_co; 195 }; 196 197 #endif /* SIMPLEX_HCRASH_H_ */ 198