OR-Tools  8.2
primal_edge_norms.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_PRIMAL_EDGE_NORMS_H_
15#define OR_TOOLS_GLOP_PRIMAL_EDGE_NORMS_H_
16
18#include "ortools/glop/parameters.pb.h"
24#include "ortools/util/stats.h"
25
26namespace operations_research {
27namespace glop {
28
29// This class maintains the primal edge squared norms (and other variants) to be
30// used in the primal pricing step. Instead of computing the needed values from
31// scractch at each iteration, it is more efficient to update them incrementally
32// for each basis pivot applied to the simplex basis matrix B.
33//
34// Terminology:
35// - To each non-basic column 'a' of a matrix A, we can associate an "edge" in
36// the kernel of A equal to 1.0 on the index of 'a' and '-B^{-1}.a' on the
37// basic variables.
38// - 'B^{-1}.a' is called the "right inverse" of 'a'.
39// - The entering edge is the edge we are following during a simplex step,
40// and we call "direction" the reverse of this edge restricted to the
41// basic variables, i.e. the right inverse of the entering column.
42//
43// Papers:
44// - D. Goldfarb, J.K. Reid, "A practicable steepest-edge simplex algorithm"
45// Mathematical Programming 12 (1977) 361-371, North-Holland.
46// http://www.springerlink.com/content/g8335137n3j16934/
47// - J.J. Forrest, D. Goldfarb, "Steepest-edge simplex algorithms for linear
48// programming", Mathematical Programming 57 (1992) 341-374, North-Holland.
49// http://www.springerlink.com/content/q645w3t2q229m248/
50// - Ping-Qi Pan "A fast simplex algorithm for linear programming".
51// http://www.optimization-online.org/DB_FILE/2007/10/1805.pdf
52// - Ping-Qi Pan, "Efficient nested pricing in the simplex algorithm",
53// http://www.optimization-online.org/DB_FILE/2007/10/1810.pdf
55 public:
56 // Takes references to the linear program data we need. Note that we assume
57 // that the matrix will never change in our back, but the other references are
58 // supposed to reflect the correct state.
59 PrimalEdgeNorms(const CompactSparseMatrix& compact_matrix,
60 const VariablesInfo& variables_info,
61 const BasisFactorization& basis_factorization);
62
63 // Clears, i.e. resets the object to its initial value. This will trigger
64 // a recomputation for the next Get*() method call.
65 void Clear();
66
67 // If this is true, then the caller must re-factorize the basis before the
68 // next call to GetEdgeSquaredNorms(). This is because the latter will
69 // recompute the norms from scratch and therefore needs a hightened precision
70 // and speed.
71 bool NeedsBasisRefactorization() const;
72
73 // Returns the primal edge squared norms. This is only valid if the caller
74 // properly called UpdateBeforeBasisPivot() before each basis pivot, or if
75 // this is the first call to this function after a Clear(). Note that only the
76 // relevant columns are filled.
78
79 // Returns an approximation of the edges norms "devex".
80 // This is only valid if the caller properly called UpdateBeforeBasisPivot()
81 // before each basis pivot, or if this is the first call to this function
82 // after a Clear().
84
85 // Returns the L2 norms of all the columns of A.
86 // Note that this is currently not cleared by Clear().
88
89 // Compares the current entering edge norm with its precise version (using the
90 // direction that wasn't avaible before) and triggers a full recomputation if
91 // the precision is not good enough (see recompute_edges_norm_threshold in
92 // GlopParameters). As a side effect, this replace the entering_col edge
93 // norm with its precise version.
94 void TestEnteringEdgeNormPrecision(ColIndex entering_col,
95 const ScatteredColumn& direction);
96
97 // Updates any internal data BEFORE the given simplex pivot is applied to B.
98 // Note that no updates are needed in case of a bound flip.
99 // The arguments are in order:
100 // - The index of the entering non-basic column of A.
101 // - The index in B of the leaving basic variable.
102 // - The 'direction', i.e. the right inverse of the entering column.
103 // - The update row (see UpdateRow), which will only be computed if needed.
104 void UpdateBeforeBasisPivot(ColIndex entering_col, ColIndex leaving_col,
105 RowIndex leaving_row,
106 const ScatteredColumn& direction,
107 UpdateRow* update_row);
108
109 // Sets the algorithm parameters.
110 void SetParameters(const GlopParameters& parameters) {
111 parameters_ = parameters;
112 }
113
114 // Returns a string with statistics about this class.
115 std::string StatString() const { return stats_.StatString(); }
116
117 // Deterministic time used by the scalar product computation of this class.
118 double DeterministicTime() const {
119 return DeterministicTimeForFpOperations(num_operations_);
120 }
121
122 private:
123 // Statistics about this class.
124 struct Stats : public StatsGroup {
125 Stats()
126 : StatsGroup("PrimalEdgeNorms"),
127 direction_left_inverse_density("direction_left_inverse_density",
128 this),
129 direction_left_inverse_accuracy("direction_left_inverse_accuracy",
130 this),
131 edges_norm_accuracy("edges_norm_accuracy", this),
132 lower_bounded_norms("lower_bounded_norms", this) {}
133 RatioDistribution direction_left_inverse_density;
134 DoubleDistribution direction_left_inverse_accuracy;
135 DoubleDistribution edges_norm_accuracy;
136 IntegerDistribution lower_bounded_norms;
137 };
138
139 // Recompute the matrix column L2 norms from scratch.
140 void ComputeMatrixColumnNorms();
141
142 // Recompute the edge squared L2 norms from scratch.
143 void ComputeEdgeSquaredNorms();
144
145 // Compute the left inverse of the direction.
146 // The first argument is there for checking precision.
147 void ComputeDirectionLeftInverse(ColIndex entering_col,
148 const ScatteredColumn& direction);
149
150 // Updates edges_squared_norm_ according to the given pivot.
151 void UpdateEdgeSquaredNorms(ColIndex entering_col, ColIndex leaving_col,
152 RowIndex leaving_row,
153 const DenseColumn& direction,
154 const UpdateRow& update_row);
155
156 // Resets all devex weights to 1.0 .
157 void ResetDevexWeights();
158
159 // Updates devex_weights_ according to the given pivot.
160 void UpdateDevexWeights(ColIndex entering_col, ColIndex leaving_col,
161 RowIndex leaving_row, const DenseColumn& direction,
162 const UpdateRow& update_row);
163
164 // Problem data that should be updated from outside.
165 const CompactSparseMatrix& compact_matrix_;
166 const VariablesInfo& variables_info_;
167 const BasisFactorization& basis_factorization_;
168
169 // Internal data.
170 GlopParameters parameters_;
171 Stats stats_;
172
173 // Booleans to control what happens on the next ChooseEnteringColumn() call.
174 bool must_refactorize_basis_;
175 bool recompute_edge_squared_norms_;
176 bool reset_devex_weights_;
177
178 // Norm^2 of the edges of the relevant columns of A.
179 DenseRow edge_squared_norms_;
180
181 // Norm of all the columns of A.
182 DenseRow matrix_column_norms_;
183
184 // Approximation of edges norms "devex".
185 // Denoted by vector 'w' in Pin Qi Pan (1810.pdf section 1.1.4)
186 // At any time, devex_weights_ >= 1.0.
187 DenseRow devex_weights_;
188
189 // Tracks number of updates of the devex weights since we have to reset
190 // them to 1.0 every now and then.
191 int num_devex_updates_since_reset_;
192
193 // Left inverse by B of the 'direction'. This is the transpose of 'v' in the
194 // steepest edge paper. Its scalar product with a column 'a' of A gives the
195 // value of the scalar product of the 'direction' with the right inverse of
196 // 'a'.
197 ScatteredRow direction_left_inverse_;
198
199 // Used by DeterministicTime().
200 int64 num_operations_;
201
202 DISALLOW_COPY_AND_ASSIGN(PrimalEdgeNorms);
203};
204
205} // namespace glop
206} // namespace operations_research
207
208#endif // OR_TOOLS_GLOP_PRIMAL_EDGE_NORMS_H_
PrimalEdgeNorms(const CompactSparseMatrix &compact_matrix, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization)
void UpdateBeforeBasisPivot(ColIndex entering_col, ColIndex leaving_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)
void TestEnteringEdgeNormPrecision(ColIndex entering_col, const ScatteredColumn &direction)
void SetParameters(const GlopParameters &parameters)
SatParameters parameters
int64_t int64
static double DeterministicTimeForFpOperations(int64 n)
Definition: lp_types.h:379
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...