OR-Tools  8.2
lu_factorization.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
16#include <cstddef>
17
20
21namespace operations_research {
22namespace glop {
23
25 : is_identity_factorization_(true),
26 col_perm_(),
27 inverse_col_perm_(),
28 row_perm_(),
29 inverse_row_perm_() {}
30
32 SCOPED_TIME_STAT(&stats_);
33 lower_.Reset(RowIndex(0), ColIndex(0));
34 upper_.Reset(RowIndex(0), ColIndex(0));
35 transpose_upper_.Reset(RowIndex(0), ColIndex(0));
36 transpose_lower_.Reset(RowIndex(0), ColIndex(0));
37 is_identity_factorization_ = true;
38 col_perm_.clear();
39 row_perm_.clear();
40 inverse_row_perm_.clear();
41 inverse_col_perm_.clear();
42}
43
45 const CompactSparseMatrixView& matrix) {
46 SCOPED_TIME_STAT(&stats_);
47 Clear();
48 if (matrix.num_rows().value() != matrix.num_cols().value()) {
49 GLOP_RETURN_AND_LOG_ERROR(Status::ERROR_LU, "Not a square matrix!!");
50 }
51
53 markowitz_.ComputeLU(matrix, &row_perm_, &col_perm_, &lower_, &upper_));
54 inverse_col_perm_.PopulateFromInverse(col_perm_);
55 inverse_row_perm_.PopulateFromInverse(row_perm_);
56 ComputeTransposeUpper();
57 ComputeTransposeLower();
58
59 is_identity_factorization_ = false;
61 stats_.lu_fill_in.Add(GetFillInPercentage(matrix));
62 stats_.basis_num_entries.Add(matrix.num_entries().value());
63 });
64 DCHECK(CheckFactorization(matrix, Fractional(1e-6)));
65 return Status::OK();
66}
67
69 SCOPED_TIME_STAT(&stats_);
70 if (is_identity_factorization_) return;
71
72 ApplyPermutation(row_perm_, *x, &dense_column_scratchpad_);
73 lower_.LowerSolve(&dense_column_scratchpad_);
74 upper_.UpperSolve(&dense_column_scratchpad_);
75 ApplyPermutation(inverse_col_perm_, dense_column_scratchpad_, x);
76}
77
79 SCOPED_TIME_STAT(&stats_);
80 if (is_identity_factorization_) return;
81
82 // We need to interpret y as a column for the permutation functions.
83 DenseColumn* const x = reinterpret_cast<DenseColumn*>(y);
84 ApplyInversePermutation(inverse_col_perm_, *x, &dense_column_scratchpad_);
85 upper_.TransposeUpperSolve(&dense_column_scratchpad_);
86 lower_.TransposeLowerSolve(&dense_column_scratchpad_);
87 ApplyInversePermutation(row_perm_, dense_column_scratchpad_, x);
88}
89
90namespace {
91// If non_zeros is empty, uses a dense algorithm to compute the squared L2
92// norm of the given column, otherwise do the same with a sparse version. In
93// both cases column is cleared.
94Fractional ComputeSquaredNormAndResetToZero(
95 const std::vector<RowIndex>& non_zeros, DenseColumn* column) {
96 Fractional sum = 0.0;
97 if (non_zeros.empty()) {
98 sum = SquaredNorm(*column);
99 column->clear();
100 } else {
101 for (const RowIndex row : non_zeros) {
102 sum += Square((*column)[row]);
103 (*column)[row] = 0.0;
104 }
105 }
106 return sum;
107}
108} // namespace
109
111 SCOPED_TIME_STAT(&stats_);
112 if (is_identity_factorization_) return SquaredNorm(a);
113
114 non_zero_rows_.clear();
115 dense_zero_scratchpad_.resize(lower_.num_rows(), 0.0);
116 DCHECK(IsAllZero(dense_zero_scratchpad_));
117
118 for (const SparseColumn::Entry e : a) {
119 const RowIndex permuted_row = row_perm_[e.row()];
120 dense_zero_scratchpad_[permuted_row] = e.coefficient();
121 non_zero_rows_.push_back(permuted_row);
122 }
123
124 lower_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
125 if (non_zero_rows_.empty()) {
126 lower_.LowerSolve(&dense_zero_scratchpad_);
127 } else {
128 lower_.HyperSparseSolve(&dense_zero_scratchpad_, &non_zero_rows_);
129 upper_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
130 }
131 if (non_zero_rows_.empty()) {
132 upper_.UpperSolve(&dense_zero_scratchpad_);
133 } else {
134 upper_.HyperSparseSolveWithReversedNonZeros(&dense_zero_scratchpad_,
135 &non_zero_rows_);
136 }
137 return ComputeSquaredNormAndResetToZero(non_zero_rows_,
138 &dense_zero_scratchpad_);
139}
140
142 if (is_identity_factorization_) return 1.0;
143 SCOPED_TIME_STAT(&stats_);
144 const RowIndex permuted_row =
145 col_perm_.empty() ? row : ColToRowIndex(col_perm_[RowToColIndex(row)]);
146
147 non_zero_rows_.clear();
148 dense_zero_scratchpad_.resize(lower_.num_rows(), 0.0);
149 DCHECK(IsAllZero(dense_zero_scratchpad_));
150 dense_zero_scratchpad_[permuted_row] = 1.0;
151 non_zero_rows_.push_back(permuted_row);
152
153 transpose_upper_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
154 if (non_zero_rows_.empty()) {
155 transpose_upper_.LowerSolveStartingAt(RowToColIndex(permuted_row),
156 &dense_zero_scratchpad_);
157 } else {
158 transpose_upper_.HyperSparseSolve(&dense_zero_scratchpad_, &non_zero_rows_);
159 transpose_lower_.ComputeRowsToConsiderInSortedOrder(&non_zero_rows_);
160 }
161 if (non_zero_rows_.empty()) {
162 transpose_lower_.UpperSolve(&dense_zero_scratchpad_);
163 } else {
165 &dense_zero_scratchpad_, &non_zero_rows_);
166 }
167 return ComputeSquaredNormAndResetToZero(non_zero_rows_,
168 &dense_zero_scratchpad_);
169}
170
171namespace {
172// Returns whether 'b' is equal to 'a' permuted by the given row permutation
173// 'perm'.
174bool AreEqualWithPermutation(const DenseColumn& a, const DenseColumn& b,
175 const RowPermutation& perm) {
176 const RowIndex num_rows = perm.size();
177 for (RowIndex row(0); row < num_rows; ++row) {
178 if (a[row] != b[perm[row]]) return false;
179 }
180 return true;
181}
182} // namespace
183
185 ScatteredColumn* x) const {
186 SCOPED_TIME_STAT(&stats_);
187 if (!is_identity_factorization_) {
188 DCHECK(AreEqualWithPermutation(a, x->values, row_perm_));
190 if (x->non_zeros.empty()) {
191 lower_.LowerSolve(&x->values);
192 } else {
193 lower_.HyperSparseSolve(&x->values, &x->non_zeros);
194 }
195 }
196}
197
198template <typename Column>
199void LuFactorization::RightSolveLInternal(const Column& b,
200 ScatteredColumn* x) const {
201 // This code is equivalent to
202 // b.PermutedCopyToDenseVector(row_perm_, num_rows, x);
203 // but it also computes the first column index which does not correspond to an
204 // identity column of lower_ thus exploiting a bit the hyper-sparsity
205 // of b.
206 ColIndex first_column_to_consider(RowToColIndex(x->values.size()));
207 const ColIndex limit = lower_.GetFirstNonIdentityColumn();
208 for (const auto e : b) {
209 const RowIndex permuted_row = row_perm_[e.row()];
210 (*x)[permuted_row] = e.coefficient();
211 x->non_zeros.push_back(permuted_row);
212
213 // The second condition only works because the elements on the diagonal of
214 // lower_ are all equal to 1.0.
215 const ColIndex col = RowToColIndex(permuted_row);
216 if (col < limit || lower_.ColumnIsDiagonalOnly(col)) {
218 continue;
219 }
220 first_column_to_consider = std::min(first_column_to_consider, col);
221 }
222
224 x->non_zeros_are_sorted = true;
225 if (x->non_zeros.empty()) {
226 lower_.LowerSolveStartingAt(first_column_to_consider, &x->values);
227 } else {
228 lower_.HyperSparseSolve(&x->values, &x->non_zeros);
229 }
230}
231
233 ScatteredColumn* x) const {
234 SCOPED_TIME_STAT(&stats_);
236 x->non_zeros.clear();
237 if (is_identity_factorization_) {
238 for (const ColumnView::Entry e : b) {
239 (*x)[e.row()] = e.coefficient();
240 x->non_zeros.push_back(e.row());
241 }
242 return;
243 }
244
245 RightSolveLInternal(b, x);
246}
247
249 if (is_identity_factorization_) return;
250 if (x->non_zeros.empty()) {
251 PermuteWithScratchpad(row_perm_, &dense_zero_scratchpad_, &x->values);
252 lower_.LowerSolve(&x->values);
253 return;
254 }
255
256 PermuteWithKnownNonZeros(row_perm_, &dense_zero_scratchpad_, &x->values,
257 &x->non_zeros);
259 x->non_zeros_are_sorted = true;
260 if (x->non_zeros.empty()) {
261 lower_.LowerSolve(&x->values);
262 } else {
263 lower_.HyperSparseSolve(&x->values, &x->non_zeros);
264 }
265}
266
268 ScatteredColumn* x) const {
269 SCOPED_TIME_STAT(&stats_);
271 x->non_zeros.clear();
272
273 if (is_identity_factorization_) {
274 *x = b;
275 return;
276 }
277
278 if (b.non_zeros.empty()) {
279 *x = b;
280 return RightSolveLWithNonZeros(x);
281 }
282
283 RightSolveLInternal(b, x);
284}
285
287 SCOPED_TIME_STAT(&stats_);
288 CHECK(col_perm_.empty());
289 if (is_identity_factorization_) return;
290
291 DenseColumn* const x = reinterpret_cast<DenseColumn*>(&y->values);
292 RowIndexVector* const nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
293 transpose_upper_.ComputeRowsToConsiderInSortedOrder(nz);
294 y->non_zeros_are_sorted = true;
295 if (nz->empty()) {
296 upper_.TransposeUpperSolve(x);
297 } else {
298 upper_.TransposeHyperSparseSolve(x, nz);
299 }
300}
301
303 SCOPED_TIME_STAT(&stats_);
304 CHECK(col_perm_.empty());
305 if (is_identity_factorization_) return;
306
307 // If non-zeros is non-empty, we use an hypersparse solve. Note that if
308 // non_zeros starts to be too big, we clear it and thus switch back to a
309 // normal sparse solve.
310 upper_.ComputeRowsToConsiderInSortedOrder(&x->non_zeros, 0.1, 0.2);
311 x->non_zeros_are_sorted = true;
312 if (x->non_zeros.empty()) {
313 transpose_upper_.TransposeLowerSolve(&x->values);
314 } else {
316 &x->values, &x->non_zeros);
317 }
318}
319
321 ScatteredRow* y, ScatteredColumn* result_before_permutation) const {
322 SCOPED_TIME_STAT(&stats_);
323 if (is_identity_factorization_) {
324 // It is not advantageous to fill result_before_permutation in this case.
325 return false;
326 }
327 DenseColumn* const x = reinterpret_cast<DenseColumn*>(&y->values);
328 std::vector<RowIndex>* nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
329
330 // Hypersparse?
331 transpose_lower_.ComputeRowsToConsiderInSortedOrder(nz);
332 y->non_zeros_are_sorted = true;
333 if (nz->empty()) {
334 lower_.TransposeLowerSolve(x);
335 } else {
337 }
338
339 if (result_before_permutation == nullptr) {
340 // Note(user): For the behavior of the two functions to be exactly the same,
341 // we need the positions listed in nz to be the "exact" non-zeros of x. This
342 // should be the case because the hyper-sparse functions makes sure of that.
343 // We also DCHECK() this below.
344 if (nz->empty()) {
345 PermuteWithScratchpad(inverse_row_perm_, &dense_zero_scratchpad_, x);
346 } else {
347 PermuteWithKnownNonZeros(inverse_row_perm_, &dense_zero_scratchpad_, x,
348 nz);
349 }
350 if (DEBUG_MODE) {
351 for (const RowIndex row : *nz) {
352 DCHECK_NE((*x)[row], 0.0);
353 }
354 }
355 return false;
356 }
357
358 // This computes the same thing as in the other branch but also keeps the
359 // original x in result_before_permutation. Because of this, it is faster to
360 // use a different algorithm.
361 ClearAndResizeVectorWithNonZeros(x->size(), result_before_permutation);
362 x->swap(result_before_permutation->values);
363 if (nz->empty()) {
364 for (RowIndex row(0); row < inverse_row_perm_.size(); ++row) {
365 const Fractional value = (*result_before_permutation)[row];
366 if (value != 0.0) {
367 const RowIndex permuted_row = inverse_row_perm_[row];
368 (*x)[permuted_row] = value;
369 }
370 }
371 } else {
372 nz->swap(result_before_permutation->non_zeros);
373 nz->reserve(result_before_permutation->non_zeros.size());
374 for (const RowIndex row : result_before_permutation->non_zeros) {
375 const Fractional value = (*result_before_permutation)[row];
376 const RowIndex permuted_row = inverse_row_perm_[row];
377 (*x)[permuted_row] = value;
378 nz->push_back(permuted_row);
379 }
380 y->non_zeros_are_sorted = false;
381 }
382 return true;
383}
384
386 LeftSolveLWithNonZeros(y, nullptr);
387}
388
390 ScatteredRow* y) const {
391 SCOPED_TIME_STAT(&stats_);
393 DCHECK(y->non_zeros.empty());
394 if (is_identity_factorization_) {
395 (*y)[col] = 1.0;
396 y->non_zeros.push_back(col);
397 return col;
398 }
399 const ColIndex permuted_col = col_perm_.empty() ? col : col_perm_[col];
400 (*y)[permuted_col] = 1.0;
401 y->non_zeros.push_back(permuted_col);
402
403 // Using the transposed matrix here is faster (even accounting the time to
404 // construct it). Note the small optimization in case the inversion is
405 // trivial.
406 if (transpose_upper_.ColumnIsDiagonalOnly(permuted_col)) {
407 (*y)[permuted_col] /= transpose_upper_.GetDiagonalCoefficient(permuted_col);
408 } else {
409 RowIndexVector* const nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
410 DenseColumn* const x = reinterpret_cast<DenseColumn*>(&y->values);
411 transpose_upper_.ComputeRowsToConsiderInSortedOrder(nz);
412 y->non_zeros_are_sorted = true;
413 if (y->non_zeros.empty()) {
414 transpose_upper_.LowerSolveStartingAt(permuted_col, x);
415 } else {
416 transpose_upper_.HyperSparseSolve(x, nz);
417 }
418 }
419 return permuted_col;
420}
421
423 if (is_identity_factorization_) {
424 column_of_upper_.Clear();
425 column_of_upper_.SetCoefficient(ColToRowIndex(col), 1.0);
426 return column_of_upper_;
427 }
428 upper_.CopyColumnToSparseColumn(col_perm_.empty() ? col : col_perm_[col],
429 &column_of_upper_);
430 return column_of_upper_;
431}
432
434 const CompactSparseMatrixView& matrix) const {
435 const int initial_num_entries = matrix.num_entries().value();
436 const int lu_num_entries =
437 (lower_.num_entries() + upper_.num_entries()).value();
438 if (is_identity_factorization_ || initial_num_entries == 0) return 1.0;
439 return static_cast<double>(lu_num_entries) /
440 static_cast<double>(initial_num_entries);
441}
442
444 return is_identity_factorization_
445 ? EntryIndex(0)
446 : lower_.num_entries() + upper_.num_entries();
447}
448
450 if (is_identity_factorization_) return 1.0;
451 DCHECK_EQ(upper_.num_rows().value(), upper_.num_cols().value());
452 Fractional product(1.0);
453 for (ColIndex col(0); col < upper_.num_cols(); ++col) {
454 product *= upper_.GetDiagonalCoefficient(col);
455 }
456 return product * row_perm_.ComputeSignature() *
457 inverse_col_perm_.ComputeSignature();
458}
459
461 if (is_identity_factorization_) return 1.0;
462 const RowIndex num_rows = lower_.num_rows();
463 const ColIndex num_cols = lower_.num_cols();
464 Fractional norm = 0.0;
465 for (ColIndex col(0); col < num_cols; ++col) {
466 DenseColumn right_hand_side(num_rows, 0.0);
467 right_hand_side[ColToRowIndex(col)] = 1.0;
468 // Get a column of the matrix inverse.
469 RightSolve(&right_hand_side);
470 Fractional column_norm = 0.0;
471 // Compute sum_i |basis_matrix_ij|.
472 for (RowIndex row(0); row < num_rows; ++row) {
473 column_norm += std::abs(right_hand_side[row]);
474 }
475 // Compute max_j sum_i |basis_matrix_ij|
476 norm = std::max(norm, column_norm);
477 }
478 return norm;
479}
480
482 if (is_identity_factorization_) return 1.0;
483 const RowIndex num_rows = lower_.num_rows();
484 const ColIndex num_cols = lower_.num_cols();
485 DenseColumn row_sum(num_rows, 0.0);
486 for (ColIndex col(0); col < num_cols; ++col) {
487 DenseColumn right_hand_side(num_rows, 0.0);
488 right_hand_side[ColToRowIndex(col)] = 1.0;
489 // Get a column of the matrix inverse.
490 RightSolve(&right_hand_side);
491 // Compute sum_j |basis_matrix_ij|.
492 for (RowIndex row(0); row < num_rows; ++row) {
493 row_sum[row] += std::abs(right_hand_side[row]);
494 }
495 }
496 // Compute max_i sum_j |basis_matrix_ij|
497 Fractional norm = 0.0;
498 for (RowIndex row(0); row < num_rows; ++row) {
499 norm = std::max(norm, row_sum[row]);
500 }
501 return norm;
502}
503
505 const CompactSparseMatrixView& matrix) const {
506 if (is_identity_factorization_) return 1.0;
507 return matrix.ComputeOneNorm() * ComputeInverseOneNorm();
508}
509
511 const CompactSparseMatrixView& matrix) const {
512 if (is_identity_factorization_) return 1.0;
514}
515
519}
520
521namespace {
522// Returns the density of the sparse column 'b' w.r.t. the given permutation.
523double ComputeDensity(const SparseColumn& b, const RowPermutation& row_perm) {
524 double density = 0.0;
525 for (const SparseColumn::Entry e : b) {
526 if (row_perm[e.row()] != kNonPivotal && e.coefficient() != 0.0) {
527 ++density;
528 }
529 }
530 const RowIndex num_rows = row_perm.size();
531 return density / num_rows.value();
532}
533} // anonymous namespace
534
535void LuFactorization::ComputeTransposeUpper() {
536 SCOPED_TIME_STAT(&stats_);
537 transpose_upper_.PopulateFromTranspose(upper_);
538}
539
540void LuFactorization::ComputeTransposeLower() const {
541 SCOPED_TIME_STAT(&stats_);
542 transpose_lower_.PopulateFromTranspose(lower_);
543}
544
545bool LuFactorization::CheckFactorization(const CompactSparseMatrixView& matrix,
546 Fractional tolerance) const {
547 if (is_identity_factorization_) return true;
548 SparseMatrix lu;
550 SparseMatrix paq;
551 paq.PopulateFromPermutedMatrix(matrix, row_perm_, inverse_col_perm_);
552 if (!row_perm_.Check()) {
553 return false;
554 }
555 if (!inverse_col_perm_.Check()) {
556 return false;
557 }
558
559 SparseMatrix should_be_zero;
560 should_be_zero.PopulateFromLinearCombination(Fractional(1.0), paq,
561 Fractional(-1.0), lu);
562
563 for (ColIndex col(0); col < should_be_zero.num_cols(); ++col) {
564 for (const SparseColumn::Entry e : should_be_zero.column(col)) {
565 const Fractional magnitude = std::abs(e.coefficient());
566 if (magnitude > tolerance) {
567 VLOG(2) << magnitude << " != 0, at column " << col;
568 return false;
569 }
570 }
571 }
572 return true;
573}
574
575} // namespace glop
576} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define VLOG(verboselevel)
Definition: base/logging.h:978
void swap(StrongVector &x)
void LeftSolveUWithNonZeros(ScatteredRow *y) const
const SparseColumn & GetColumnOfU(ColIndex col) const
void RightSolveLForColumnView(const ColumnView &b, ScatteredColumn *x) const
void RightSolveLWithPermutedInput(const DenseColumn &a, ScatteredColumn *x) const
double GetFillInPercentage(const CompactSparseMatrixView &matrix) const
Fractional RightSolveSquaredNorm(const ColumnView &a) const
void RightSolveUWithNonZeros(ScatteredColumn *x) const
bool LeftSolveLWithNonZeros(ScatteredRow *y, ScatteredColumn *result_before_permutation) const
ColIndex LeftSolveUForUnitRow(ColIndex col, ScatteredRow *y) const
Fractional DualEdgeSquaredNorm(RowIndex row) const
void RightSolveLForScatteredColumn(const ScatteredColumn &b, ScatteredColumn *x) const
void RightSolveLWithNonZeros(ScatteredColumn *x) const
Fractional ComputeInfinityNormConditionNumber(const CompactSparseMatrixView &matrix) const
void ComputeLowerTimesUpper(SparseMatrix *product) const
ABSL_MUST_USE_RESULT Status ComputeFactorization(const CompactSparseMatrixView &compact_matrix)
Fractional ComputeOneNormConditionNumber(const CompactSparseMatrixView &matrix) const
ABSL_MUST_USE_RESULT Status ComputeLU(const CompactSparseMatrixView &basis_matrix, RowPermutation *row_perm, ColumnPermutation *col_perm, TriangularMatrix *lower, TriangularMatrix *upper)
Definition: markowitz.cc:143
void PopulateFromInverse(const Permutation &inverse)
Definition: sparse_column.h:28
void SetCoefficient(Index index, Fractional value)
static const Status OK()
Definition: status.h:54
void TransposeHyperSparseSolve(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:930
void UpperSolve(DenseColumn *rhs) const
Definition: sparse.cc:770
void HyperSparseSolve(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:869
Fractional GetDiagonalCoefficient(ColIndex col) const
Definition: sparse.h:572
void LowerSolve(DenseColumn *rhs) const
Definition: sparse.cc:737
void TransposeHyperSparseSolveWithReversedNonZeros(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:960
void LowerSolveStartingAt(ColIndex start, DenseColumn *rhs) const
Definition: sparse.cc:741
void PopulateFromTranspose(const TriangularMatrix &input)
Definition: sparse.cc:491
void CopyColumnToSparseColumn(ColIndex col, SparseColumn *output) const
Definition: sparse.cc:720
void ComputeRowsToConsiderInSortedOrder(RowIndexVector *non_zero_rows, Fractional sparsity_ratio, Fractional num_ops_ratio) const
Definition: sparse.cc:1314
void TransposeLowerSolve(DenseColumn *rhs) const
Definition: sparse.cc:831
void TransposeUpperSolve(DenseColumn *rhs) const
Definition: sparse.cc:801
Fractional ComputeInverseInfinityNormUpperBound() const
Definition: sparse.cc:1357
void Reset(RowIndex num_rows, ColIndex col_capacity)
Definition: sparse.cc:524
bool ColumnIsDiagonalOnly(ColIndex col) const
Definition: sparse.h:577
void HyperSparseSolveWithReversedNonZeros(DenseColumn *rhs, RowIndexVector *non_zero_rows) const
Definition: sparse.cc:899
int64 value
const bool DEBUG_MODE
Definition: macros.h:24
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
const RowIndex kNonPivotal(-1)
Fractional SquaredNorm(const SparseColumn &v)
void ApplyInversePermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
bool IsAllZero(const Container &input)
Fractional Square(Fractional f)
void PermuteWithKnownNonZeros(const Permutation< IndexType > &permutation, StrictITIVector< IndexType, Fractional > *zero_scratchpad, StrictITIVector< IndexType, Fractional > *output, std::vector< IndexType > *non_zeros)
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
std::vector< RowIndex > RowIndexVector
Definition: lp_types.h:309
void ApplyPermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
void ClearAndResizeVectorWithNonZeros(IndexType size, ScatteredRowOrCol *v)
void PermuteWithScratchpad(const Permutation< PermutationIndexType > &permutation, StrictITIVector< IndexType, Fractional > *zero_scratchpad, StrictITIVector< IndexType, Fractional > *input_output)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define IF_STATS_ENABLED(instructions)
Definition: stats.h:437
#define SCOPED_TIME_STAT(stats)
Definition: stats.h:438
#define GLOP_RETURN_IF_ERROR(function_call)
Definition: status.h:70
#define GLOP_RETURN_AND_LOG_ERROR(error_code, message)
Definition: status.h:77
StrictITIVector< Index, Fractional > values