OR-Tools  8.2
matrix_scaler.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// The SparseMatrixScaler class provides tools to scale a SparseMatrix, i.e.
15// reduce the range of its coefficients and make for each column and each row
16// the maximum magnitude of its coefficients equal to 1.
17//
18// In the case there are bounds or costs on the columns or a right-hand side
19// related to each row, SparseMatrixScaler provides the tools to scale those
20// appropriately.
21//
22// More precisely, suppose we have the Linear Program:
23// min c.x
24// s.t A.x = b
25// with l <= x <= u
26//
27// The rows of A are scaled by left-multiplying it by a diagonal matrix R
28// whose elements R_ii correspond to the scaling factor of row i.
29// The columns of A are scaled by right-multiplying it by a diagonal matrix C
30// whose elements C_jj correspond to the scaling factor of column j.
31//
32// We obtain a matrix A' = R.A.C.
33//
34// We wish to scale x, c, b, l, u so as to work on the scaled problem:
35// min c'.x'
36// s.t A'.x' = b'
37// with l' <= x' <= u'
38//
39// The right-hand side b needs to be left-multiplied by R, the cost function c
40// needs to be right-multiplied by C. Finally, x, and its lower- and upper-bound
41// vectors l and u need to be left-multiplied by C^-1.
42//
43// Note also that the dual vector y is scaled as follows:
44// y'.R = y, thus y' = y.R^-1.
45//
46// The complete transformation is thus:
47// A' = R.A.C,
48// b' = R.b,
49// c' = c.C,
50// x' = C^-1.x,
51// l' = C^-1.l,
52// u' = C^-1.u,
53// y' = y.R^-1.
54//
55// The validity of the above transformation can be checked by computing:
56// c'.x' = c.C.C^-1.x = c.x.
57// and:
58// A'.x' = R.A.C.C^-1.x = R.A.x = R.b = b'.
59
60#ifndef OR_TOOLS_LP_DATA_MATRIX_SCALER_H_
61#define OR_TOOLS_LP_DATA_MATRIX_SCALER_H_
62
63#include <vector>
64
66#include "ortools/base/macros.h"
67#include "ortools/glop/parameters.pb.h"
69#include "ortools/glop/status.h"
72
73namespace operations_research {
74namespace glop {
75
76class SparseMatrix;
77
79 public:
81
82 // Initializes the object with the SparseMatrix passed as argument.
83 // The row and column scaling factors are all set to 1.0 (i.e. no scaling.)
84 // In terms of matrices, R and C are set to identity matrices.
85 void Init(SparseMatrix* matrix);
86
87 // Clears the object, and puts it back into the same state as after being
88 // constructed.
89 void Clear();
90
91 // The column col of the matrix was multiplied by ColScalingFactor(col). The
92 // variable bounds and objective coefficient at the same columsn where DIVIDED
93 // by that same factor. If col is outside the matrix size, this returns 1.0.
94 Fractional ColScalingFactor(ColIndex col) const;
95
96 // The constraint row of the matrix was multiplied by RowScalingFactor(row),
97 // same for the constraint bounds (which is not the same as for the variable
98 // bounds for a column!). If row is outside the matrix size, this returns 1.0.
99 Fractional RowScalingFactor(RowIndex row) const;
100
101 // The inverse of both factor above (this is how we keep them) so this
102 // direction should be faster to query (no 1.0 / factor).
103 Fractional ColUnscalingFactor(ColIndex col) const;
104 Fractional RowUnscalingFactor(RowIndex row) const;
105
106 // TODO(user): rename function and field to col_scales (and row_scales)
107 const DenseRow& col_scale() const { return col_scale_; }
108
109 // Scales the matrix.
110 void Scale(GlopParameters::ScalingAlgorithm method);
111
112 // Solves the scaling problem as a linear program.
113 Status LPScale();
114
115 // Unscales the matrix.
116 void Unscale();
117
118 // Scales a row vector up or down (depending whether parameter up is true or
119 // false) using the scaling factors determined by Scale().
120 // Scaling up means multiplying by the scaling factors, while scaling down
121 // means dividing by the scaling factors.
122 void ScaleRowVector(bool up, DenseRow* row_vector) const;
123
124 // Scales a column vector up or down (depending whether parameter up is true
125 // or false) using the scaling factors determined by Scale().
126 // Scaling up means multiplying by the scaling factors, while scaling down
127 // means dividing by the scaling factors.
128 void ScaleColumnVector(bool up, DenseColumn* column_vector) const;
129
130 // Computes the variance of the non-zero coefficients of the matrix.
131 // Used by Scale() do decide when to stop.
133
134 // Scales the rows. Returns the number of rows that have been scaled.
135 // Helper function to Scale().
136 RowIndex ScaleRowsGeometrically();
137
138 // Scales the columns. Returns the number of columns that have been scaled.
139 // Helper function to Scale().
140 ColIndex ScaleColumnsGeometrically();
141
142 // Equilibrates the rows. Returns the number of rows that have been scaled.
143 // Helper function to Scale().
144 RowIndex EquilibrateRows();
145
146 // Equilibrates the Columns. Returns the number of columns that have been
147 // scaled. Helper function to Scale().
148 ColIndex EquilibrateColumns();
149
150 private:
151 // Convert the matrix to be scaled into a linear program.
152 void GenerateLinearProgram(LinearProgram*);
153
154 // Scales the row indexed by row by 1/factor.
155 // Used by ScaleMatrixRowsGeometrically and EquilibrateRows.
156 RowIndex ScaleMatrixRows(const DenseColumn& factors);
157
158 // Scales the column index by col by 1/factor.
159 // Used by ScaleColumnsGeometrically and EquilibrateColumns.
160 void ScaleMatrixColumn(ColIndex col, Fractional factor);
161
162 // Looks up the index to the scale factor variable for this matrix row, in the
163 // LinearProgram, or creates it. Note lp_ must be initialized first.
164 ColIndex GetRowScaleIndex(RowIndex row_num);
165
166 // As above, but for the columns of the matrix.
167 ColIndex GetColumnScaleIndex(ColIndex col_num);
168
169 // Returns a string containing information on the progress of the scaling
170 // algorithm. This is not meant to be called in an optimized mode as it takes
171 // some time to compute the displayed quantities.
172 std::string DebugInformationString() const;
173
174 // Pointer to the matrix to be scaled.
175 SparseMatrix* matrix_;
176
177 // Member pointer for convenience, in particular for GetRowScaleIndex and
178 // GetColumnScaleIndex.
179 LinearProgram* lp_;
180
181 // Array of scaling factors for each row. Indexed by row number.
182 DenseColumn row_scale_;
183
184 // Array of scaling factors for each column. Indexed by column number.
185 DenseRow col_scale_;
186
187 DISALLOW_COPY_AND_ASSIGN(SparseMatrixScaler);
188};
189
190} // namespace glop
191} // namespace operations_research
192
193#endif // OR_TOOLS_LP_DATA_MATRIX_SCALER_H_
Fractional RowScalingFactor(RowIndex row) const
Fractional ColScalingFactor(ColIndex col) const
void ScaleColumnVector(bool up, DenseColumn *column_vector) const
void ScaleRowVector(bool up, DenseRow *row_vector) const
void Scale(GlopParameters::ScalingAlgorithm method)
Fractional ColUnscalingFactor(ColIndex col) const
Fractional RowUnscalingFactor(RowIndex row) const
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...