OR-Tools  8.2
basis_representation.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#include "ortools/glop/status.h"
19
20namespace operations_research {
21namespace glop {
22
23// --------------------------------------------------------
24// EtaMatrix
25// --------------------------------------------------------
26
27const Fractional EtaMatrix::kSparseThreshold = 0.5;
28
29EtaMatrix::EtaMatrix(ColIndex eta_col, const ScatteredColumn& direction)
30 : eta_col_(eta_col),
31 eta_col_coefficient_(direction[ColToRowIndex(eta_col)]),
32 eta_coeff_(),
33 sparse_eta_coeff_() {
34 DCHECK_NE(0.0, eta_col_coefficient_);
35 eta_coeff_ = direction.values;
36 eta_coeff_[ColToRowIndex(eta_col_)] = 0.0;
37
38 // Only fill sparse_eta_coeff_ if it is sparse enough.
39 if (direction.non_zeros.size() <
40 kSparseThreshold * eta_coeff_.size().value()) {
41 for (const RowIndex row : direction.non_zeros) {
42 if (row == ColToRowIndex(eta_col)) continue;
43 sparse_eta_coeff_.SetCoefficient(row, eta_coeff_[row]);
44 }
45 DCHECK(sparse_eta_coeff_.CheckNoDuplicates());
46 }
47}
48
50
53 DCHECK_EQ(RowToColIndex(eta_coeff_.size()), y->size());
54 if (!sparse_eta_coeff_.IsEmpty()) {
55 LeftSolveWithSparseEta(y);
56 } else {
57 LeftSolveWithDenseEta(y);
58 }
59}
60
63 DCHECK_EQ(eta_coeff_.size(), d->size());
64
65 // Nothing to do if 'a' is zero at position eta_row.
66 // This exploits the possible sparsity of the column 'a'.
67 if ((*d)[ColToRowIndex(eta_col_)] == 0.0) return;
68 if (!sparse_eta_coeff_.IsEmpty()) {
69 RightSolveWithSparseEta(d);
70 } else {
71 RightSolveWithDenseEta(d);
72 }
73}
74
77 DCHECK_EQ(RowToColIndex(eta_coeff_.size()), y->size());
78
79 Fractional y_value = (*y)[eta_col_];
80 bool is_eta_col_in_pos = false;
81 const int size = pos->size();
82 for (int i = 0; i < size; ++i) {
83 const ColIndex col = (*pos)[i];
84 const RowIndex row = ColToRowIndex(col);
85 if (col == eta_col_) {
86 is_eta_col_in_pos = true;
87 continue;
88 }
89 y_value -= (*y)[col] * eta_coeff_[row];
90 }
91
92 (*y)[eta_col_] = y_value / eta_col_coefficient_;
93
94 // We add the new non-zero position if it wasn't already there.
95 if (!is_eta_col_in_pos) pos->push_back(eta_col_);
96}
97
98void EtaMatrix::LeftSolveWithDenseEta(DenseRow* y) const {
99 Fractional y_value = (*y)[eta_col_];
100 const RowIndex num_rows(eta_coeff_.size());
101 for (RowIndex row(0); row < num_rows; ++row) {
102 y_value -= (*y)[RowToColIndex(row)] * eta_coeff_[row];
103 }
104 (*y)[eta_col_] = y_value / eta_col_coefficient_;
105}
106
107void EtaMatrix::LeftSolveWithSparseEta(DenseRow* y) const {
108 Fractional y_value = (*y)[eta_col_];
109 for (const SparseColumn::Entry e : sparse_eta_coeff_) {
110 y_value -= (*y)[RowToColIndex(e.row())] * e.coefficient();
111 }
112 (*y)[eta_col_] = y_value / eta_col_coefficient_;
113}
114
115void EtaMatrix::RightSolveWithDenseEta(DenseColumn* d) const {
116 const RowIndex eta_row = ColToRowIndex(eta_col_);
117 const Fractional coeff = (*d)[eta_row] / eta_col_coefficient_;
118 const RowIndex num_rows(eta_coeff_.size());
119 for (RowIndex row(0); row < num_rows; ++row) {
120 (*d)[row] -= eta_coeff_[row] * coeff;
121 }
122 (*d)[eta_row] = coeff;
123}
124
125void EtaMatrix::RightSolveWithSparseEta(DenseColumn* d) const {
126 const RowIndex eta_row = ColToRowIndex(eta_col_);
127 const Fractional coeff = (*d)[eta_row] / eta_col_coefficient_;
128 for (const SparseColumn::Entry e : sparse_eta_coeff_) {
129 (*d)[e.row()] -= e.coefficient() * coeff;
130 }
131 (*d)[eta_row] = coeff;
132}
133
134// --------------------------------------------------------
135// EtaFactorization
136// --------------------------------------------------------
138
140
142
143void EtaFactorization::Update(ColIndex entering_col,
144 RowIndex leaving_variable_row,
145 const ScatteredColumn& direction) {
146 const ColIndex leaving_variable_col = RowToColIndex(leaving_variable_row);
147 EtaMatrix* const eta_factorization =
148 new EtaMatrix(leaving_variable_col, direction);
149 eta_matrix_.push_back(eta_factorization);
150}
151
154 for (int i = eta_matrix_.size() - 1; i >= 0; --i) {
155 eta_matrix_[i]->LeftSolve(y);
156 }
157}
158
161 for (int i = eta_matrix_.size() - 1; i >= 0; --i) {
162 eta_matrix_[i]->SparseLeftSolve(y, pos);
163 }
164}
165
168 const size_t num_eta_matrices = eta_matrix_.size();
169 for (int i = 0; i < num_eta_matrices; ++i) {
170 eta_matrix_[i]->RightSolve(d);
171 }
172}
173
174// --------------------------------------------------------
175// BasisFactorization
176// --------------------------------------------------------
178 const CompactSparseMatrix* compact_matrix, const RowToColMapping* basis)
179 : stats_(),
180 compact_matrix_(*compact_matrix),
181 basis_(*basis),
182 tau_is_computed_(false),
183 max_num_updates_(0),
184 num_updates_(0),
185 eta_factorization_(),
186 lu_factorization_(),
187 deterministic_time_(0.0) {
188 SetParameters(parameters_);
189}
190
192
194 SCOPED_TIME_STAT(&stats_);
195 num_updates_ = 0;
196 tau_computation_can_be_optimized_ = false;
197 eta_factorization_.Clear();
198 lu_factorization_.Clear();
199 rank_one_factorization_.Clear();
200 storage_.Reset(compact_matrix_.num_rows());
201 right_storage_.Reset(compact_matrix_.num_rows());
202 left_pool_mapping_.assign(compact_matrix_.num_cols(), kInvalidCol);
203 right_pool_mapping_.assign(compact_matrix_.num_cols(), kInvalidCol);
204}
205
207 SCOPED_TIME_STAT(&stats_);
208 Clear();
209 if (IsIdentityBasis()) return Status::OK();
210 CompactSparseMatrixView basis_matrix(&compact_matrix_, &basis_);
211 return lu_factorization_.ComputeFactorization(basis_matrix);
212}
213
214bool BasisFactorization::IsRefactorized() const { return num_updates_ == 0; }
215
217 if (IsRefactorized()) return Status::OK();
218 return ForceRefactorization();
219}
220
222 SCOPED_TIME_STAT(&stats_);
223 stats_.refactorization_interval.Add(num_updates_);
224 Clear();
225 CompactSparseMatrixView basis_matrix(&compact_matrix_, &basis_);
226 const Status status = lu_factorization_.ComputeFactorization(basis_matrix);
227
228 const double kLuComplexityFactor = 10;
229 deterministic_time_ +=
230 kLuComplexityFactor * DeterministicTimeForFpOperations(
231 lu_factorization_.NumberOfEntries().value());
232 return status;
233}
234
235// This update formula can be derived by:
236// e = unit vector on the leaving_variable_row
237// new B = L.U + (matrix.column(entering_col) - B.e).e^T
238// new B = L.U + L.L^{-1}.(matrix.column(entering_col) - B.e).e^T.U^{-1}.U
239// new B = L.(Identity +
240// (right_update_vector - U.column(leaving_column)).left_update_vector).U
241// new B = L.RankOneUpdateElementatyMatrix(
242// right_update_vector - U.column(leaving_column), left_update_vector)
243Status BasisFactorization::MiddleProductFormUpdate(
244 ColIndex entering_col, RowIndex leaving_variable_row) {
245 const ColIndex right_index = right_pool_mapping_[entering_col];
246 const ColIndex left_index =
247 left_pool_mapping_[RowToColIndex(leaving_variable_row)];
248 if (right_index == kInvalidCol || left_index == kInvalidCol) {
249 LOG(INFO) << "One update vector is missing!!!";
250 return ForceRefactorization();
251 }
252
253 // TODO(user): create a class for these operations.
254 // Initialize scratchpad_ with the right update vector.
255 DCHECK(IsAllZero(scratchpad_));
256 scratchpad_.resize(right_storage_.num_rows(), 0.0);
257 for (const EntryIndex i : right_storage_.Column(right_index)) {
258 const RowIndex row = right_storage_.EntryRow(i);
259 scratchpad_[row] = right_storage_.EntryCoefficient(i);
260 scratchpad_non_zeros_.push_back(row);
261 }
262 // Subtract the column of U from scratchpad_.
263 const SparseColumn& column_of_u =
264 lu_factorization_.GetColumnOfU(RowToColIndex(leaving_variable_row));
265 for (const SparseColumn::Entry e : column_of_u) {
266 scratchpad_[e.row()] -= e.coefficient();
267 scratchpad_non_zeros_.push_back(e.row());
268 }
269
270 // Creates the new rank one update matrix and update the factorization.
271 const Fractional scalar_product =
272 storage_.ColumnScalarProduct(left_index, Transpose(scratchpad_));
273 const ColIndex u_index = storage_.AddAndClearColumnWithNonZeros(
274 &scratchpad_, &scratchpad_non_zeros_);
275 RankOneUpdateElementaryMatrix elementary_update_matrix(
276 &storage_, u_index, left_index, scalar_product);
277 if (elementary_update_matrix.IsSingular()) {
278 GLOP_RETURN_AND_LOG_ERROR(Status::ERROR_LU, "Degenerate rank-one update.");
279 }
280 rank_one_factorization_.Update(elementary_update_matrix);
281 return Status::OK();
282}
283
284Status BasisFactorization::Update(ColIndex entering_col,
285 RowIndex leaving_variable_row,
286 const ScatteredColumn& direction) {
287 if (num_updates_ < max_num_updates_) {
288 SCOPED_TIME_STAT(&stats_);
289
290 // Note(user): in some rare case (to investigate!) MiddleProductFormUpdate()
291 // will trigger a full refactorization. Because of this, it is important to
292 // increment num_updates_ first as this counter is used by IsRefactorized().
293 ++num_updates_;
294 if (use_middle_product_form_update_) {
296 MiddleProductFormUpdate(entering_col, leaving_variable_row));
297 } else {
298 eta_factorization_.Update(entering_col, leaving_variable_row, direction);
299 }
300 tau_computation_can_be_optimized_ = false;
301 return Status::OK();
302 }
303 return ForceRefactorization();
304}
305
307 SCOPED_TIME_STAT(&stats_);
309 BumpDeterministicTimeForSolve(compact_matrix_.num_rows().value());
310 if (use_middle_product_form_update_) {
311 lu_factorization_.LeftSolveUWithNonZeros(y);
312 rank_one_factorization_.LeftSolveWithNonZeros(y);
313 lu_factorization_.LeftSolveLWithNonZeros(y);
315 } else {
316 y->non_zeros.clear();
317 eta_factorization_.LeftSolve(&y->values);
318 lu_factorization_.LeftSolve(&y->values);
319 }
320}
321
323 SCOPED_TIME_STAT(&stats_);
325 BumpDeterministicTimeForSolve(d->non_zeros.size());
326 if (use_middle_product_form_update_) {
327 lu_factorization_.RightSolveLWithNonZeros(d);
328 rank_one_factorization_.RightSolveWithNonZeros(d);
329 lu_factorization_.RightSolveUWithNonZeros(d);
331 } else {
332 d->non_zeros.clear();
333 lu_factorization_.RightSolve(&d->values);
334 eta_factorization_.RightSolve(&d->values);
335 }
336}
337
339 const ScatteredColumn& a) const {
340 SCOPED_TIME_STAT(&stats_);
341 BumpDeterministicTimeForSolve(compact_matrix_.num_rows().value());
342 if (use_middle_product_form_update_) {
343 if (tau_computation_can_be_optimized_) {
344 // Once used, the intermediate result is overwritten, so
345 // RightSolveForTau() can no longer use the optimized algorithm.
346 tau_computation_can_be_optimized_ = false;
347 lu_factorization_.RightSolveLWithPermutedInput(a.values, &tau_);
348 } else {
349 ClearAndResizeVectorWithNonZeros(compact_matrix_.num_rows(), &tau_);
350 lu_factorization_.RightSolveLForScatteredColumn(a, &tau_);
351 }
352 rank_one_factorization_.RightSolveWithNonZeros(&tau_);
353 lu_factorization_.RightSolveUWithNonZeros(&tau_);
354 } else {
355 tau_.non_zeros.clear();
356 tau_.values = a.values;
357 lu_factorization_.RightSolve(&tau_.values);
358 eta_factorization_.RightSolve(&tau_.values);
359 }
360 tau_is_computed_ = true;
361 return tau_.values;
362}
363
365 ScatteredRow* y) const {
366 SCOPED_TIME_STAT(&stats_);
368 BumpDeterministicTimeForSolve(1);
370 y);
371 if (!use_middle_product_form_update_) {
372 (*y)[j] = 1.0;
373 y->non_zeros.push_back(j);
374 eta_factorization_.SparseLeftSolve(&y->values, &y->non_zeros);
375 lu_factorization_.LeftSolve(&y->values);
376 return;
377 }
378
379 // If the leaving index is the same, we can reuse the column! Note also that
380 // since we do a left solve for a unit row using an upper triangular matrix,
381 // all positions in front of the unit will be zero (modulo the column
382 // permutation).
383 if (left_pool_mapping_[j] == kInvalidCol) {
384 const ColIndex start = lu_factorization_.LeftSolveUForUnitRow(j, y);
385 if (y->non_zeros.empty()) {
386 left_pool_mapping_[j] = storage_.AddDenseColumnPrefix(
387 Transpose(y->values), ColToRowIndex(start));
388 } else {
389 left_pool_mapping_[j] = storage_.AddDenseColumnWithNonZeros(
390 Transpose(y->values),
391 *reinterpret_cast<RowIndexVector*>(&y->non_zeros));
392 }
393 } else {
394 DenseColumn* const x = reinterpret_cast<DenseColumn*>(y);
395 RowIndexVector* const nz = reinterpret_cast<RowIndexVector*>(&y->non_zeros);
396 storage_.ColumnCopyToClearedDenseColumnWithNonZeros(left_pool_mapping_[j],
397 x, nz);
398 }
399
400 rank_one_factorization_.LeftSolveWithNonZeros(y);
401
402 // We only keep the intermediate result needed for the optimized tau_
403 // computation if it was computed after the last time this was called.
404 if (tau_is_computed_) {
405 tau_computation_can_be_optimized_ =
406 lu_factorization_.LeftSolveLWithNonZeros(y, &tau_);
407 } else {
408 tau_computation_can_be_optimized_ = false;
409 lu_factorization_.LeftSolveLWithNonZeros(y);
410 }
411 tau_is_computed_ = false;
413}
414
416 ScatteredRow* y) const {
418 SCOPED_TIME_STAT(&stats_);
420 BumpDeterministicTimeForSolve(1);
422 y);
423 lu_factorization_.LeftSolveUForUnitRow(j, y);
424 lu_factorization_.LeftSolveLWithNonZeros(y);
426}
427
429 ScatteredColumn* d) const {
430 SCOPED_TIME_STAT(&stats_);
432 BumpDeterministicTimeForSolve(
433 compact_matrix_.column(col).num_entries().value());
434 ClearAndResizeVectorWithNonZeros(compact_matrix_.num_rows(), d);
435
436 if (!use_middle_product_form_update_) {
437 compact_matrix_.ColumnCopyToClearedDenseColumn(col, &d->values);
438 lu_factorization_.RightSolve(&d->values);
439 eta_factorization_.RightSolve(&d->values);
440 return;
441 }
442
443 // TODO(user): if right_pool_mapping_[col] != kInvalidCol, we can reuse it and
444 // just apply the last rank one update since it was computed.
445 lu_factorization_.RightSolveLForColumnView(compact_matrix_.column(col), d);
446 rank_one_factorization_.RightSolveWithNonZeros(d);
447 if (col >= right_pool_mapping_.size()) {
448 // This is needed because when we do an incremental solve with only new
449 // columns, we still reuse the current factorization without calling
450 // Refactorize() which would have resized this vector.
451 right_pool_mapping_.resize(col + 1, kInvalidCol);
452 }
453 if (d->non_zeros.empty()) {
454 right_pool_mapping_[col] = right_storage_.AddDenseColumn(d->values);
455 } else {
456 // The sort is needed if we want to have the same behavior for the sparse or
457 // hyper-sparse version.
458 std::sort(d->non_zeros.begin(), d->non_zeros.end());
459 right_pool_mapping_[col] =
460 right_storage_.AddDenseColumnWithNonZeros(d->values, d->non_zeros);
461 }
462 lu_factorization_.RightSolveUWithNonZeros(d);
464}
465
467 const ColumnView& a) const {
468 SCOPED_TIME_STAT(&stats_);
470 BumpDeterministicTimeForSolve(a.num_entries().value());
471 return lu_factorization_.RightSolveSquaredNorm(a);
472}
473
475 SCOPED_TIME_STAT(&stats_);
477 BumpDeterministicTimeForSolve(1);
478 return lu_factorization_.DualEdgeSquaredNorm(row);
479}
480
481bool BasisFactorization::IsIdentityBasis() const {
482 const RowIndex num_rows = compact_matrix_.num_rows();
483 for (RowIndex row(0); row < num_rows; ++row) {
484 const ColIndex col = basis_[row];
485 if (compact_matrix_.column(col).num_entries().value() != 1) return false;
486 const Fractional coeff = compact_matrix_.column(col).GetFirstCoefficient();
487 const RowIndex entry_row = compact_matrix_.column(col).GetFirstRow();
488 if (entry_row != row || coeff != 1.0) return false;
489 }
490 return true;
491}
492
494 if (IsIdentityBasis()) return 1.0;
495 CompactSparseMatrixView basis_matrix(&compact_matrix_, &basis_);
496 return basis_matrix.ComputeOneNorm();
497}
498
500 if (IsIdentityBasis()) return 1.0;
501 CompactSparseMatrixView basis_matrix(&compact_matrix_, &basis_);
502 return basis_matrix.ComputeInfinityNorm();
503}
504
505// TODO(user): try to merge the computation of the norm of inverses
506// with that of MatrixView. Maybe use a wrapper class for InverseMatrix.
507
509 if (IsIdentityBasis()) return 1.0;
510 const RowIndex num_rows = compact_matrix_.num_rows();
511 const ColIndex num_cols = RowToColIndex(num_rows);
512 Fractional norm = 0.0;
513 for (ColIndex col(0); col < num_cols; ++col) {
514 ScatteredColumn right_hand_side;
515 right_hand_side.values.AssignToZero(num_rows);
516 right_hand_side[ColToRowIndex(col)] = 1.0;
517 // Get a column of the matrix inverse.
518 RightSolve(&right_hand_side);
519 Fractional column_norm = 0.0;
520 // Compute sum_i |inverse_ij|.
521 for (RowIndex row(0); row < num_rows; ++row) {
522 column_norm += std::abs(right_hand_side[row]);
523 }
524 // Compute max_j sum_i |inverse_ij|
525 norm = std::max(norm, column_norm);
526 }
527 return norm;
528}
529
531 if (IsIdentityBasis()) return 1.0;
532 const RowIndex num_rows = compact_matrix_.num_rows();
533 const ColIndex num_cols = RowToColIndex(num_rows);
534 DenseColumn row_sum(num_rows, 0.0);
535 for (ColIndex col(0); col < num_cols; ++col) {
536 ScatteredColumn right_hand_side;
537 right_hand_side.values.AssignToZero(num_rows);
538 right_hand_side[ColToRowIndex(col)] = 1.0;
539 // Get a column of the matrix inverse.
540 RightSolve(&right_hand_side);
541 // Compute sum_j |inverse_ij|.
542 for (RowIndex row(0); row < num_rows; ++row) {
543 row_sum[row] += std::abs(right_hand_side[row]);
544 }
545 }
546 // Compute max_i sum_j |inverse_ij|
547 Fractional norm = 0.0;
548 for (RowIndex row(0); row < num_rows; ++row) {
549 norm = std::max(norm, row_sum[row]);
550 }
551 return norm;
552}
553
555 if (IsIdentityBasis()) return 1.0;
557}
558
560 if (IsIdentityBasis()) return 1.0;
562}
563
565 const {
566 if (IsIdentityBasis()) return 1.0;
567 BumpDeterministicTimeForSolve(compact_matrix_.num_rows().value());
568 return ComputeInfinityNorm() *
569 lu_factorization_.ComputeInverseInfinityNormUpperBound();
570}
571
573 return deterministic_time_;
574}
575
576void BasisFactorization::BumpDeterministicTimeForSolve(int num_entries) const {
577 // TODO(user): Spend more time finding a good approximation here.
578 if (compact_matrix_.num_rows().value() == 0) return;
579 const double density =
580 static_cast<double>(num_entries) /
581 static_cast<double>(compact_matrix_.num_rows().value());
582 deterministic_time_ +=
583 (1.0 + density) * DeterministicTimeForFpOperations(
584 lu_factorization_.NumberOfEntries().value()) +
586 rank_one_factorization_.num_entries().value());
587}
588
589} // namespace glop
590} // namespace operations_research
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 LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
BasisFactorization(const CompactSparseMatrix *compact_matrix, const RowToColMapping *basis)
const DenseColumn & RightSolveForTau(const ScatteredColumn &a) const
void LeftSolveForUnitRow(ColIndex j, ScatteredRow *y) const
Fractional RightSolveSquaredNorm(const ColumnView &a) const
void TemporaryLeftSolveForUnitRow(ColIndex j, ScatteredRow *y) const
ABSL_MUST_USE_RESULT Status Update(ColIndex entering_col, RowIndex leaving_variable_row, const ScatteredColumn &direction)
Fractional DualEdgeSquaredNorm(RowIndex row) const
void RightSolveForProblemColumn(ColIndex col, ScatteredColumn *d) const
void SetParameters(const GlopParameters &parameters)
ColIndex AddDenseColumn(const DenseColumn &dense_column)
Definition: sparse.cc:536
ColIndex AddDenseColumnWithNonZeros(const DenseColumn &dense_column, const std::vector< RowIndex > &non_zeros)
Definition: sparse.cc:554
ColIndex AddAndClearColumnWithNonZeros(DenseColumn *column, std::vector< RowIndex > *non_zeros)
Definition: sparse.cc:569
void ColumnCopyToClearedDenseColumnWithNonZeros(ColIndex col, DenseColumn *dense_column, RowIndexVector *non_zeros) const
Definition: sparse.h:436
ColIndex AddDenseColumnPrefix(const DenseColumn &dense_column, RowIndex start)
Definition: sparse.cc:540
Fractional EntryCoefficient(EntryIndex i) const
Definition: sparse.h:361
void ColumnCopyToClearedDenseColumn(ColIndex col, DenseColumn *dense_column) const
Definition: sparse.h:426
Fractional ColumnScalarProduct(ColIndex col, const DenseRow &vector) const
Definition: sparse.h:382
::util::IntegerRange< EntryIndex > Column(ColIndex col) const
Definition: sparse.h:358
RowIndex EntryRow(EntryIndex i) const
Definition: sparse.h:362
ColumnView column(ColIndex col) const
Definition: sparse.h:364
void SparseLeftSolve(DenseRow *y, ColIndexVector *pos) const
void Update(ColIndex entering_col, RowIndex leaving_variable_row, const ScatteredColumn &direction)
EtaMatrix(ColIndex eta_col, const ScatteredColumn &direction)
void SparseLeftSolve(DenseRow *y, ColIndexVector *pos) const
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
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
ABSL_MUST_USE_RESULT Status ComputeFactorization(const CompactSparseMatrixView &compact_matrix)
void Update(const RankOneUpdateElementaryMatrix &update_matrix)
void SetCoefficient(Index index, Fractional value)
static const Status OK()
Definition: status.h:54
void assign(IntType size, const T &v)
Definition: lp_types.h:274
const int INFO
Definition: log_severity.h:31
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
void STLDeleteElements(T *container)
Definition: stl_util.h:372
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
std::vector< ColIndex > ColIndexVector
Definition: lp_types.h:308
static double DeterministicTimeForFpOperations(int64 n)
Definition: lp_types.h:379
bool IsAllZero(const Container &input)
const ColIndex kInvalidCol(-1)
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
const DenseRow & Transpose(const DenseColumn &col)
std::vector< RowIndex > RowIndexVector
Definition: lp_types.h:309
void ClearAndResizeVectorWithNonZeros(IndexType size, ScatteredRowOrCol *v)
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
EntryIndex num_entries
#define RETURN_IF_NULL(x)
Definition: return_macros.h:20
#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