73 #ifndef OR_TOOLS_GLOP_MARKOWITZ_H_
74 #define OR_TOOLS_GLOP_MARKOWITZ_H_
78 #include "absl/container/inlined_vector.h"
81 #include "ortools/glop/parameters.pb.h"
107 void Reset(RowIndex num_rows, ColIndex num_cols);
115 std::vector<ColIndex>* singleton_columns,
116 std::vector<RowIndex>* singleton_rows);
150 void Update(RowIndex pivot_row, ColIndex pivot_col,
157 return col_degree_[
col];
168 return row_non_zero_[
row];
174 void MergeInto(RowIndex pivot_row, RowIndex
row);
181 void MergeIntoSorted(RowIndex pivot_row, RowIndex
row);
195 std::vector<ColIndex> col_scratchpad_;
196 ColIndex num_non_deleted_columns_;
213 void Reset(
int32 max_degree, ColIndex num_cols);
227 std::vector<std::vector<ColIndex>> col_by_degree_;
241 void Reset(ColIndex num_cols);
264 std::vector<int> free_columns_;
265 std::vector<SparseColumn> columns_;
283 ABSL_MUST_USE_RESULT
Status
306 std::string
StatString()
const {
return stats_.StatString(); }
318 basis_singleton_column_ratio(
"basis_singleton_column_ratio", this),
319 basis_residual_singleton_column_ratio(
320 "basis_residual_singleton_column_ratio", this),
321 pivots_without_fill_in_ratio(
"pivots_without_fill_in_ratio", this),
322 degree_two_pivot_columns(
"degree_two_pivot_columns", this) {}
336 void ExtractSingletonColumns(
const CompactSparseMatrixView& basis_matrix,
347 void ExtractResidualSingletonColumns(
348 const CompactSparseMatrixView& basis_matrix,
RowPermutation* row_perm,
353 bool IsResidualSingletonColumn(
const ColumnView& column,
378 ColIndex* pivot_col,
Fractional* pivot_coefficient);
382 void UpdateDegree(ColIndex
col,
int degree);
386 void RemoveRowFromResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
387 void RemoveColumnFromResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
393 void UpdateResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
396 CompactSparseMatrixView
const* basis_matrix_;
401 SparseMatrixWithReusableColumnMemory permuted_lower_;
402 SparseMatrixWithReusableColumnMemory permuted_upper_;
407 TriangularMatrix lower_;
408 TriangularMatrix upper_;
417 MatrixNonZeroPattern residual_matrix_non_zero_;
420 ColumnPriorityQueue col_by_degree_;
423 bool contains_only_singleton_columns_;
426 bool is_col_by_degree_initialized_;
430 std::vector<ColIndex> examined_col_;
435 std::vector<ColIndex> singleton_column_;
438 std::vector<RowIndex> singleton_row_;
441 GlopParameters parameters_;
#define DCHECK(condition)
void Reset(int32 max_degree, ColIndex num_cols)
void PushOrAdjust(ColIndex col, int32 degree)
ABSL_MUST_USE_RESULT Status ComputeLU(const CompactSparseMatrixView &basis_matrix, RowPermutation *row_perm, ColumnPermutation *col_perm, TriangularMatrix *lower, TriangularMatrix *upper)
void SetParameters(const GlopParameters ¶meters)
std::string StatString() const
ABSL_MUST_USE_RESULT Status ComputeRowAndColumnPermutation(const CompactSparseMatrixView &basis_matrix, RowPermutation *row_perm, ColumnPermutation *col_perm)
const absl::InlinedVector< ColIndex, 6 > & RowNonZero(RowIndex row) const
bool IsColumnDeleted(ColIndex col) const
void RemoveDeletedColumnsFromRow(RowIndex row)
void DeleteRowAndColumn(RowIndex pivot_row, ColIndex pivot_col)
void AddEntry(RowIndex row, ColIndex col)
void Reset(RowIndex num_rows, ColIndex num_cols)
void Update(RowIndex pivot_row, ColIndex pivot_col, const SparseColumn &column)
int32 ColDegree(ColIndex col) const
int32 DecreaseRowDegree(RowIndex row)
int32 DecreaseColDegree(ColIndex col)
int32 RowDegree(RowIndex row) const
ColIndex GetFirstNonDeletedColumnFromRow(RowIndex row) const
void InitializeFromMatrixSubset(const CompactSparseMatrixView &basis_matrix, const RowPermutation &row_perm, const ColumnPermutation &col_perm, std::vector< ColIndex > *singleton_columns, std::vector< RowIndex > *singleton_rows)
void Reset(ColIndex num_cols)
void ClearAndReleaseColumn(ColIndex col)
SparseColumn * mutable_column(ColIndex col)
const SparseColumn & column(ColIndex col) const
SparseMatrixWithReusableColumnMemory()
Permutation< ColIndex > ColumnPermutation
StrictITIVector< ColIndex, bool > DenseBooleanRow
Permutation< RowIndex > RowPermutation
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...