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 #ifndef HIGHS_CUTPOOL_H_
11 #define HIGHS_CUTPOOL_H_
12 
13 #include <memory>
14 #include <unordered_map>
15 #include <vector>
16 
17 #include "lp_data/HConst.h"
18 #include "mip/HighsDomain.h"
19 #include "mip/HighsDynamicRowMatrix.h"
20 
21 class HighsLpRelaxation;
22 
23 struct HighsCutSet {
24   std::vector<int> cutindices;
25   std::vector<int> ARstart_;
26   std::vector<int> ARindex_;
27   std::vector<double> ARvalue_;
28   std::vector<double> lower_;
29   std::vector<double> upper_;
30 
numCutsHighsCutSet31   int numCuts() const { return cutindices.size(); }
32 
resizeHighsCutSet33   void resize(int nnz) {
34     int ncuts = numCuts();
35     lower_.resize(ncuts, -HIGHS_CONST_INF);
36     upper_.resize(ncuts);
37     ARstart_.resize(ncuts + 1);
38     ARindex_.resize(nnz);
39     ARvalue_.resize(nnz);
40   }
41 
clearHighsCutSet42   void clear() {
43     cutindices.clear();
44     upper_.clear();
45     ARstart_.clear();
46     ARindex_.clear();
47     ARvalue_.clear();
48   }
49 
emptyHighsCutSet50   bool empty() const { return cutindices.empty(); }
51 };
52 
53 class HighsCutPool {
54  private:
55   HighsDynamicRowMatrix matrix_;
56   std::vector<double> rhs_;
57   std::vector<unsigned> modification_;
58   std::vector<int> ages_;
59   std::vector<double> rownormalization_;
60   std::vector<double> maxabscoef_;
61   std::vector<uint8_t> rowintegral;
62   std::unordered_multimap<size_t, int> supportmap;
63 
64   int agelim_;
65   int nrounds_;
66 
67   int replaceSupportDuplicate(size_t hash, int* Rindex, double* Rvalue,
68                               int Rlen, double rhs);
69 
70  public:
HighsCutPool(int ncols,int agelim)71   HighsCutPool(int ncols, int agelim)
72       : matrix_(ncols), agelim_(agelim), nrounds_(0) {}
getMatrix()73   const HighsDynamicRowMatrix& getMatrix() const { return matrix_; }
74 
getRhs()75   const std::vector<double>& getRhs() const { return rhs_; }
76 
resetAge(int cut)77   void resetAge(int cut) {
78     if (ages_[cut] < 0)
79       ages_[cut] = -1;
80     else
81       ages_[cut] = 0;
82   }
83 
84   double getParallelism(int row1, int row2) const;
85 
86   void ageLPRows(HighsLpRelaxation& lprelaxation);
87 
88   void ageNonLPRows();
89 
setAgeLimit(int agelim)90   void setAgeLimit(int agelim) { agelim_ = agelim; }
91 
92   void removeObsoleteRows(HighsLpRelaxation& lprelaxation);
93 
94   void removeAllRows(HighsLpRelaxation& lprelaxation);
95 
96   void separate(const std::vector<double>& sol, HighsDomain& domprop,
97                 HighsCutSet& cutset, double feastol);
98 
cutIsIntegral(int cut)99   bool cutIsIntegral(int cut) const { return rowintegral[cut]; }
100 
getNumCuts()101   int getNumCuts() const {
102     return matrix_.getNumRows() - matrix_.getNumDelRows();
103   }
104 
getMaxAbsCutCoef(int cut)105   double getMaxAbsCutCoef(int cut) const { return maxabscoef_[cut]; }
106 
107   int addCut(int* Rindex, double* Rvalue, int Rlen, double rhs,
108              bool integral = false);
109 
getRowLength(int row)110   int getRowLength(int row) const {
111     return matrix_.getRowEnd(row) - matrix_.getRowStart(row);
112   }
113 
getModificationCount(int cut)114   unsigned getModificationCount(int cut) { return modification_[cut]; }
115 
getCut(int cut,int & cutlen,const int * & cutinds,const double * & cutvals)116   void getCut(int cut, int& cutlen, const int*& cutinds,
117               const double*& cutvals) const {
118     int start = matrix_.getRowStart(cut);
119     cutlen = matrix_.getRowEnd(cut) - start;
120     cutinds = matrix_.getARindex() + start;
121     cutvals = matrix_.getARvalue() + start;
122   }
123 };
124 
125 #endif