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/HQPrimal.h 11 * @brief Phase 2 primal simplex solver for HiGHS 12 * @author Julian Hall, Ivet Galabova, Qi Huangfu and Michael Feldmeier 13 */ 14 #ifndef SIMPLEX_HQPRIMAL_H_ 15 #define SIMPLEX_HQPRIMAL_H_ 16 17 #include <utility> 18 19 #include "HConfig.h" 20 #include "lp_data/HighsModelObject.h" 21 #include "simplex/HSimplex.h" 22 #include "simplex/HVector.h" 23 24 using std::pair; 25 26 /** 27 * @brief Phase 2 primal simplex solver for HiGHS 28 * 29 * Not an efficient primal simplex solver: just a way of tidying up 30 * dual infeasibilities when dual optimality (primal feasibility) has 31 * been acheived with the dual simplex method 32 */ 33 34 class HQPrimal { 35 public: HQPrimal(HighsModelObject & model_object)36 HQPrimal(HighsModelObject& model_object) : workHMO(model_object) {} 37 /** 38 * @brief Solve a model instance 39 */ 40 HighsStatus solve(); 41 42 /** 43 * @brief Perform Phase 2 primal simplex iterations 44 */ 45 void solvePhase2(); 46 47 const SimplexAlgorithm algorithm = SimplexAlgorithm::PRIMAL; 48 49 private: 50 void primalRebuild(); 51 void primalChooseColumn(); 52 void primalChooseRow(); 53 void primalUpdate(); 54 55 void phase1ComputeDual(); 56 void phase1ChooseColumn(); 57 void phase1ChooseRow(); 58 void phase1Update(); 59 60 void devexReset(); 61 void devexUpdate(); 62 63 /** 64 * @brief Pass the data for the iteration analysis, report and rebuild report 65 */ 66 void iterationAnalysisData(); 67 68 /** 69 * @brief Perform the iteration analysis 70 */ 71 void iterationAnalysis(); 72 73 /** 74 * @brief Single line report after rebuild 75 */ 76 void reportRebuild(const int rebuild_invert_hint = -1); 77 bool bailout(); 78 bool solve_bailout; //!< Set true if control is to be returned immediately to 79 //!< calling function 80 81 // Model pointer 82 HighsModelObject& workHMO; 83 84 int solver_num_col; 85 int solver_num_row; 86 int solver_num_tot; 87 HighsSimplexAnalysis* analysis; 88 89 bool no_free_columns; 90 91 int isPrimalPhase1; 92 93 int solvePhase; 94 // Pivot related 95 int invertHint; 96 int columnIn; 97 int rowOut; 98 int columnOut; 99 int phase1OutBnd; 100 double thetaDual; 101 double thetaPrimal; 102 double alpha; 103 // double alphaRow; 104 double numericalTrouble; 105 int num_flip_since_rebuild; 106 107 // Primal phase 1 tools 108 vector<pair<double, int> > ph1SorterR; 109 vector<pair<double, int> > ph1SorterT; 110 111 // Devex weight 112 int num_devex_iterations; 113 int num_bad_devex_weight; 114 vector<double> devex_weight; 115 vector<int> devex_index; 116 117 // Solve buffer 118 HVector row_ep; 119 HVector row_ap; 120 HVector col_aq; 121 }; 122 123 #endif /* SIMPLEX_HQPRIMAL_H_ */ 124