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
25namespace operations_research {
26namespace 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.
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...