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