OR-Tools  8.2
dual_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_DUAL_EDGE_NORMS_H_
15 #define OR_TOOLS_GLOP_DUAL_EDGE_NORMS_H_
16 
18 #include "ortools/glop/parameters.pb.h"
23 #include "ortools/util/stats.h"
24 
25 namespace operations_research {
26 namespace glop {
27 
28 // This class maintains the dual edge squared norms to be used in the
29 // dual steepest edge pricing. The dual edge u_i associated with a basic
30 // variable of row index i is such that u_i.B = e_i where e_i is the unit row
31 // vector with a 1.0 at position i and B the current basis. We call such vector
32 // u_i an unit row left inverse, and it can be computed by
33 //
34 // basis_factorization.LeftSolveForUnitRow(i, &u_i);
35 //
36 // Instead of computing each ||u_i|| at every iteration, it is more efficient to
37 // update them incrementally for each basis pivot applied to B. See the code or
38 // the papers below for details:
39 //
40 // J.J. Forrest, D. Goldfarb, "Steepest-edge simplex algorithms for linear
41 // programming", Mathematical Programming 57 (1992) 341-374, North-Holland.
42 // http://www.springerlink.com/content/q645w3t2q229m248/
43 //
44 // Achim Koberstein, "The dual simplex method, techniques for a fast and stable
45 // implementation", PhD, Paderborn, Univ., 2005.
46 // http://digital.ub.uni-paderborn.de/hs/download/pdf/3885?originalFilename=true
48  public:
49  // Takes references to the linear program data we need.
50  explicit DualEdgeNorms(const BasisFactorization& basis_factorization);
51 
52  // Clears, i.e. reset the object to its initial value. This will trigger a
53  // full norm recomputation on the next GetEdgeSquaredNorms().
54  void Clear();
55 
56  // When we just add new constraints to the matrix and use an incremental
57  // solve, we do not need to recompute the norm of the old rows, and the norm
58  // of the new ones can be just set to 1 as long as we use identity columns for
59  // these.
60  void ResizeOnNewRows(RowIndex new_size);
61 
62  // If this is true, then the caller must re-factorize the basis before the
63  // next call to GetEdgeSquaredNorms(). This is because the latter will
64  // recompute the norms from scratch and therefore needs a hightened precision
65  // and speed.
67 
68  // Returns the dual edge squared norms. This is only valid if the caller
69  // properly called UpdateBeforeBasisPivot() before each basis pivot, or just
70  // called Clear().
72 
73  // Updates the norms if the columns of the basis where permuted.
74  void UpdateDataOnBasisPermutation(const ColumnPermutation& col_perm);
75 
76  // Updates the norms just before a basis pivot is applied:
77  // - The column at leaving_row will leave the basis and the column at
78  // entering_col will enter it.
79  // - direction is the right inverse of the entering column.
80  // - unit_row_left_inverse is the left inverse of the unit row with index
81  // given by the leaving_row. This is also the leaving dual edge.
82  void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row,
83  const ScatteredColumn& direction,
84  const ScatteredRow& unit_row_left_inverse);
85 
86  // Sets the algorithm parameters.
87  void SetParameters(const GlopParameters& parameters) {
88  parameters_ = parameters;
89  }
90 
91  // Stats related functions.
92  std::string StatString() const { return stats_.StatString(); }
93 
94  private:
95  // Recomputes the dual edge squared norms from scratch with maximum precision.
96  // The matrix must have been refactorized before because we will do a lot of
97  // inversions. See NeedsBasisRefactorization(). This is checked in debug mode.
98  void ComputeEdgeSquaredNorms();
99 
100  // Computes the vector tau needed to update the norms using a right solve:
101  // B.tau = (u_i)^T, u_i.B = e_i for i = leaving_row.
102  const DenseColumn& ComputeTau(const ScatteredColumn& unit_row_left_inverse);
103 
104  // Statistics.
105  struct Stats : public StatsGroup {
106  Stats()
107  : StatsGroup("DualEdgeNorms"),
108  tau_density("tau_density", this),
109  edge_norms_accuracy("edge_norms_accuracy", this),
110  lower_bounded_norms("lower_bounded_norms", this) {}
111  RatioDistribution tau_density;
112  DoubleDistribution edge_norms_accuracy;
113  IntegerDistribution lower_bounded_norms;
114  };
115  Stats stats_;
116 
117  // Parameters.
118  GlopParameters parameters_;
119 
120  // Problem data that should be updated from outside.
121  const BasisFactorization& basis_factorization_;
122 
123  // The dual edge norms.
124  DenseColumn edge_squared_norms_;
125 
126  // Whether we should recompute the norm from scratch.
127  bool recompute_edge_squared_norms_;
128 
129  DISALLOW_COPY_AND_ASSIGN(DualEdgeNorms);
130 };
131 
132 } // namespace glop
133 } // namespace operations_research
134 
135 #endif // OR_TOOLS_GLOP_DUAL_EDGE_NORMS_H_
void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, const ScatteredRow &unit_row_left_inverse)
void UpdateDataOnBasisPermutation(const ColumnPermutation &col_perm)
DualEdgeNorms(const BasisFactorization &basis_factorization)
void SetParameters(const GlopParameters &parameters)
SatParameters parameters
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...