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_DOMAIN_H_ 11 #define HIGHS_DOMAIN_H_ 12 13 #include <cstdint> 14 #include <memory> 15 #include <unordered_map> 16 #include <vector> 17 18 #include "mip/HighsDomainChange.h" 19 #include "mip/HighsMipSolver.h" 20 #include "util/HighsCDouble.h" 21 22 class HighsCutPool; 23 24 class HighsDomain { 25 std::vector<uint8_t> changedcolsflags_; 26 std::vector<int> changedcols_; 27 28 std::vector<int> propRowNumChangedBounds_; 29 30 std::vector<HighsDomainChange> domchgstack_; 31 std::vector<int> domchgreason_; 32 std::vector<double> prevboundval_; 33 34 std::vector<HighsCDouble> activitymin_; 35 std::vector<HighsCDouble> activitymax_; 36 std::vector<int> activitymininf_; 37 std::vector<int> activitymaxinf_; 38 std::vector<uint8_t> propagateflags_; 39 std::vector<int> propagateinds_; 40 41 std::vector<HighsCDouble> activitycuts_; 42 std::vector<int> activitycutsinf_; 43 std::vector<unsigned> activitycutversion_; 44 std::vector<uint8_t> propagatecutflags_; 45 std::vector<int> propagatecutinds_; 46 47 HighsMipSolver* mipsolver; 48 HighsCutPool* cutpool; 49 HighsDomain* parentdomain; 50 51 int infeasible_ = 0; 52 53 void computeMinActivity(int start, int end, const int* ARindex, 54 const double* ARvalue, int& ninfmin, 55 HighsCDouble& activitymin); 56 57 void computeMaxActivity(int start, int end, const int* ARindex, 58 const double* ARvalue, int& ninfmax, 59 HighsCDouble& activitymax); 60 61 int propagateRowUpper(const int* Rindex, const double* Rvalue, int Rlen, 62 double Rupper, const HighsCDouble& minactivity, 63 int ninfmin, HighsDomainChange* boundchgs); 64 65 int propagateRowLower(const int* Rindex, const double* Rvalue, int Rlen, 66 double Rlower, const HighsCDouble& maxactivity, 67 int ninfmax, HighsDomainChange* boundchgs); 68 69 void updateActivityLbChange(int col, double oldbound, double newbound); 70 71 void updateActivityUbChange(int col, double oldbound, double newbound); 72 73 double doChangeBound(const HighsDomainChange& boundchg); 74 75 public: 76 std::vector<double> colLower_; 77 std::vector<double> colUpper_; 78 HighsDomain(HighsMipSolver& mipsolver, HighsCutPool& cutpool); 79 HighsDomain(const HighsDomain & other)80 HighsDomain(const HighsDomain& other) 81 : changedcolsflags_(other.changedcolsflags_), 82 changedcols_(other.changedcols_), 83 domchgstack_(other.domchgstack_), 84 domchgreason_(other.domchgreason_), 85 prevboundval_(other.prevboundval_), 86 activitymin_(other.activitymin_), 87 activitymax_(other.activitymax_), 88 activitymininf_(other.activitymininf_), 89 activitymaxinf_(other.activitymaxinf_), 90 propagateflags_(other.propagateflags_), 91 propagateinds_(other.propagateinds_), 92 activitycuts_(other.activitycuts_), 93 activitycutsinf_(other.activitycutsinf_), 94 activitycutversion_(other.activitycutversion_), 95 propagatecutflags_(other.propagatecutflags_), 96 propagatecutinds_(other.propagatecutinds_), 97 mipsolver(other.mipsolver), 98 cutpool(other.cutpool), 99 parentdomain(other.parentdomain), 100 infeasible_(other.infeasible_), 101 colLower_(other.colLower_), 102 colUpper_(other.colUpper_) {} 103 104 HighsDomain& operator=(const HighsDomain&) = default; 105 createChildDomain()106 HighsDomain createChildDomain() { 107 HighsDomain childdomain(*this); 108 childdomain.parentdomain = this; 109 return childdomain; 110 } 111 getChangedCols()112 const std::vector<int>& getChangedCols() const { return changedcols_; } 113 clearChangedCols()114 void clearChangedCols() { 115 for (int i : changedcols_) changedcolsflags_[i] = 0; 116 changedcols_.clear(); 117 } 118 clearChangedCols(int start)119 void clearChangedCols(int start) { 120 int end = changedcols_.size(); 121 for (int i = start; i != end; ++i) changedcolsflags_[changedcols_[i]] = 0; 122 123 changedcols_.resize(start); 124 } 125 getPropagateRows()126 const std::vector<int>& getPropagateRows() const { return propagateinds_; } 127 clearPropagateRows(int start)128 void clearPropagateRows(int start) { 129 int end = propagateinds_.size(); 130 for (int i = start; i != end; ++i) propagateflags_[propagateinds_[i]] = 0; 131 132 propagateinds_.resize(start); 133 } 134 getPropagateCuts()135 const std::vector<int>& getPropagateCuts() const { return propagatecutinds_; } 136 clearPropagateCuts(int start)137 void clearPropagateCuts(int start) { 138 int end = propagatecutinds_.size(); 139 for (int i = start; i != end; ++i) 140 propagatecutflags_[propagatecutinds_[i]] = 0; 141 142 propagatecutinds_.resize(start); 143 } 144 setParentDomain(HighsDomain * parentdomain)145 void setParentDomain(HighsDomain* parentdomain) { 146 this->parentdomain = parentdomain; 147 } 148 149 void cutAdded(int cut); 150 151 void markPropagateCut(int cut); 152 153 void markPropagate(int row); 154 155 void computeRowActivities(); 156 infeasible()157 bool infeasible() const { return infeasible_ != 0; } 158 159 void changeBound(HighsDomainChange boundchg, int reason = -1); 160 161 void changeBound(HighsBoundType boundtype, int col, double boundval, 162 int reason = -1) { 163 changeBound({boundtype, col, boundval}, reason); 164 } 165 fixCol(int col,double val)166 void fixCol(int col, double val) { 167 assert(infeasible_ == 0); 168 if (colLower_[col] < val) 169 changeBound({HighsBoundType::Lower, col, val}, -2); 170 171 if (infeasible_ == 0 && colUpper_[col] > val) 172 changeBound({HighsBoundType::Upper, col, val}, -2); 173 } 174 175 HighsDomainChange backtrack(); 176 getDomainChangeStack()177 const std::vector<HighsDomainChange>& getDomainChangeStack() const { 178 return domchgstack_; 179 } 180 getReducedDomainChangeStack()181 std::vector<HighsDomainChange> getReducedDomainChangeStack() const { 182 std::vector<HighsDomainChange> reducedstack; 183 reducedstack.reserve(domchgstack_.size()); 184 for (const HighsDomainChange& domchg : domchgstack_) { 185 // keep only the tightest bound change for each variable 186 if ((domchg.boundtype == HighsBoundType::Lower && 187 colLower_[domchg.column] != domchg.boundval) || 188 (domchg.boundtype == HighsBoundType::Upper && 189 colUpper_[domchg.column] != domchg.boundval)) 190 continue; 191 192 reducedstack.push_back(domchg); 193 } 194 reducedstack.shrink_to_fit(); 195 return reducedstack; 196 } 197 198 void setDomainChangeStack(const std::vector<HighsDomainChange>& domchgstack); 199 200 void propagate(); 201 202 void tightenCoefficients(int* inds, double* vals, int len, double& rhs) const; 203 isBinary(int col)204 bool isBinary(int col) const { 205 return mipsolver->variableType(col) != HighsVarType::CONTINUOUS && 206 colLower_[col] == 0.0 && colUpper_[col] == 1.0; 207 } 208 isFixed(int col)209 bool isFixed(int col) const { return colLower_[col] == colUpper_[col]; } 210 211 bool isFixing(const HighsDomainChange& domchg) const; 212 }; 213 214 #endif