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