1 // Copyright 2010-2021 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 
19 #include "ortools/glop/basis_representation.h"
20 #include "ortools/glop/parameters.pb.h"
21 #include "ortools/glop/variables_info.h"
22 #include "ortools/lp_data/lp_types.h"
23 #include "ortools/lp_data/scattered_vector.h"
24 #include "ortools/util/stats.h"
25 
26 namespace operations_research {
27 namespace glop {
28 
29 // During a simplex iteration, when the basis 'leaving_row' has been
30 // selected, one of the main quantities needed in the primal or dual simplex
31 // algorithm is called the update row.
32 //
33 // By definition, update_row[col] is the coefficient at position
34 // 'leaving_row' in the current basis of the column 'col' of the matrix A.
35 //
36 // One efficient way to compute it is to compute the left inverse by B of the
37 // unit vector with a one at the given leaving_row, and then to take the
38 // scalar product of this left inverse with all the columns of A:
39 //     update_row[col] = (unit_{leaving_row} . B^{-1}) . A_col
40 class UpdateRow {
41  public:
42   // Takes references to the linear program data we need.
43   UpdateRow(const CompactSparseMatrix& matrix,
44             const CompactSparseMatrix& transposed_matrix,
45             const VariablesInfo& variables_info, const RowToColMapping& basis,
46             const BasisFactorization& basis_factorization);
47 
48   // Invalidates the current update row and unit_row_left_inverse so the next
49   // call to ComputeUpdateRow() will recompute everything and not just return
50   // right away.
51   void Invalidate();
52 
53   // Computes the relevant coefficients (See GetIsRelevantBitRow() in
54   // VariablesInfo) of the update row. The result is only computed once until
55   // the next Invalidate() call and calling this function more than once will
56   // have no effect until then.
57   void ComputeUpdateRow(RowIndex leaving_row);
58 
59   // Returns the left inverse of the unit row as computed by the last call to
60   // ComputeUpdateRow().
61   const ScatteredRow& GetUnitRowLeftInverse() const;
62 
63   // Returns true if ComputeUpdateRow() was called since the last Invalidate().
IsComputed()64   const bool IsComputed() const { return !compute_update_row_; }
65 
66   // Returns the update coefficients and non-zero positions corresponding to the
67   // last call to ComputeUpdateRow().
68   const DenseRow& GetCoefficients() const;
69   const ColIndexVector& GetNonZeroPositions() const;
GetCoefficient(ColIndex col)70   const Fractional GetCoefficient(ColIndex col) const {
71     return coefficient_[col];
72   }
73 
74   // This must be called after a call to ComputeUpdateRow(). It will fill
75   // all the non-relevant positions that where not filled by ComputeUpdateRow().
76   void RecomputeFullUpdateRow(RowIndex leaving_row);
77 
78   // Sets the algorithm parameters.
79   void SetParameters(const GlopParameters& parameters);
80 
81   // Returns statistics about this class as a string.
StatString()82   std::string StatString() const { return stats_.StatString(); }
83 
84   // Only used for testing.
85   // Computes as the update row the product 'lhs' times the linear program
86   // matrix given at construction. Only the relevant columns matter (see
87   // VariablesInfo) and 'algorithm' can be one of "column", "row" or
88   // "row_hypersparse".
89   void ComputeUpdateRowForBenchmark(const DenseRow& lhs,
90                                     const std::string& algorithm);
91 
92   // Deterministic time used by the scalar product computation of this class.
DeterministicTime()93   double DeterministicTime() const {
94     return DeterministicTimeForFpOperations(num_operations_);
95   }
96 
97   // This returns the asked unit row left inverse. It temporarily invalidate
98   // the class state by calling Invalidate().
99   const ScatteredRow& ComputeAndGetUnitRowLeftInverse(RowIndex leaving_row);
100 
101   // Advanced usage. This has side effects and should be used with care.
102   //
103   // Computes the left inverse of the given unit row, and stores it in
104   // unit_row_left_inverse_.
105   void ComputeUnitRowLeftInverse(RowIndex leaving_row);
106 
107  private:
108   // ComputeUpdateRow() does the common work and calls one of these functions
109   // depending on the situation.
110   void ComputeUpdatesRowWise();
111   void ComputeUpdatesRowWiseHypersparse();
112   void ComputeUpdatesColumnWise();
113 
114   // Problem data that should be updated from outside.
115   const CompactSparseMatrix& matrix_;
116   const CompactSparseMatrix& transposed_matrix_;
117   const VariablesInfo& variables_info_;
118   const RowToColMapping& basis_;
119   const BasisFactorization& basis_factorization_;
120 
121   // Left inverse by B of a unit row. Its scalar product with a column 'a' of A
122   // gives the value of the right inverse of 'a' on the 'leaving_row'.
123   ScatteredRow unit_row_left_inverse_;
124 
125   // The non-zeros of unit_row_left_inverse_ above the drop tolerance.
126   std::vector<ColIndex> unit_row_left_inverse_filtered_non_zeros_;
127 
128   // Holds the current update row data.
129   // TODO(user): Introduce a ScatteredSparseRow class?
130   ColIndexVector non_zero_position_list_;
131   DenseBitRow non_zero_position_set_;
132   DenseRow coefficient_;
133 
134   // Boolean used to avoid recomputing many times the same thing.
135   bool compute_update_row_;
136   RowIndex update_row_computed_for_;
137 
138   // Statistics about this class.
139   struct Stats : public StatsGroup {
StatsStats140     Stats()
141         : StatsGroup("UpdateRow"),
142           unit_row_left_inverse_density("unit_row_left_inverse_density", this),
143           unit_row_left_inverse_accuracy("unit_row_left_inverse_accuracy",
144                                          this),
145           update_row_density("update_row_density", this) {}
146     RatioDistribution unit_row_left_inverse_density;
147     DoubleDistribution unit_row_left_inverse_accuracy;
148     RatioDistribution update_row_density;
149   };
150 
151   // Track the number of basic floating point multiplication.
152   // Used by DeterministicTime().
153   int64_t num_operations_;
154 
155   // Glop standard classes.
156   GlopParameters parameters_;
157   Stats stats_;
158 
159   DISALLOW_COPY_AND_ASSIGN(UpdateRow);
160 };
161 
162 }  // namespace glop
163 }  // namespace operations_research
164 
165 #endif  // OR_TOOLS_GLOP_UPDATE_ROW_H_
166