OR-Tools  8.2
lp_data/lp_utils.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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
15
17
18namespace operations_research {
19namespace glop {
20
21template <typename SparseColumnLike>
22Fractional SquaredNormTemplate(const SparseColumnLike& column) {
23 Fractional sum(0.0);
24 for (const SparseColumn::Entry e : column) {
25 sum += Square(e.coefficient());
26 }
27 return sum;
28}
29
31 return SquaredNormTemplate<SparseColumn>(v);
32}
33
35 return SquaredNormTemplate<ColumnView>(v);
36}
37
39 KahanSum sum;
40 for (const SparseColumn::Entry e : v) {
41 sum.Add(Square(e.coefficient()));
42 }
43 return sum.Value();
44}
45
48 return PreciseSquaredNorm(v.values);
49 }
50 KahanSum sum;
51 for (const RowIndex row : v.non_zeros) {
52 sum.Add(Square(v[row]));
53 }
54 return sum.Value();
55}
56
58 Fractional sum(0.0);
59 RowIndex row(0);
60 const size_t num_blocks = column.size().value() / 4;
61 for (size_t i = 0; i < num_blocks; ++i) {
62 // See the comment in ScalarProduct in the header for some notes about the
63 // effect of adding up several squares at a time.
64 sum += Square(column[row++]) + Square(column[row++]) +
65 Square(column[row++]) + Square(column[row++]);
66 }
67 while (row < column.size()) {
68 sum += Square(column[row++]);
69 }
70 return sum;
71}
72
74 KahanSum sum;
75 for (RowIndex row(0); row < column.size(); ++row) {
76 sum.Add(Square(column[row]));
77 }
78 return sum.Value();
79}
80
82 Fractional infinity_norm = 0.0;
83 for (RowIndex row(0); row < v.size(); ++row) {
84 infinity_norm = std::max(infinity_norm, fabs(v[row]));
85 }
86 return infinity_norm;
87}
88
89template <typename SparseColumnLike>
90Fractional InfinityNormTemplate(const SparseColumnLike& column) {
91 Fractional infinity_norm = 0.0;
92 for (const SparseColumn::Entry e : column) {
93 infinity_norm = std::max(infinity_norm, fabs(e.coefficient()));
94 }
95 return infinity_norm;
96}
97
99 return InfinityNormTemplate<SparseColumn>(v);
100}
101
103 return InfinityNormTemplate<ColumnView>(v);
104}
105
106double Density(const DenseRow& row) {
107 if (row.empty()) return 0.0;
108 int sum = 0.0;
109 for (ColIndex col(0); col < row.size(); ++col) {
110 if (row[col] != Fractional(0.0)) ++sum;
111 }
112 return static_cast<double>(sum) / row.size().value();
113}
114
116 if (threshold == Fractional(0.0)) return;
117 for (ColIndex col(0); col < row->size(); ++col) {
118 if (fabs((*row)[col]) < threshold) {
119 (*row)[col] = Fractional(0.0);
120 }
121 }
122}
123
125 if (threshold == Fractional(0.0)) return;
126 for (RowIndex row(0); row < column->size(); ++row) {
127 if (fabs((*column)[row]) < threshold) {
128 (*column)[row] = Fractional(0.0);
129 }
130 }
131}
132
134 const DenseBooleanColumn& rows_to_consider,
135 RowIndex* row_index) {
136 Fractional infinity_norm = 0.0;
137 for (const SparseColumn::Entry e : column) {
138 if (rows_to_consider[e.row()] && fabs(e.coefficient()) > infinity_norm) {
139 infinity_norm = fabs(e.coefficient());
140 *row_index = e.row();
141 }
142 }
143 return infinity_norm;
144}
145
147 for (const SparseColumn::Entry e : column) {
148 if (e.coefficient() != 0.0) {
149 (*b)[e.row()] = false;
150 }
151 }
152}
153
154bool IsDominated(const ColumnView& column, const DenseColumn& radius) {
155 for (const SparseColumn::Entry e : column) {
156 DCHECK_GE(radius[e.row()], 0.0);
157 if (fabs(e.coefficient()) > radius[e.row()]) return false;
158 }
159 return true;
160}
161
162} // namespace glop
163} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
void Add(const FpNumber &value)
Definition: accurate_sum.h:29
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
Fractional PreciseSquaredNorm(const SparseColumn &v)
Fractional InfinityNorm(const DenseColumn &v)
Fractional SquaredNorm(const SparseColumn &v)
Fractional Square(Fractional f)
void RemoveNearZeroEntries(Fractional threshold, DenseRow *row)
double Density(const DenseRow &row)
Fractional InfinityNormTemplate(const SparseColumnLike &column)
void SetSupportToFalse(const ColumnView &column, DenseBooleanColumn *b)
bool IsDominated(const ColumnView &column, const DenseColumn &radius)
Fractional SquaredNormTemplate(const SparseColumnLike &column)
Fractional RestrictedInfinityNorm(const ColumnView &column, const DenseBooleanColumn &rows_to_consider, RowIndex *row_index)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool ShouldUseDenseIteration(double ratio_for_using_dense_representation) const
StrictITIVector< Index, Fractional > values