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 
18 namespace operations_research {
19 namespace glop {
20 
21 template <typename SparseColumnLike>
22 Fractional 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 
47  if (v.ShouldUseDenseIteration()) {
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 
89 template <typename SparseColumnLike>
90 Fractional 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 
106 double 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 
124 void RemoveNearZeroEntries(Fractional threshold, DenseColumn* column) {
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 
154 bool 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 Square(Fractional f)
Fractional PreciseSquaredNorm(const SparseColumn &v)
Fractional InfinityNorm(const DenseColumn &v)
Fractional SquaredNorm(const SparseColumn &v)
void RemoveNearZeroEntries(Fractional threshold, DenseRow *row)
Fractional InfinityNormTemplate(const SparseColumnLike &column)
double Density(const DenseRow &row)
void SetSupportToFalse(const ColumnView &column, DenseBooleanColumn *b)
Fractional SquaredNormTemplate(const SparseColumnLike &column)
bool IsDominated(const ColumnView &column, const DenseColumn &radius)
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