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 
26 namespace operations_research {
27 namespace 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().
83  const DenseRow& GetDevexWeights();
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...