29#ifndef OR_TOOLS_LP_DATA_SPARSE_H_
30#define OR_TOOLS_LP_DATA_SPARSE_H_
37#include "absl/log/check.h"
38#include "absl/types/span.h"
77#if (!defined(_MSC_VER) || _MSC_VER >= 1800)
79 std::initializer_list<std::initializer_list<Fractional>> init_list);
133 template <
typename Matrix>
142 template <
typename Matrix>
188 RowIndex
num_rows()
const {
return num_rows_; }
189 ColIndex
num_cols()
const {
return ColIndex(columns_.size()); }
210 std::string
Dump()
const;
237 const ColIndex
num_cols = matrix.num_cols();
239 for (ColIndex col(0); col <
num_cols; ++col) {
240 columns_[col] = &matrix.column(col);
242 num_rows_ = matrix.num_rows();
248 const SparseMatrix& matrix_b) {
249 const ColIndex
num_cols = matrix_a.num_cols() + matrix_b.num_cols();
251 for (ColIndex col(0); col < matrix_a.num_cols(); ++col) {
252 columns_[col] = &matrix_a.column(col);
254 for (ColIndex col(0); col < matrix_b.num_cols(); ++col) {
255 columns_[matrix_a.num_cols() + col] = &matrix_b.column(col);
257 num_rows_ = std::max(matrix_a.num_rows(), matrix_b.num_rows());
264 for (RowIndex row(0); row < basis.size(); ++row) {
267 num_rows_ = matrix.num_rows();
271 bool IsEmpty()
const {
return columns_.empty(); }
272 RowIndex
num_rows()
const {
return num_rows_; }
273 ColIndex
num_cols()
const {
return columns_.size(); }
306 : coefficients_(matrix->coefficients_.data()),
307 rows_(matrix->rows_.data()),
308 starts_(matrix->starts_.data()) {}
317 return ::util::IntegerRange<EntryIndex>(
starts_[col.value()],
318 starts_[col.value() + 1]);
320 Fractional EntryCoefficient(EntryIndex i)
const {
323 RowIndex EntryRow(EntryIndex i)
const {
return rows_[i.value()]; }
326 return starts_[col.value() + 1] - starts_[col.value()];
336 const RowIndex*
const rows_;
337 const EntryIndex*
const starts_;
341 ConstView view()
const {
return ConstView(
this); }
388 absl::Span<const RowIndex> non_zeros);
395 std::vector<RowIndex>* non_zeros);
403 EntryIndex num_entries()
const {
404 DCHECK_EQ(coefficients_.size(), rows_.size());
407 RowIndex num_rows()
const {
return num_rows_; }
408 ColIndex num_cols()
const {
return num_cols_; }
419 DCHECK_LT(col, num_cols_);
423 const EntryIndex start =
starts_[col];
430 bool ColumnIsEmpty(ColIndex col)
const {
431 return starts_[col + 1] == starts_[col];
437 return view().ColumnScalarProduct(col, vector.
const_view());
443 void ColumnAddMultipleToDenseColumn(ColIndex col,
Fractional multiplier,
445 if (multiplier == 0.0)
return;
446 const auto entry_rows =
rows_.view();
448 for (
const EntryIndex i :
Column(col)) {
449 dense_column[entry_rows[i]] += multiplier * entry_coeffs[i];
452 void ColumnAddMultipleToDenseColumn(ColIndex col,
Fractional multiplier,
455 dense_column->view());
461 void ColumnAddMultipleToSparseScatteredColumn(ColIndex col,
465 if (multiplier == 0.0)
return;
466 const auto entry_rows =
rows_.view();
468 for (
const EntryIndex i :
Column(col)) {
469 column->Add(entry_rows[i], multiplier * entry_coeffs[i]);
475 void ColumnCopyToDenseColumn(ColIndex col,
DenseColumn* dense_column)
const {
483 void ColumnCopyToClearedDenseColumn(ColIndex col,
487 const auto entry_rows =
rows_.view();
489 for (
const EntryIndex i :
Column(col)) {
490 (*dense_column)[entry_rows[i]] = entry_coeffs[i];
495 void ColumnCopyToClearedDenseColumnWithNonZeros(
501 const auto entry_rows =
rows_.view();
503 for (
const EntryIndex i :
Column(col)) {
504 const RowIndex row = entry_rows[i];
505 (*dense_column)[row] = entry_coeffs[i];
506 non_zeros->push_back(row);
515 return ::util::IntegerRange<EntryIndex>(starts_[col], starts_[col + 1]);
534 int i = starts_[col.value()].value();
535 const int end = starts_[col.value() + 1].value();
536 const int shifted_end = end - 3;
541 for (; i < shifted_end; i += 4) {
542 result1 += coefficients_[i] * vector[
RowToColIndex(rows_[i])];
543 result2 += coefficients_[i + 1] * vector[
RowToColIndex(rows_[i + 1])];
544 result3 += coefficients_[i + 2] * vector[
RowToColIndex(rows_[i + 2])];
545 result4 += coefficients_[i + 3] * vector[
RowToColIndex(rows_[i + 3])];
547 Fractional result = result1 + result2 + result3 + result4;
564class CompactSparseMatrixView {
568 : compact_matrix_(*compact_matrix),
569 columns_(basis->data(), basis->size().value()) {}
571 const std::vector<ColIndex>* columns)
572 : compact_matrix_(*compact_matrix), columns_(*columns) {}
575 bool IsEmpty()
const {
return compact_matrix_.IsEmpty(); }
576 RowIndex
num_rows()
const {
return compact_matrix_.num_rows(); }
577 ColIndex
num_cols()
const {
return ColIndex(columns_.size()); }
579 return compact_matrix_.column(columns_[col.value()]);
589 const absl::Span<const ColIndex> columns_;
612 bool IsEmpty()
const {
return diagonal_coefficients_.empty(); }
644 RowIndex diagonal_row,
646 void AddDiagonalOnlyColumn(
Fractional diagonal_value);
653 RowIndex diagonal_row,
657 void ApplyRowPermutationToNonDiagonalEntries(
const RowPermutation& row_perm);
660 void CopyColumnToSparseColumn(ColIndex col,
SparseColumn* output)
const;
668 ColIndex GetFirstNonIdentityColumn()
const {
669 return first_non_identity_column_;
673 Fractional GetDiagonalCoefficient(ColIndex col)
const {
674 return diagonal_coefficients_[col];
678 bool ColumnIsDiagonalOnly(ColIndex col)
const {
701 void LowerSolveStartingAt(ColIndex start,
DenseColumn* rhs)
const;
737 void HyperSparseSolveWithReversedNonZeros(
741 void TransposeHyperSparseSolveWithReversedNonZeros(
749 void ComputeRowsToConsiderWithDfs(
RowIndexVector* non_zero_rows)
const;
755 void ComputeRowsToConsiderInSortedOrder(
RowIndexVector* non_zero_rows)
const;
794 void PermutedLowerSparseSolve(
const ColumnView& rhs,
799 int64_t NumFpOperationsInLastPermutedLowerSparseSolve()
const {
800 return num_fp_operations_;
838 template <
bool diagonal_of_ones>
839 void LowerSolveStartingAtInternal(ColIndex start,
841 template <
bool diagonal_of_ones>
843 template <
bool diagonal_of_ones>
845 template <
bool diagonal_of_ones>
847 template <
bool diagonal_of_ones>
850 template <
bool diagonal_of_ones>
851 void HyperSparseSolveWithReversedNonZerosInternal(
853 template <
bool diagonal_of_ones>
856 template <
bool diagonal_of_ones>
857 void TransposeHyperSparseSolveWithReversedNonZerosInternal(
870 ColIndex first_non_identity_column_;
874 bool all_diagonal_coefficients_are_one_;
879 mutable std::vector<RowIndex> nodes_to_explore_;
882 int64_t num_fp_operations_;
883 mutable std::vector<RowIndex> lower_column_rows_;
884 mutable std::vector<RowIndex> upper_column_rows_;
885 mutable DenseColumn initially_all_zero_scratchpad_;
CompactSparseMatrixView(const CompactSparseMatrix *compact_matrix, const RowToColMapping *basis)
EntryIndex ColumnNumEntries(ColIndex col) const
ConstView(const CompactSparseMatrix *matrix)
Fractional ColumnScalarProduct(ColIndex col, DenseRow::ConstView vector) const
void Reset(RowIndex num_rows)
void PopulateFromMatrixView(const MatrixView &input)
CompactSparseMatrix & operator=(const CompactSparseMatrix &)=delete
CompactSparseMatrix()=default
ColIndex AddDenseColumnPrefix(DenseColumn::ConstView dense_column, RowIndex start)
Same as AddDenseColumn(), but only adds the non-zero from the given start.
StrictITIVector< EntryIndex, Fractional > coefficients_
void ColumnAddMultipleToDenseColumn(ColIndex col, Fractional multiplier, DenseColumn *dense_column) const
ColIndex AddDenseColumn(const DenseColumn &dense_column)
void PopulateFromSparseMatrixAndAddSlacks(const SparseMatrix &input)
StrictITIVector< ColIndex, EntryIndex > starts_
EntryIndex num_entries() const
Returns the matrix dimensions. See same functions in SparseMatrix.
ColIndex AddAndClearColumnWithNonZeros(DenseColumn *column, std::vector< RowIndex > *non_zeros)
RowIndex num_rows() const
bool IsEmpty() const
Returns whether or not this matrix contains any non-zero entries.
ColIndex AddDenseColumnWithNonZeros(const DenseColumn &dense_column, absl::Span< const RowIndex > non_zeros)
ColIndex num_cols() const
void AddEntryToCurrentColumn(RowIndex row, Fractional coeff)
Api to add columns one at the time.
bool ColumnIsEmpty(ColIndex col) const
EntryIndex ColumnNumEntries(ColIndex col) const
Returns the number of entries (i.e. degree) of the given column.
StrictITIVector< EntryIndex, RowIndex > rows_
void Swap(CompactSparseMatrix *other)
void ColumnCopyToClearedDenseColumn(ColIndex col, DenseColumn *dense_column) const
Fractional ColumnScalarProduct(ColIndex col, const DenseRow &vector) const
void PopulateFromTranspose(const CompactSparseMatrix &input)
RowIndex num_rows_
The matrix dimensions, properly updated by full and incremental builders.
::util::IntegerRange< EntryIndex > Column(ColIndex col) const
Functions to iterate on the entries of a given column.
ColumnView column(ColIndex col) const
void CloseCurrentColumn()
RowIndex num_rows() const
void PopulateFromMatrixPair(const SparseMatrix &matrix_a, const SparseMatrix &matrix_b)
Fractional ComputeInfinityNorm() const
ColIndex num_cols() const
void PopulateFromMatrix(const SparseMatrix &matrix)
Takes all the columns of the given matrix.
bool IsEmpty() const
Same behavior as the SparseMatrix functions above.
EntryIndex num_entries() const
Fractional ComputeOneNorm() const
void PopulateFromBasis(const MatrixView &matrix, const RowToColMapping &basis)
Takes only the columns of the given matrix that belongs to the given basis.
const SparseColumn & column(ColIndex col) const
void ComputeMinAndMaxMagnitudes(Fractional *min_magnitude, Fractional *max_magnitude) const
void PopulateFromProduct(const SparseMatrix &a, const SparseMatrix &b)
Multiplies SparseMatrix a by SparseMatrix b.
std::string Dump() const
Returns a dense representation of the matrix.
void PopulateFromPermutedMatrix(const Matrix &a, const RowPermutation &row_perm, const ColumnPermutation &inverse_col_perm)
const SparseColumn & column(ColIndex col) const
Access the underlying sparse columns.
SparseMatrix & operator=(const SparseMatrix &)=delete
void PopulateFromTranspose(const Matrix &input)
Instantiate needed templates.
bool CheckNoDuplicates() const
Call CheckNoDuplicates() on all columns, useful for doing a DCHECK.
void PopulateFromLinearCombination(Fractional alpha, const SparseMatrix &a, Fractional beta, const SparseMatrix &b)
SparseColumn * mutable_column(ColIndex col)
void AppendUnitVector(RowIndex row, Fractional value)
void Swap(SparseMatrix *matrix)
bool IsCleanedUp() const
Call IsCleanedUp() on all columns, useful for doing a DCHECK.
void ApplyRowPermutation(const RowPermutation &row_perm)
Applies the row permutation.
void DeleteRows(RowIndex num_rows, const RowPermutation &permutation)
void PopulateFromIdentity(ColIndex num_cols)
RowIndex num_rows() const
Return the matrix dimension.
Fractional ComputeInfinityNorm() const
void PopulateFromZero(RowIndex num_rows, ColIndex num_cols)
bool AppendRowsFromSparseMatrix(const SparseMatrix &matrix)
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
Fractional ComputeOneNorm() const
void PopulateFromSparseMatrix(const SparseMatrix &matrix)
bool Equals(const SparseMatrix &a, Fractional tolerance) const
ColIndex num_cols() const
ColIndex AppendEmptyColumn()
Appends an empty column and returns its index.
void SetNumRows(RowIndex num_rows)
Change the number of row of this matrix.
EntryIndex num_entries() const
Fractional LookUpValue(RowIndex row, ColIndex col) const
StrictITISpan< RowIndex, Fractional > View
void AssignToZero(IntType size)
StrictITISpan< ColIndex, const Fractional > ConstView
ConstView const_view() const
void resize(IntType size)
Fractional ComputeInverseInfinityNorm() const
bool IsUpperTriangular() const
Fractional ComputeInverseInfinityNormUpperBound() const
void PermutedComputeRowsToConsider(const ColumnView &rhs, const RowPermutation &row_perm, RowIndexVector *lower_column_rows, RowIndexVector *upper_column_rows)
bool IsLowerTriangular() const
StrictITIVector< RowIndex, ColIndex > RowToColMapping
std::vector< RowIndex > RowIndexVector
StrictITIVector< RowIndex, bool > DenseBooleanColumn
Column of booleans.
Permutation< ColIndex > ColumnPermutation
Permutation< RowIndex > RowPermutation
ColIndex RowToColIndex(RowIndex row)
Get the ColIndex corresponding to the column # row.
StrictITIVector< RowIndex, RowIndex > RowMapping
Column of row indices. Used to represent mappings between rows.
StrictITIVector< RowIndex, Fractional > DenseColumn
Column-vector types. Column-vector types are indexed by a row index.
StrictITIVector< ColIndex, Fractional > DenseRow
Row-vector types. Row-vector types are indexed by a column index.
StrictITIVector< ColIndex, bool > DenseBooleanRow
Row of booleans.
In SWIG mode, we don't want anything besides these top-level includes.
static int input(yyscan_t yyscanner)
#define RETURN_IF_NULL(x)