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