Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
update_row.h
Go to the documentation of this file.
1// Copyright 2010-2024 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#ifndef OR_TOOLS_GLOP_UPDATE_ROW_H_
15#define OR_TOOLS_GLOP_UPDATE_ROW_H_
16
17#include <cstdint>
18#include <string>
19#include <vector>
20
21#include "absl/types/span.h"
23#include "ortools/glop/parameters.pb.h"
28#include "ortools/util/stats.h"
29
30namespace operations_research {
31namespace glop {
32
33// During a simplex iteration, when the basis 'leaving_row' has been
34// selected, one of the main quantities needed in the primal or dual simplex
35// algorithm is called the update row.
36//
37// By definition, update_row[col] is the coefficient at position
38// 'leaving_row' in the current basis of the column 'col' of the matrix A.
39//
40// One efficient way to compute it is to compute the left inverse by B of the
41// unit vector with a one at the given leaving_row, and then to take the
42// scalar product of this left inverse with all the columns of A:
43// update_row[col] = (unit_{leaving_row} . B^{-1}) . A_col
44class UpdateRow {
45 public:
46 // Takes references to the linear program data we need.
47 UpdateRow(const CompactSparseMatrix& matrix,
48 const CompactSparseMatrix& transposed_matrix,
49 const VariablesInfo& variables_info, const RowToColMapping& basis,
50 const BasisFactorization& basis_factorization);
51
52 // This type is neither copyable nor movable.
53 UpdateRow(const UpdateRow&) = delete;
54 UpdateRow& operator=(const UpdateRow&) = delete;
55
56 // Invalidates the current update row and unit_row_left_inverse so the next
57 // call to ComputeUpdateRow() will recompute everything and not just return
58 // right away.
59 void Invalidate();
60
61 // Computes the left inverse of the given unit row, and stores it in
62 // unit_row_left_inverse_. The result is computed only once if leaving_row do
63 // not change, this until the next Invalidate() call.
64 void ComputeUnitRowLeftInverse(RowIndex leaving_row);
65
66 // Computes the relevant coefficients (See GetIsRelevantBitRow() in
67 // VariablesInfo) of the update row. The result is only computed once
68 // if leaving_row do not change, this until the next Invalidate() call.
69 void ComputeUpdateRow(RowIndex leaving_row);
70
71 // Returns the left inverse of the unit row as computed by the last call to
72 // ComputeUpdateRow().
74
75 // Returns true if ComputeUpdateRow() was called since the last Invalidate().
76 bool IsComputedFor(RowIndex leaving_row) const {
77 return update_row_computed_for_ == leaving_row;
78 }
79
80 // Returns the update coefficients and non-zero positions corresponding to the
81 // last call to ComputeUpdateRow().
82 //
83 // TODO(user): Consider returning a packed vector of coefficient parallel to
84 // GetNonZeroPositions() instead. It should be fast to compute and iteration
85 // later should be quicker.
86 const DenseRow& GetCoefficients() const;
87 absl::Span<const ColIndex> GetNonZeroPositions() const;
88 Fractional GetCoefficient(ColIndex col) const { return coefficient_[col]; }
89
90 // Computes the update row including all position and fill output with it.
91 // We only use this when ComputeUnitRowLeftInverse() has already been called
92 // and we CHECK that.
93 void ComputeFullUpdateRow(RowIndex leaving_row, DenseRow* output) const;
94
95 // Sets the algorithm parameters.
96 void SetParameters(const GlopParameters& parameters);
97
98 // Returns statistics about this class as a string.
99 std::string StatString() const { return stats_.StatString(); }
100
101 // Only used for testing.
102 // Computes as the update row the product 'lhs' times the linear program
103 // matrix given at construction. Only the relevant columns matter (see
104 // VariablesInfo) and 'algorithm' can be one of "column", "row" or
105 // "row_hypersparse".
107 const std::string& algorithm);
108
109 // Deterministic time used by the scalar product computation of this class.
110 double DeterministicTime() const {
111 return DeterministicTimeForFpOperations(num_operations_);
112 }
113
114 // This returns the asked unit row left inverse. It temporarily invalidate
115 // the class state by calling Invalidate().
116 const ScatteredRow& ComputeAndGetUnitRowLeftInverse(RowIndex leaving_row);
117
118 private:
119 // ComputeUpdateRow() does the common work and calls one of these functions
120 // depending on the situation.
121 void ComputeUpdatesRowWise();
122 void ComputeUpdatesRowWiseHypersparse();
123 void ComputeUpdatesColumnWise();
124 void ComputeUpdatesForSingleRow(ColIndex row_as_col);
125
126 // Problem data that should be updated from outside.
127 const CompactSparseMatrix& matrix_;
128 const CompactSparseMatrix& transposed_matrix_;
129 const VariablesInfo& variables_info_;
130 const RowToColMapping& basis_;
131 const BasisFactorization& basis_factorization_;
132
133 // Left inverse by B of a unit row. Its scalar product with a column 'a' of A
134 // gives the value of the right inverse of 'a' on the 'leaving_row'.
135 ScatteredRow unit_row_left_inverse_;
136
137 // The non-zeros of unit_row_left_inverse_ above the drop tolerance.
138 std::vector<ColIndex> unit_row_left_inverse_filtered_non_zeros_;
139
140 // Holds the current update row data.
141 // Note that non_zero_position_set_ is not always up to date.
142 int num_non_zeros_ = 0;
143 ColIndexVector non_zero_position_list_;
144 DenseBitRow non_zero_position_set_;
145 DenseRow coefficient_;
146
147 // Boolean used to avoid recomputing many times the same thing.
148 bool compute_update_row_;
149 RowIndex left_inverse_computed_for_ = kInvalidRow;
150 RowIndex update_row_computed_for_ = kInvalidRow;
151
152 // Statistics about this class.
153 struct Stats : public StatsGroup {
154 Stats()
155 : StatsGroup("UpdateRow"),
156 unit_row_left_inverse_density("unit_row_left_inverse_density", this),
157 unit_row_left_inverse_accuracy("unit_row_left_inverse_accuracy",
158 this),
159 update_row_density("update_row_density", this) {}
160 RatioDistribution unit_row_left_inverse_density;
161 DoubleDistribution unit_row_left_inverse_accuracy;
162 RatioDistribution update_row_density;
163 };
164
165 // Track the number of basic floating point multiplication.
166 // Used by DeterministicTime().
167 int64_t num_operations_;
168
169 // Glop standard classes.
170 GlopParameters parameters_;
171 Stats stats_;
172};
173
174} // namespace glop
175} // namespace operations_research
176
177#endif // OR_TOOLS_GLOP_UPDATE_ROW_H_
Statistic on the distribution of a sequence of doubles.
Definition stats.h:276
Statistic on the distribution of a sequence of ratios, displayed as %.
Definition stats.h:265
Base class to print a nice summary of a group of statistics.
Definition stats.h:128
std::string StatString() const
Definition stats.cc:77
const DenseRow & GetCoefficients() const
const ScatteredRow & ComputeAndGetUnitRowLeftInverse(RowIndex leaving_row)
Definition update_row.cc:62
void SetParameters(const GlopParameters &parameters)
Sets the algorithm parameters.
void ComputeFullUpdateRow(RowIndex leaving_row, DenseRow *output) const
std::string StatString() const
Returns statistics about this class as a string.
Definition update_row.h:99
const ScatteredRow & GetUnitRowLeftInverse() const
Definition update_row.cc:58
void ComputeUnitRowLeftInverse(RowIndex leaving_row)
Definition update_row.cc:70
void ComputeUpdateRow(RowIndex leaving_row)
Definition update_row.cc:87
UpdateRow(const UpdateRow &)=delete
This type is neither copyable nor movable.
UpdateRow & operator=(const UpdateRow &)=delete
bool IsComputedFor(RowIndex leaving_row) const
Returns true if ComputeUpdateRow() was called since the last Invalidate().
Definition update_row.h:76
double DeterministicTime() const
Deterministic time used by the scalar product computation of this class.
Definition update_row.h:110
Fractional GetCoefficient(ColIndex col) const
Definition update_row.h:88
UpdateRow(const CompactSparseMatrix &matrix, const CompactSparseMatrix &transposed_matrix, const VariablesInfo &variables_info, const RowToColMapping &basis, const BasisFactorization &basis_factorization)
Takes references to the linear program data we need.
Definition update_row.cc:34
void ComputeUpdateRowForBenchmark(const DenseRow &lhs, const std::string &algorithm)
absl::Span< const ColIndex > GetNonZeroPositions() const
SatParameters parameters
ColIndex col
Definition markowitz.cc:187
std::vector< ColIndex > ColIndexVector
Vector of row or column indices. Useful to list the non-zero positions.
Definition lp_types.h:362
constexpr RowIndex kInvalidRow(-1)
static double DeterministicTimeForFpOperations(int64_t n)
Definition lp_types.h:435
In SWIG mode, we don't want anything besides these top-level includes.