 |
OR-Tools
8.1
|
Go to the documentation of this file.
29 #ifndef OR_TOOLS_LP_DATA_SPARSE_H_
30 #define OR_TOOLS_LP_DATA_SPARSE_H_
44 class CompactSparseMatrixView;
70 #if (!defined(_MSC_VER) || _MSC_VER >= 1800)
72 std::initializer_list<std::initializer_list<Fractional>> init_list);
121 template <
typename Matrix>
130 template <
typename Matrix>
177 ColIndex
num_cols()
const {
return ColIndex(columns_.size()); }
198 std::string
Dump()
const;
261 bool IsEmpty()
const {
return columns_.empty(); }
263 ColIndex
num_cols()
const {
return columns_.size(); }
274 extern template void SparseMatrix::PopulateFromTranspose<SparseMatrix>(
275 const SparseMatrix&
input);
276 extern template void SparseMatrix::PopulateFromPermutedMatrix<SparseMatrix>(
280 SparseMatrix::PopulateFromPermutedMatrix<CompactSparseMatrixView>(
311 void Reset(RowIndex num_rows);
316 ColIndex AddDenseColumn(
const DenseColumn& dense_column);
319 ColIndex AddDenseColumnPrefix(
const DenseColumn& dense_column,
324 ColIndex AddDenseColumnWithNonZeros(
const DenseColumn& dense_column,
325 const std::vector<RowIndex>& non_zeros);
331 ColIndex AddAndClearColumnWithNonZeros(
DenseColumn* column,
332 std::vector<RowIndex>* non_zeros);
336 return starts_[
col + 1] - starts_[
col];
341 DCHECK_EQ(coefficients_.size(), rows_.size());
342 return coefficients_.size();
349 DCHECK_EQ(coefficients_.size(), rows_.size());
350 return coefficients_.empty();
359 return ::util::IntegerRange<EntryIndex>(starts_[
col], starts_[
col + 1]);
362 RowIndex
EntryRow(EntryIndex i)
const {
return rows_[i]; }
369 const EntryIndex start = starts_[
col];
370 return ColumnView(starts_[
col + 1] - start, rows_.data() + start.value(),
371 coefficients_.data() + start.value());
377 return starts_[
col + 1] == starts_[
col];
384 for (
const EntryIndex i : Column(
col)) {
385 result += EntryCoefficient(i) * vector[
RowToColIndex(EntryRow(i))];
395 if (multiplier == 0.0)
return;
397 for (
const EntryIndex i : Column(
col)) {
398 (*dense_column)[EntryRow(i)] += multiplier * EntryCoefficient(i);
408 if (multiplier == 0.0)
return;
410 for (
const EntryIndex i : Column(
col)) {
411 const RowIndex
row = EntryRow(i);
412 column->
Add(
row, multiplier * EntryCoefficient(i));
421 ColumnCopyToClearedDenseColumn(
col, dense_column);
429 dense_column->
resize(num_rows_, 0.0);
430 for (
const EntryIndex i : Column(
col)) {
431 (*dense_column)[EntryRow(i)] = EntryCoefficient(i);
440 dense_column->
resize(num_rows_, 0.0);
442 for (
const EntryIndex i : Column(
col)) {
443 const RowIndex
row = EntryRow(i);
444 (*dense_column)[
row] = EntryCoefficient(i);
445 non_zeros->push_back(
row);
475 : compact_matrix_(*compact_matrix), basis_(*basis) {}
478 bool IsEmpty()
const {
return compact_matrix_.IsEmpty(); }
479 RowIndex
num_rows()
const {
return compact_matrix_.num_rows(); }
511 bool IsEmpty()
const {
return diagonal_coefficients_.empty(); }
515 return EntryIndex(num_cols_.value()) + coefficients_.size();
524 void Reset(RowIndex num_rows, ColIndex col_capacity);
541 void AddTriangularColumn(
const ColumnView& column, RowIndex diagonal_row);
542 void AddTriangularColumnWithGivenDiagonalEntry(
const SparseColumn& column,
543 RowIndex diagonal_row,
545 void AddDiagonalOnlyColumn(
Fractional diagonal_value);
551 void AddAndNormalizeTriangularColumn(
const SparseColumn& column,
552 RowIndex diagonal_row,
556 void ApplyRowPermutationToNonDiagonalEntries(
const RowPermutation& row_perm);
559 void CopyColumnToSparseColumn(ColIndex
col,
SparseColumn* output)
const;
568 return first_non_identity_column_;
573 return diagonal_coefficients_[
col];
600 void LowerSolveStartingAt(ColIndex start,
DenseColumn* rhs)
const;
636 void HyperSparseSolveWithReversedNonZeros(
640 void TransposeHyperSparseSolveWithReversedNonZeros(
648 void ComputeRowsToConsiderWithDfs(
RowIndexVector* non_zero_rows)
const;
654 void ComputeRowsToConsiderInSortedOrder(
RowIndexVector* non_zero_rows,
657 void ComputeRowsToConsiderInSortedOrder(
RowIndexVector* non_zero_rows)
const;
695 void PermutedLowerSparseSolve(
const ColumnView& rhs,
703 bool IsLowerTriangular()
const;
704 bool IsUpperTriangular()
const;
721 void PermutedComputeRowsToConsider(
const ColumnView& rhs,
729 Fractional ComputeInverseInfinityNormUpperBound()
const;
730 Fractional ComputeInverseInfinityNorm()
const;
734 template <
bool diagonal_of_ones>
735 void LowerSolveStartingAtInternal(ColIndex start,
DenseColumn* rhs)
const;
736 template <
bool diagonal_of_ones>
738 template <
bool diagonal_of_ones>
739 void TransposeLowerSolveInternal(
DenseColumn* rhs)
const;
740 template <
bool diagonal_of_ones>
741 void TransposeUpperSolveInternal(
DenseColumn* rhs)
const;
742 template <
bool diagonal_of_ones>
745 template <
bool diagonal_of_ones>
746 void HyperSparseSolveWithReversedNonZerosInternal(
748 template <
bool diagonal_of_ones>
749 void TransposeHyperSparseSolveInternal(
DenseColumn* rhs,
751 template <
bool diagonal_of_ones>
752 void TransposeHyperSparseSolveWithReversedNonZerosInternal(
757 void CloseCurrentColumn(
Fractional diagonal_value);
765 ColIndex first_non_identity_column_;
769 bool all_diagonal_coefficients_are_one_;
774 mutable std::vector<RowIndex> nodes_to_explore_;
777 mutable std::vector<RowIndex> lower_column_rows_;
778 mutable std::vector<RowIndex> upper_column_rows_;
779 mutable DenseColumn initially_all_zero_scratchpad_;
839 #endif // OR_TOOLS_LP_DATA_SPARSE_H_
void PopulateFromBasis(const MatrixView &matrix, const RowToColMapping &basis)
bool ColumnIsEmpty(ColIndex col) const
StrictITIVector< ColIndex, EntryIndex > starts_
void PopulateFromZero(RowIndex num_rows, ColIndex num_cols)
void resize(IntType size)
#define DCHECK_LT(val1, val2)
bool AppendRowsFromSparseMatrix(const SparseMatrix &matrix)
MatrixView(const SparseMatrix &matrix)
void ColumnCopyToDenseColumn(ColIndex col, DenseColumn *dense_column) const
RowIndex num_rows() const
void AppendUnitVector(RowIndex row, Fractional value)
void Add(Index index, Fractional value)
ColumnView column(ColIndex col) const
bool Equals(const SparseMatrix &a, Fractional tolerance) const
void ColumnAddMultipleToDenseColumn(ColIndex col, Fractional multiplier, DenseColumn *dense_column) const
Fractional ComputeOneNorm() const
RowIndex num_rows() const
Fractional EntryCoefficient(EntryIndex i) const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void PopulateFromProduct(const SparseMatrix &a, const SparseMatrix &b)
Fractional LookUpValue(RowIndex row, ColIndex col) const
EntryIndex num_entries() const
void PopulateFromSparseMatrix(const SparseMatrix &matrix)
ColIndex num_cols() const
EntryIndex num_entries() const
void DeleteRows(RowIndex num_rows, const RowPermutation &permutation)
Fractional ComputeInfinityNorm() const
#define RETURN_IF_NULL(x)
const ColumnView column(ColIndex col) const
void ApplyRowPermutation(const RowPermutation &row_perm)
ColIndex RowToColIndex(RowIndex row)
CompactSparseMatrix(const SparseMatrix &matrix)
ColIndex AppendEmptyColumn()
ColIndex num_cols() const
ColIndex num_cols() const
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
RowIndex EntryRow(EntryIndex i) const
void PopulateFromIdentity(ColIndex num_cols)
SparseColumn * mutable_column(ColIndex col)
void PopulateFromPermutedMatrix(const Matrix &a, const RowPermutation &row_perm, const ColumnPermutation &inverse_col_perm)
RowIndex num_rows() const
RowIndex num_rows() const
bool CheckNoDuplicates() const
RowIndex num_rows() const
void PopulateFromMatrixPair(const SparseMatrix &matrix_a, const SparseMatrix &matrix_b)
Fractional ComputeOneNorm() const
void Swap(SparseMatrix *matrix)
CompactSparseMatrixView(const CompactSparseMatrix *compact_matrix, const RowToColMapping *basis)
void AssignToZero(IntType size)
StrictITIVector< EntryIndex, RowIndex > rows_
EntryIndex ColumnNumEntries(ColIndex col) const
void PopulateFromLinearCombination(Fractional alpha, const SparseMatrix &a, Fractional beta, const SparseMatrix &b)
Permutation< RowIndex > RowPermutation
const SparseColumn & column(ColIndex col) const
ColIndex num_cols() const
Fractional GetDiagonalCoefficient(ColIndex col) const
void PopulateFromTranspose(const Matrix &input)
Permutation< ColIndex > ColumnPermutation
void PopulateFromMatrix(const SparseMatrix &matrix)
void ColumnCopyToClearedDenseColumnWithNonZeros(ColIndex col, DenseColumn *dense_column, RowIndexVector *non_zeros) const
StrictITIVector< EntryIndex, Fractional > coefficients_
::util::IntegerRange< EntryIndex > Column(ColIndex col) const
void ColumnCopyToClearedDenseColumn(ColIndex col, DenseColumn *dense_column) const
static int input(yyscan_t yyscanner)
void ComputeMinAndMaxMagnitudes(Fractional *min_magnitude, Fractional *max_magnitude) const
const SparseColumn & column(ColIndex col) const
void ColumnAddMultipleToSparseScatteredColumn(ColIndex col, Fractional multiplier, ScatteredColumn *column) const
#define DCHECK_EQ(val1, val2)
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Fractional ComputeInfinityNorm() const
EntryIndex num_entries() const
Fractional ColumnScalarProduct(ColIndex col, const DenseRow &vector) const
IntegerValue ComputeInfinityNorm(const LinearConstraint &constraint)
ColIndex GetFirstNonIdentityColumn() const
EntryIndex num_entries() const
RowIndex ColToRowIndex(ColIndex col)
bool ColumnIsDiagonalOnly(ColIndex col) const
std::vector< RowIndex > RowIndexVector
ColIndex num_cols() const
void SetNumRows(RowIndex num_rows)