73 #ifndef OR_TOOLS_GLOP_MARKOWITZ_H_
74 #define OR_TOOLS_GLOP_MARKOWITZ_H_
78 #include "absl/container/inlined_vector.h"
106 void Reset(RowIndex num_rows, ColIndex num_cols);
114 std::vector<ColIndex>* singleton_columns,
115 std::vector<RowIndex>* singleton_rows);
149 void Update(RowIndex pivot_row, ColIndex pivot_col,
156 return col_degree_[
col];
167 return row_non_zero_[
row];
173 void MergeInto(RowIndex pivot_row, RowIndex
row);
180 void MergeIntoSorted(RowIndex pivot_row, RowIndex
row);
194 std::vector<ColIndex> col_scratchpad_;
195 ColIndex num_non_deleted_columns_;
212 void Reset(
int32 max_degree, ColIndex num_cols);
226 std::vector<std::vector<ColIndex>> col_by_degree_;
240 void Reset(ColIndex num_cols);
263 std::vector<int> free_columns_;
264 std::vector<SparseColumn> columns_;
282 ABSL_MUST_USE_RESULT
Status
305 std::string
StatString()
const {
return stats_.StatString(); }
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) {}
335 void ExtractSingletonColumns(
const CompactSparseMatrixView& basis_matrix,
346 void ExtractResidualSingletonColumns(
347 const CompactSparseMatrixView& basis_matrix,
RowPermutation* row_perm,
352 bool IsResidualSingletonColumn(
const ColumnView& column,
377 ColIndex* pivot_col,
Fractional* pivot_coefficient);
381 void UpdateDegree(ColIndex
col,
int degree);
385 void RemoveRowFromResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
386 void RemoveColumnFromResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
392 void UpdateResidualMatrix(RowIndex pivot_row, ColIndex pivot_col);
395 CompactSparseMatrixView
const* basis_matrix_;
400 SparseMatrixWithReusableColumnMemory permuted_lower_;
401 SparseMatrixWithReusableColumnMemory permuted_upper_;
406 TriangularMatrix lower_;
407 TriangularMatrix upper_;
416 MatrixNonZeroPattern residual_matrix_non_zero_;
419 ColumnPriorityQueue col_by_degree_;
422 bool contains_only_singleton_columns_;
425 bool is_col_by_degree_initialized_;
429 std::vector<ColIndex> examined_col_;
434 std::vector<ColIndex> singleton_column_;
437 std::vector<RowIndex> singleton_row_;
440 GlopParameters parameters_;
448 #endif // OR_TOOLS_GLOP_MARKOWITZ_H_