1 // Copyright 2010-2021 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13
14 #ifndef OR_TOOLS_LP_DATA_SCATTERED_VECTOR_H_
15 #define OR_TOOLS_LP_DATA_SCATTERED_VECTOR_H_
16
17 #include <cmath>
18 #include <limits>
19
20 #include "ortools/base/basictypes.h"
21 #include "ortools/base/int_type.h"
22 #include "ortools/base/logging.h"
23 #include "ortools/lp_data/lp_types.h"
24 #include "ortools/util/bitset.h"
25
26 namespace operations_research {
27 namespace glop {
28
29 // A class representing an entry of a scattered vector. The i-th nonzero
30 // element of the vector is assumed to be located at indices[i] and its value is
31 // coefficients[indices[i]], i.e., coefficients is a dense array.
32 template <typename IndexType>
33 class ScatteredVectorEntry {
34 public:
35 using Index = IndexType;
36
index()37 Index index() const { return index_[i_.value()]; }
coefficient()38 Fractional coefficient() const {
39 return coefficient_[index_[i_.value()].value()];
40 }
41
42 protected:
ScatteredVectorEntry(const Index * indices,const Fractional * coefficients,EntryIndex i)43 ScatteredVectorEntry(const Index* indices, const Fractional* coefficients,
44 EntryIndex i)
45 : i_(i), index_(indices), coefficient_(coefficients) {}
46
47 EntryIndex i_;
48 const Index* index_;
49 const Fractional* coefficient_;
50 };
51
52 // A simple struct that contains a DenseVector and its non-zero indices.
53 // TODO(user): This should be changed from struct to class.
54 template <typename Index,
55 typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>
56 struct ScatteredVector {
57 StrictITIVector<Index, Fractional> values;
58
59 // This can be left empty in which case we just have the dense representation
60 // above. Otherwise, it should always be a superset of the actual non-zeros.
61 bool non_zeros_are_sorted = false;
62 std::vector<Index> non_zeros;
63
64 // Temporary vector used in some sparse computation on the ScatteredVector.
65 // True indicates a possible non-zero value. Note that its state is not always
66 // consistent.
67 StrictITIVector<Index, bool> is_non_zero;
68
69 // In many cases there is a choice between treating the ScatteredVector as
70 // dense or as sparse. By default, dense algorithms are used when the
71 // proportion of non-zero entries is greater than
72 // kDefaultRatioForUsingDenseIteration.
73 //
74 // TODO(user): The constant should depend on what algorithm is used. Clearing
75 // a dense vector is a lot more efficient than doing more complex stuff. Clean
76 // this up by extracting all the currently used constants in one place with
77 // meaningful names.
78 constexpr static const double kDefaultRatioForUsingDenseIteration = 0.8;
79
80 Fractional operator[](Index index) const { return values[index]; }
81 Fractional& operator[](Index index) { return values[index]; }
82
83 // The iterator syntax for (auto entry : v) where v is a ScatteredVector only
84 // works when non_zeros is populated (i.e., when the vector is treated as
85 // sparse).
beginScatteredVector86 Iterator begin() const {
87 DCHECK(!non_zeros.empty() || IsAllZero(values));
88 return Iterator(this->non_zeros.data(), this->values.data(), EntryIndex(0));
89 }
endScatteredVector90 Iterator end() const {
91 return Iterator(this->non_zeros.data(), this->values.data(),
92 EntryIndex(non_zeros.size()));
93 }
94
95 // Add the given value to the vector at position index. This interface
96 // encapsulates usage of the "is_non_zero" array, which should not be
97 // explicitly referenced outside of this struct.
AddScatteredVector98 void Add(Index index, Fractional value) {
99 values[index] += value;
100 if (!is_non_zero[index] && value != 0.0) {
101 is_non_zero[index] = true;
102 non_zeros.push_back(index);
103 non_zeros_are_sorted = false;
104 }
105 }
106
107 // Sorting the non-zeros is not always needed, but it allows us to have
108 // exactly the same behavior while using a sparse iteration or a dense one. So
109 // we always do it after a Solve().
SortNonZerosIfNeededScatteredVector110 void SortNonZerosIfNeeded() {
111 if (!non_zeros_are_sorted) {
112 std::sort(non_zeros.begin(), non_zeros.end());
113 non_zeros_are_sorted = true;
114 }
115 }
116
117 // Returns true if it is more advantageous to use a dense iteration rather
118 // than using the non-zeros positions.
ShouldUseDenseIterationScatteredVector119 bool ShouldUseDenseIteration(
120 double ratio_for_using_dense_representation) const {
121 if (non_zeros.empty()) return true;
122 return static_cast<double>(non_zeros.size()) >
123 ratio_for_using_dense_representation *
124 static_cast<double>(values.size().value());
125 }
126
ShouldUseDenseIterationScatteredVector127 bool ShouldUseDenseIteration() const {
128 return ShouldUseDenseIteration(kDefaultRatioForUsingDenseIteration);
129 }
130
131 // Efficiently clears the is_non_zero vector.
ClearSparseMaskScatteredVector132 void ClearSparseMask() {
133 if (ShouldUseDenseIteration()) {
134 is_non_zero.assign(values.size(), false);
135 } else {
136 is_non_zero.resize(values.size(), false);
137 for (const Index index : non_zeros) {
138 is_non_zero[index] = false;
139 }
140 DCHECK(IsAllFalse(is_non_zero));
141 }
142 }
143
144 // Update the is_non_zero vector to be consistent with the non_zeros vector.
RepopulateSparseMaskScatteredVector145 void RepopulateSparseMask() {
146 ClearSparseMask();
147 for (const Index index : non_zeros) is_non_zero[index] = true;
148 }
149
150 // If the proportion of non-zero entries is too large, clears the vector of
151 // non-zeros.
ClearNonZerosIfTooDenseScatteredVector152 void ClearNonZerosIfTooDense(double ratio_for_using_dense_representation) {
153 if (ShouldUseDenseIteration(ratio_for_using_dense_representation)) {
154 ClearSparseMask();
155 non_zeros.clear();
156 }
157 }
158
ClearNonZerosIfTooDenseScatteredVector159 void ClearNonZerosIfTooDense() {
160 ClearNonZerosIfTooDense(kDefaultRatioForUsingDenseIteration);
161 }
162
163 // Returns an over-estimate of the number of non-zeros. This is actually
164 // exact for sparse vector, or the full size otherwise.
NumNonZerosEstimateScatteredVector165 size_t NumNonZerosEstimate() const {
166 return non_zeros.empty() ? values.size().value() : non_zeros.size();
167 }
168 };
169
170 // Specializations used in the code.
171 class ScatteredColumnEntry : public ScatteredVectorEntry<RowIndex> {
172 public:
173 // Returns the row of the current entry.
row()174 RowIndex row() const { return index(); }
175
176 protected:
ScatteredColumnEntry(const RowIndex * indices,const Fractional * coefficients,EntryIndex i)177 ScatteredColumnEntry(const RowIndex* indices, const Fractional* coefficients,
178 EntryIndex i)
179 : ScatteredVectorEntry<RowIndex>(indices, coefficients, i) {}
180 };
181
182 class ScatteredRowEntry : public ScatteredVectorEntry<ColIndex> {
183 public:
184 // Returns the column of the current entry.
column()185 ColIndex column() const { return index(); }
186
187 protected:
ScatteredRowEntry(const ColIndex * indices,const Fractional * coefficients,EntryIndex i)188 ScatteredRowEntry(const ColIndex* indices, const Fractional* coefficients,
189 EntryIndex i)
190 : ScatteredVectorEntry<ColIndex>(indices, coefficients, i) {}
191 };
192
193 using ScatteredColumnIterator = VectorIterator<ScatteredColumnEntry>;
194 using ScatteredRowIterator = VectorIterator<ScatteredRowEntry>;
195
196 struct ScatteredColumn
197 : public ScatteredVector<RowIndex, ScatteredColumnIterator> {};
198 struct ScatteredRow : public ScatteredVector<ColIndex, ScatteredRowIterator> {};
199
TransposedView(const ScatteredColumn & c)200 inline const ScatteredRow& TransposedView(const ScatteredColumn& c) {
201 return reinterpret_cast<const ScatteredRow&>(c);
202 }
TransposedView(const ScatteredRow & r)203 inline const ScatteredColumn& TransposedView(const ScatteredRow& r) {
204 return reinterpret_cast<const ScatteredColumn&>(r);
205 }
206
207 } // namespace glop
208 } // namespace operations_research
209
210 #endif // OR_TOOLS_LP_DATA_SCATTERED_VECTOR_H_
211