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