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