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