OR-Tools  8.1
markowitz.h
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 
14 // LU decomposition algorithm of a sparse matrix B with Markowitz pivot
15 // selection strategy. The algorithm constructs a lower matrix L, upper matrix
16 // U, row permutation P and a column permutation Q such that L.U = P.B.Q^{-1}.
17 //
18 // The current algorithm is a mix of ideas that can be found in the literature
19 // and of some optimizations tailored for its use in a revised simplex algorithm
20 // (like a fast processing of the singleton columns present in B). It constructs
21 // L and U column by column from left to right.
22 //
23 // A key concept is the one of the residual matrix which is the bottom right
24 // square submatrix that still needs to be factorized during the classical
25 // Gaussian elimination. The algorithm maintains the non-zero pattern of its
26 // rows and its row/column degrees.
27 //
28 // At each step, a number of columns equal to 'markowitz_zlatev_parameter' are
29 // chosen as candidates from the residual matrix. They are the ones with minimal
30 // residual column degree. They can be found easily because the columns of the
31 // residual matrix are kept in a priority queue.
32 //
33 // We compute the numerical value of these residual columns like in a
34 // left-looking algorithm by solving a sparse lower-triangular system with the
35 // current L constructed so far. Note that this step is highly optimized for
36 // sparsity and we reuse the computations done in the previous steps (if the
37 // candidate column was already considered before). As a by-product, we also
38 // get the corresponding column of U.
39 //
40 // Among the entries of these columns, a pivot is chosen such that the product:
41 // (num_column_entries - 1) * (num_row_entries - 1)
42 // is minimized. Only the pivots with a magnitude greater than
43 // 'lu_factorization_pivot_threshold' times the maximum magnitude of the
44 // corresponding residual column are considered for stability reasons.
45 //
46 // Once the pivot is chosen, the residual column divided by the pivot becomes a
47 // column of L, and the non-zero pattern of the new residual submatrix is
48 // updated by subtracting the outer product of this pivot column times the pivot
49 // row. The product minimized above is thus an upper bound of the number of
50 // fill-in created during a step.
51 //
52 // References:
53 //
54 // J. R. Gilbert and T. Peierls, "Sparse partial pivoting in time proportional
55 // to arithmetic operations," SIAM J. Sci. Statist. Comput., 9 (1988): 862-874.
56 //
57 // I.S. Duff, A.M. Erisman and J.K. Reid, "Direct Methods for Sparse Matrices",
58 // Clarendon, Oxford, UK, 1987, ISBN 0-19-853421-3,
59 // http://www.amazon.com/dp/0198534213
60 //
61 // T.A. Davis, "Direct methods for Sparse Linear Systems", SIAM, Philadelphia,
62 // 2006, ISBN-13: 978-0-898716-13, http://www.amazon.com/dp/0898716136
63 //
64 // TODO(user): Determine whether any of these would bring any benefit:
65 // - S.C. Eisenstat and J.W.H. Liu, "The theory of elimination trees for
66 // sparse unsymmetric matrices," SIAM J. Matrix Anal. Appl., 26:686-705,
67 // January 2005
68 // - S.C. Eisenstat and J.W.H. Liu. "Algorithmic aspects of elimination trees
69 // for sparse unsymmetric matrices," SIAM J. Matrix Anal. Appl.,
70 // 29:1363-1381, January 2008.
71 // - http://perso.ens-lyon.fr/~bucar/papers/kauc.pdf
72 
73 #ifndef OR_TOOLS_GLOP_MARKOWITZ_H_
74 #define OR_TOOLS_GLOP_MARKOWITZ_H_
75 
76 #include <queue>
77 
78 #include "absl/container/inlined_vector.h"
79 #include "ortools/base/logging.h"
81 #include "ortools/glop/status.h"
84 #include "ortools/lp_data/sparse.h"
86 #include "ortools/util/stats.h"
87 
88 namespace operations_research {
89 namespace glop {
90 
91 // Holds the non-zero positions (by row) and column/row degree of the residual
92 // matrix during the Gaussian elimination.
93 //
94 // During each step of Gaussian elimination, a row and a column will be
95 // "removed" from the residual matrix. Note however that the row and column
96 // indices of the non-removed part do not change, so the residual matrix at a
97 // given step will only correspond to a subset of the initial indices.
99  public:
101 
102  // Releases the memory used by this class.
103  void Clear();
104 
105  // Resets the pattern to the one of an empty square matrix of the given size.
106  void Reset(RowIndex num_rows, ColIndex num_cols);
107 
108  // Resets the pattern to the one of the given matrix but only for the
109  // rows/columns whose given permutation is kInvalidRow or kInvalidCol.
110  // This also fills the singleton columns/rows with the corresponding entries.
111  void InitializeFromMatrixSubset(const CompactSparseMatrixView& basis_matrix,
112  const RowPermutation& row_perm,
113  const ColumnPermutation& col_perm,
114  std::vector<ColIndex>* singleton_columns,
115  std::vector<RowIndex>* singleton_rows);
116 
117  // Adds a non-zero entry to the matrix. There should be no duplicates.
118  void AddEntry(RowIndex row, ColIndex col);
119 
120  // Marks the given pivot row and column as deleted.
121  // This is called at each step of the Gaussian elimination on the pivot.
122  void DeleteRowAndColumn(RowIndex pivot_row, ColIndex pivot_col);
123 
124  // Decreases the degree of a row/column. This is the basic operation used to
125  // keep the correct degree after a call to DeleteRowAndColumn(). This is
126  // because row_non_zero_[row] is only lazily cleaned.
127  int32 DecreaseRowDegree(RowIndex row);
128  int32 DecreaseColDegree(ColIndex col);
129 
130  // Returns true if the column has been deleted by DeleteRowAndColumn().
131  bool IsColumnDeleted(ColIndex col) const;
132 
133  // Removes from the corresponding row_non_zero_[row] the columns that have
134  // been previously deleted by DeleteRowAndColumn().
135  void RemoveDeletedColumnsFromRow(RowIndex row);
136 
137  // Returns the first non-deleted column index from this row or kInvalidCol if
138  // none can be found.
139  ColIndex GetFirstNonDeletedColumnFromRow(RowIndex row) const;
140 
141  // Performs a generic Gaussian update of the residual matrix:
142  // - DeleteRowAndColumn() must already have been called.
143  // - The non-zero pattern is augmented (set union) by the one of the
144  // outer product of the pivot column and row.
145  //
146  // Important: as a small optimization, this function does not call
147  // DecreaseRowDegree() on the row in the pivot column. This has to be done by
148  // the client.
149  void Update(RowIndex pivot_row, ColIndex pivot_col,
150  const SparseColumn& column);
151 
152  // Returns the degree (i.e. the number of non-zeros) of the given column.
153  // This is only valid for the column indices still in the residual matrix.
154  int32 ColDegree(ColIndex col) const {
155  DCHECK(!deleted_columns_[col]);
156  return col_degree_[col];
157  }
158 
159  // Returns the degree (i.e. the number of non-zeros) of the given row.
160  // This is only valid for the row indices still in the residual matrix.
161  int32 RowDegree(RowIndex row) const { return row_degree_[row]; }
162 
163  // Returns the set of non-zeros of the given row (unsorted).
164  // Call RemoveDeletedColumnsFromRow(row) to clean the row first.
165  // This is only valid for the row indices still in the residual matrix.
166  const absl::InlinedVector<ColIndex, 6>& RowNonZero(RowIndex row) const {
167  return row_non_zero_[row];
168  }
169 
170  private:
171  // Augments the non-zero pattern of the given row by taking its union with the
172  // non-zero pattern of the given pivot_row.
173  void MergeInto(RowIndex pivot_row, RowIndex row);
174 
175  // Different version of MergeInto() that works only if the non-zeros position
176  // of each row are sorted in increasing order. The output will also be sorted.
177  //
178  // TODO(user): This is currently not used but about the same speed as the
179  // non-sorted version. Investigate more.
180  void MergeIntoSorted(RowIndex pivot_row, RowIndex row);
181 
182  // Using InlinedVector helps because we usually have many rows with just a few
183  // non-zeros. Note that on a 64 bits computer we get exactly 6 inlined int32
184  // elements without extra space, and the size of the inlined vector is 4 times
185  // 64 bits.
186  //
187  // TODO(user): We could be even more efficient since a size of int32 is enough
188  // for us and we could store in common the inlined/not-inlined size.
192  DenseBooleanRow deleted_columns_;
193  DenseBooleanRow bool_scratchpad_;
194  std::vector<ColIndex> col_scratchpad_;
195  ColIndex num_non_deleted_columns_;
196 
197  DISALLOW_COPY_AND_ASSIGN(MatrixNonZeroPattern);
198 };
199 
200 // Adjustable priority queue of columns. Pop() returns a column with the
201 // smallest degree first (degree = number of entries in the column).
202 // Empty columns (i.e. with degree 0) are not stored in the queue.
204  public:
206 
207  // Releases the memory used by this class.
208  void Clear();
209 
210  // Clears the queue and prepares it to store up to num_cols column indices
211  // with a degree from 1 to max_degree included.
212  void Reset(int32 max_degree, ColIndex num_cols);
213 
214  // Changes the degree of a column and make sure it is in the queue. The degree
215  // must be non-negative (>= 0) and at most equal to the value of num_cols used
216  // in Reset(). A degree of zero will remove the column from the queue.
217  void PushOrAdjust(ColIndex col, int32 degree);
218 
219  // Removes the column index with higher priority from the queue and returns
220  // it. Returns kInvalidCol if the queue is empty.
221  ColIndex Pop();
222 
223  private:
226  std::vector<std::vector<ColIndex>> col_by_degree_;
227  int32 min_degree_;
228  DISALLOW_COPY_AND_ASSIGN(ColumnPriorityQueue);
229 };
230 
231 // Contains a set of columns indexed by ColIndex. This is like a SparseMatrix
232 // but this class is optimized for the case where only a small subset of columns
233 // is needed at the same time (like it is the case in our LU algorithm). It
234 // reuses the memory of the columns that are no longer needed.
236  public:
238 
239  // Resets the repository to num_cols empty columns.
240  void Reset(ColIndex num_cols);
241 
242  // Returns the column with given index.
243  const SparseColumn& column(ColIndex col) const;
244 
245  // Gets the mutable column with given column index. The returned vector
246  // address is only valid until the next call to mutable_column().
247  SparseColumn* mutable_column(ColIndex col);
248 
249  // Clears the column with given index and releases its memory to the common
250  // memory pool that is used to create new mutable_column() on demand.
251  void ClearAndReleaseColumn(ColIndex col);
252 
253  // Reverts this class to its initial state. This releases the memory of the
254  // columns that were used but not the memory of this class member (this should
255  // be fine).
256  void Clear();
257 
258  private:
259  // mutable_column(col) is stored in columns_[mapping_[col]].
260  // The columns_ that can be reused have their index stored in free_columns_.
261  const SparseColumn empty_column_;
263  std::vector<int> free_columns_;
264  std::vector<SparseColumn> columns_;
265  DISALLOW_COPY_AND_ASSIGN(SparseMatrixWithReusableColumnMemory);
266 };
267 
268 // The class that computes either the actual L.U decomposition, or the
269 // permutation P and Q such that P.B.Q^{-1} will have a sparse L.U
270 // decomposition.
271 class Markowitz {
272  public:
274 
275  // Computes the full factorization with P, Q, L and U.
276  //
277  // If the matrix is singular, the returned status will indicate it and the
278  // permutation (col_perm) will contain a maximum non-singular set of columns
279  // of the matrix. Moreover, by adding singleton columns with a one at the rows
280  // such that 'row_perm[row] == kInvalidRow', then the matrix will be
281  // non-singular.
282  ABSL_MUST_USE_RESULT Status
283  ComputeLU(const CompactSparseMatrixView& basis_matrix,
284  RowPermutation* row_perm, ColumnPermutation* col_perm,
285  TriangularMatrix* lower, TriangularMatrix* upper);
286 
287  // Only computes P and Q^{-1}, L and U can be computed later from these
288  // permutations using another algorithm (for instance left-looking L.U). This
289  // may be faster than computing the full L and U at the same time but the
290  // current implementation is not optimized for this.
291  //
292  // It behaves the same as ComputeLU() for singular matrices.
293  //
294  // This function also works with a non-square matrix. It will return a set of
295  // independent columns of maximum size. If all the given columns are
296  // independent, the returned Status will be OK.
297  ABSL_MUST_USE_RESULT Status ComputeRowAndColumnPermutation(
298  const CompactSparseMatrixView& basis_matrix, RowPermutation* row_perm,
299  ColumnPermutation* col_perm);
300 
301  // Releases the memory used by this class.
302  void Clear();
303 
304  // Returns a string containing the statistics for this class.
305  std::string StatString() const { return stats_.StatString(); }
306 
307  // Sets the current parameters.
308  void SetParameters(const GlopParameters& parameters) {
309  parameters_ = parameters;
310  }
311 
312  private:
313  // Statistics about this class.
314  struct Stats : public StatsGroup {
315  Stats()
316  : StatsGroup("Markowitz"),
317  basis_singleton_column_ratio("basis_singleton_column_ratio", this),
318  basis_residual_singleton_column_ratio(
319  "basis_residual_singleton_column_ratio", this),
320  pivots_without_fill_in_ratio("pivots_without_fill_in_ratio", this),
321  degree_two_pivot_columns("degree_two_pivot_columns", this) {}
322  RatioDistribution basis_singleton_column_ratio;
323  RatioDistribution basis_residual_singleton_column_ratio;
324  RatioDistribution pivots_without_fill_in_ratio;
325  RatioDistribution degree_two_pivot_columns;
326  };
327  Stats stats_;
328 
329  // Fast track for singleton columns of the matrix. Fills a part of the row and
330  // column permutation that move these columns in order to form an identity
331  // sub-matrix on the upper left.
332  //
333  // Note(user): Linear programming bases usually have a resonable percentage of
334  // slack columns in them, so this gives a big speedup.
335  void ExtractSingletonColumns(const CompactSparseMatrixView& basis_matrix,
336  RowPermutation* row_perm,
337  ColumnPermutation* col_perm, int* index);
338 
339  // Fast track for columns that form a triangular matrix. This does not find
340  // all of them, but because the column are ordered in the same way they were
341  // ordered at the end of the previous factorization, this is likely to find
342  // quite a few.
343  //
344  // The main gain here is that it avoids taking these columns into account in
345  // InitializeResidualMatrix() and later in RemoveRowFromResidualMatrix().
346  void ExtractResidualSingletonColumns(
347  const CompactSparseMatrixView& basis_matrix, RowPermutation* row_perm,
348  ColumnPermutation* col_perm, int* index);
349 
350  // Helper function for determining if a column is a residual singleton column.
351  // If it is, RowIndex* row contains the index of the single residual edge.
352  bool IsResidualSingletonColumn(const ColumnView& column,
353  const RowPermutation& row_perm, RowIndex* row);
354 
355  // Returns the column of the current residual matrix with an index 'col' in
356  // the initial matrix. We compute it by solving a linear system with the
357  // current lower_ and the last computed column 'col' of a previous residual
358  // matrix. This uses the same algorithm as a left-looking factorization (see
359  // lu_factorization.h for more details).
360  const SparseColumn& ComputeColumn(const RowPermutation& row_perm,
361  ColIndex col);
362 
363  // Finds an entry in the residual matrix with a low Markowitz score and a high
364  // enough magnitude. Returns its Markowitz score and updates the given
365  // pointers.
366  //
367  // We use the strategy of Zlatev, "On some pivotal strategies in Gaussian
368  // elimination by sparse technique" (1980). SIAM J. Numer. Anal. 17 18-30. It
369  // consists of looking for the best pivot in only a few columns (usually 3
370  // or 4) amongst the ones which have the lowest number of entries.
371  //
372  // Amongst the pivots with a minimum Markowitz number, we choose the one
373  // with highest magnitude. This doesn't apply to pivots with a 0 Markowitz
374  // number because all such pivots will have to be taken at some point anyway.
375  int64 FindPivot(const RowPermutation& row_perm,
376  const ColumnPermutation& col_perm, RowIndex* pivot_row,
377  ColIndex* pivot_col, Fractional* pivot_coefficient);
378 
379  // Updates the degree of a given column in the internal structure of the
380  // class.
381  void UpdateDegree(ColIndex col, int degree);
382 
383  // Removes all the coefficients in the residual matrix that are on the given
384  // row or column. In both cases, the pivot row or column is ignored.
385  void RemoveRowFromResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
386  void RemoveColumnFromResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
387 
388  // Updates the residual matrix given the pivot position. This is needed if the
389  // pivot row and pivot column both have more than one entry. Otherwise, the
390  // residual matrix can be updated more efficiently by calling one of the
391  // Remove...() functions above.
392  void UpdateResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
393 
394  // Pointer to the matrix to factorize.
395  CompactSparseMatrixView const* basis_matrix_;
396 
397  // These matrices are transformed during the algorithm into the final L and U
398  // matrices modulo some row and column permutations. Note that the columns of
399  // these matrices stay in the initial order.
400  SparseMatrixWithReusableColumnMemory permuted_lower_;
401  SparseMatrixWithReusableColumnMemory permuted_upper_;
402 
403  // These matrices will hold the final L and U. The are created columns by
404  // columns from left to right, and at the end, their rows are permuted by
405  // ComputeLU() to become triangular.
406  TriangularMatrix lower_;
407  TriangularMatrix upper_;
408 
409  // The columns of permuted_lower_ for which we do need a call to
410  // PermutedLowerSparseSolve(). This speeds up ComputeColumn().
411  DenseBooleanRow permuted_lower_column_needs_solve_;
412 
413  // Contains the non-zero positions of the current residual matrix (the
414  // lower-right square matrix that gets smaller by one row and column at each
415  // Gaussian elimination step).
416  MatrixNonZeroPattern residual_matrix_non_zero_;
417 
418  // Data structure to access the columns by increasing degree.
419  ColumnPriorityQueue col_by_degree_;
420 
421  // True as long as only singleton columns of the residual matrix are used.
422  bool contains_only_singleton_columns_;
423 
424  // Boolean used to know when col_by_degree_ become useful.
425  bool is_col_by_degree_initialized_;
426 
427  // FindPivot() needs to look at the first entries of col_by_degree_, it
428  // temporary put them here before pushing them back to col_by_degree_.
429  std::vector<ColIndex> examined_col_;
430 
431  // Singleton column indices are kept here rather than in col_by_degree_ to
432  // optimize the algorithm: as long as this or singleton_row_ are not empty,
433  // col_by_degree_ do not need to be initialized nor updated.
434  std::vector<ColIndex> singleton_column_;
435 
436  // List of singleton row indices.
437  std::vector<RowIndex> singleton_row_;
438 
439  // Proto holding all the parameters of this algorithm.
440  GlopParameters parameters_;
441 
442  DISALLOW_COPY_AND_ASSIGN(Markowitz);
443 };
444 
445 } // namespace glop
446 } // namespace operations_research
447 
448 #endif // OR_TOOLS_GLOP_MARKOWITZ_H_
operations_research::glop::MatrixNonZeroPattern::RowDegree
int32 RowDegree(RowIndex row) const
Definition: markowitz.h:161
operations_research::glop::MatrixNonZeroPattern::Reset
void Reset(RowIndex num_rows, ColIndex num_cols)
Definition: markowitz.cc:550
operations_research::glop::SparseMatrixWithReusableColumnMemory::SparseMatrixWithReusableColumnMemory
SparseMatrixWithReusableColumnMemory()
Definition: markowitz.h:237
operations_research::glop::MatrixNonZeroPattern::Clear
void Clear()
Definition: markowitz.cc:541
operations_research::StatsGroup
Definition: stats.h:131
operations_research::glop::SparseMatrixWithReusableColumnMemory::mutable_column
SparseColumn * mutable_column(ColIndex col)
Definition: markowitz.cc:854
operations_research::glop::MatrixNonZeroPattern::RemoveDeletedColumnsFromRow
void RemoveDeletedColumnsFromRow(RowIndex row)
Definition: markowitz.cc:640
operations_research::RatioDistribution
Definition: stats.h:263
logging.h
operations_research::glop::CompactSparseMatrixView
Definition: sparse.h:471
operations_research::glop::MatrixNonZeroPattern::Update
void Update(RowIndex pivot_row, ColIndex pivot_col, const SparseColumn &column)
Definition: markowitz.cc:662
operations_research::glop::Status
Definition: status.h:24
operations_research::glop::ColumnPriorityQueue::Pop
ColIndex Pop()
Definition: markowitz.cc:830
operations_research::glop::MatrixNonZeroPattern::DeleteRowAndColumn
void DeleteRowAndColumn(RowIndex pivot_row, ColIndex pivot_col)
Definition: markowitz.cc:626
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::glop::MatrixNonZeroPattern
Definition: markowitz.h:98
operations_research::glop::MatrixNonZeroPattern::MatrixNonZeroPattern
MatrixNonZeroPattern()
Definition: markowitz.h:100
operations_research::glop::ColumnPriorityQueue::ColumnPriorityQueue
ColumnPriorityQueue()
Definition: markowitz.h:205
operations_research::glop::SparseColumn
Definition: sparse_column.h:44
int64
int64_t int64
Definition: integral_types.h:34
operations_research::glop::Markowitz::SetParameters
void SetParameters(const GlopParameters &parameters)
Definition: markowitz.h:308
index
int index
Definition: pack.cc:508
int32
int int32
Definition: integral_types.h:33
operations_research::glop::SparseMatrixWithReusableColumnMemory::Reset
void Reset(ColIndex num_cols)
Definition: markowitz.cc:842
operations_research::glop::Fractional
double Fractional
Definition: lp_types.h:77
operations_research::glop::MatrixNonZeroPattern::IsColumnDeleted
bool IsColumnDeleted(ColIndex col) const
Definition: markowitz.cc:636
operations_research::glop::ColumnPriorityQueue::PushOrAdjust
void PushOrAdjust(ColIndex col, int32 degree)
Definition: markowitz.cc:807
stats.h
operations_research::glop::MatrixNonZeroPattern::GetFirstNonDeletedColumnFromRow
ColIndex GetFirstNonDeletedColumnFromRow(RowIndex row) const
Definition: markowitz.cc:654
operations_research::glop::SparseMatrixWithReusableColumnMemory::Clear
void Clear()
Definition: markowitz.cc:876
operations_research::glop::Markowitz::ComputeRowAndColumnPermutation
ABSL_MUST_USE_RESULT Status ComputeRowAndColumnPermutation(const CompactSparseMatrixView &basis_matrix, RowPermutation *row_perm, ColumnPermutation *col_perm)
Definition: markowitz.cc:26
operations_research::glop::StrictITIVector< RowIndex, int32 >
operations_research::glop::MatrixNonZeroPattern::InitializeFromMatrixSubset
void InitializeFromMatrixSubset(const CompactSparseMatrixView &basis_matrix, const RowPermutation &row_perm, const ColumnPermutation &col_perm, std::vector< ColIndex > *singleton_columns, std::vector< RowIndex > *singleton_rows)
Definition: markowitz.cc:560
operations_research::glop::MatrixNonZeroPattern::ColDegree
int32 ColDegree(ColIndex col) const
Definition: markowitz.h:154
operations_research::glop::DenseBooleanRow
StrictITIVector< ColIndex, bool > DenseBooleanRow
Definition: lp_types.h:302
operations_research::glop::MatrixNonZeroPattern::AddEntry
void AddEntry(RowIndex row, ColIndex col)
Definition: markowitz.cc:612
operations_research::glop::ColumnPriorityQueue::Reset
void Reset(int32 max_degree, ColIndex num_cols)
Definition: markowitz.cc:799
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::glop::MatrixNonZeroPattern::DecreaseRowDegree
int32 DecreaseRowDegree(RowIndex row)
Definition: markowitz.cc:622
operations_research::glop::TriangularMatrix
Definition: sparse.h:502
operations_research::glop::RowPermutation
Permutation< RowIndex > RowPermutation
Definition: lp_data/permutation.h:93
operations_research::glop::Markowitz::StatString
std::string StatString() const
Definition: markowitz.h:305
operations_research::glop::Permutation< RowIndex >
operations_research::glop::Markowitz::Clear
void Clear()
Definition: markowitz.cc:163
operations_research::glop::ColumnPermutation
Permutation< ColIndex > ColumnPermutation
Definition: lp_data/permutation.h:94
operations_research::glop::ColumnPriorityQueue
Definition: markowitz.h:203
absl::StrongVector
Definition: strong_vector.h:76
operations_research::glop::SparseMatrixWithReusableColumnMemory::column
const SparseColumn & column(ColIndex col) const
Definition: markowitz.cc:848
col
ColIndex col
Definition: markowitz.cc:176
operations_research::glop::SparseMatrixWithReusableColumnMemory::ClearAndReleaseColumn
void ClearAndReleaseColumn(ColIndex col)
Definition: markowitz.cc:869
row
RowIndex row
Definition: markowitz.cc:175
operations_research::glop::ColumnPriorityQueue::Clear
void Clear()
Definition: markowitz.cc:793
operations_research::glop::Markowitz
Definition: markowitz.h:271
operations_research::glop::MatrixNonZeroPattern::DecreaseColDegree
int32 DecreaseColDegree(ColIndex col)
Definition: markowitz.cc:618
operations_research::glop::Markowitz::Markowitz
Markowitz()
Definition: markowitz.h:273
operations_research::glop::SparseMatrixWithReusableColumnMemory
Definition: markowitz.h:235
permutation.h
lp_types.h
operations_research::glop::Markowitz::ComputeLU
ABSL_MUST_USE_RESULT Status ComputeLU(const CompactSparseMatrixView &basis_matrix, RowPermutation *row_perm, ColumnPermutation *col_perm, TriangularMatrix *lower, TriangularMatrix *upper)
Definition: markowitz.cc:143
sparse_column.h
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
sparse.h
status.h
parameters.pb.h
operations_research::glop::MatrixNonZeroPattern::RowNonZero
const absl::InlinedVector< ColIndex, 6 > & RowNonZero(RowIndex row) const
Definition: markowitz.h:166