OR-Tools  8.2
lp_data_utils.cc
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
15
16namespace operations_research {
17namespace glop {
18
19void ComputeSlackVariablesValues(const LinearProgram& linear_program,
20 DenseRow* values) {
21 DCHECK(values);
22 DCHECK_EQ(linear_program.num_variables(), values->size());
23
24 // If there are no slack variable, we can give up.
25 if (linear_program.GetFirstSlackVariable() == kInvalidCol) return;
26
27 const auto& transposed_matrix = linear_program.GetTransposeSparseMatrix();
28 for (RowIndex row(0); row < linear_program.num_constraints(); row++) {
29 const ColIndex slack_variable = linear_program.GetSlackVariable(row);
30
31 if (slack_variable == kInvalidCol) continue;
32
33 DCHECK_EQ(0.0, linear_program.constraint_lower_bounds()[row]);
34 DCHECK_EQ(0.0, linear_program.constraint_upper_bounds()[row]);
35
36 const RowIndex transposed_slack = ColToRowIndex(slack_variable);
37 Fractional activation = 0.0;
38 // Row in the initial matrix (column in the transposed).
39 const SparseColumn& sparse_row =
40 transposed_matrix.column(RowToColIndex(row));
41 for (const auto& entry : sparse_row) {
42 if (transposed_slack == entry.index()) continue;
43 activation +=
44 (*values)[RowToColIndex(entry.index())] * entry.coefficient();
45 }
46 (*values)[slack_variable] = -activation;
47 }
48}
49
50// This is separated from the LinearProgram class because of a cyclic dependency
51// when scaling as an LP.
53 // Create GlopParameters proto to get default scaling algorithm.
54 GlopParameters params;
55 Scale(lp, scaler, params.scaling_method());
56}
57
58// This is separated from LinearProgram class because of a cyclic dependency
59// when scaling as an LP.
61 GlopParameters::ScalingAlgorithm scaling_method) {
62 scaler->Init(&lp->matrix_);
63 scaler->Scale(
64 scaling_method); // Compute R and C, and replace the matrix A by R.A.C
65 scaler->ScaleRowVector(false,
66 &lp->objective_coefficients_); // oc = oc.C
67 scaler->ScaleRowVector(true,
68 &lp->variable_upper_bounds_); // cl = cl.C^-1
69 scaler->ScaleRowVector(true,
70 &lp->variable_lower_bounds_); // cu = cu.C^-1
71 scaler->ScaleColumnVector(false, &lp->constraint_upper_bounds_); // rl = R.rl
72 scaler->ScaleColumnVector(false, &lp->constraint_lower_bounds_); // ru = R.ru
73 lp->transpose_matrix_is_consistent_ = false;
74}
75
76void LpScalingHelper::Scale(LinearProgram* lp) { Scale(GlopParameters(), lp); }
77
78void LpScalingHelper::Scale(const GlopParameters& params, LinearProgram* lp) {
79 scaler_.Clear();
80 ::operations_research::glop::Scale(lp, &scaler_, params.scaling_method());
81 bound_scaling_factor_ = 1.0 / lp->ScaleBounds();
82 objective_scaling_factor_ = 1.0 / lp->ScaleObjective(params.cost_scaling());
83}
84
86 scaler_.Clear();
87 bound_scaling_factor_ = 1.0;
88 objective_scaling_factor_ = 1.0;
89}
90
92 // During scaling a col was multiplied by ColScalingFactor() and the variable
93 // bounds divided by it.
94 return scaler_.ColUnscalingFactor(col) * bound_scaling_factor_;
95}
96
98 Fractional value) const {
99 // Just the opposite of ScaleVariableValue().
100 return value / (scaler_.ColUnscalingFactor(col) * bound_scaling_factor_);
101}
102
104 Fractional value) const {
105 // The reduced cost move like the objective and the col scale.
106 return value * scaler_.ColUnscalingFactor(col) / objective_scaling_factor_;
107}
108
110 Fractional value) const {
111 // The dual value move like the objective and the inverse of the row scale.
112 return value / (scaler_.RowUnscalingFactor(row) * objective_scaling_factor_);
113}
114
116 Fractional value) const {
117 // The activity move with the row_scale and the bound_scaling_factor.
118 return value * scaler_.RowUnscalingFactor(row) / bound_scaling_factor_;
119}
120
122 ColIndex basis_col, ScatteredRow* left_inverse) const {
123 const Fractional global_factor = scaler_.ColUnscalingFactor(basis_col);
124
125 // We have left_inverse * [RowScale * B * ColScale] = unit_row.
126 if (left_inverse->non_zeros.empty()) {
127 const ColIndex num_rows = left_inverse->values.size();
128 for (ColIndex col(0); col < num_rows; ++col) {
129 left_inverse->values[col] /=
130 scaler_.RowUnscalingFactor(ColToRowIndex(col)) * global_factor;
131 }
132 } else {
133 for (const ColIndex col : left_inverse->non_zeros) {
134 left_inverse->values[col] /=
135 scaler_.RowUnscalingFactor(ColToRowIndex(col)) * global_factor;
136 }
137 }
138}
139
141 const RowToColMapping& basis, ColIndex col,
142 ScatteredColumn* right_inverse) const {
143 const Fractional global_factor = scaler_.ColScalingFactor(col);
144
145 // [RowScale * B * BColScale] * inverse = RowScale * column * ColScale.
146 // That is B * (BColScale * inverse) = columm * ColScale[col].
147 if (right_inverse->non_zeros.empty()) {
148 const RowIndex num_rows = right_inverse->values.size();
149 for (RowIndex row(0); row < num_rows; ++row) {
150 right_inverse->values[row] /=
151 scaler_.ColUnscalingFactor(basis[row]) * global_factor;
152 }
153 } else {
154 for (const RowIndex row : right_inverse->non_zeros) {
155 right_inverse->values[row] /=
156 scaler_.ColUnscalingFactor(basis[row]) * global_factor;
157 }
158 }
159}
160
161} // namespace glop
162} // namespace operations_research
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
const SparseMatrix & GetTransposeSparseMatrix() const
Definition: lp_data.cc:375
ColIndex GetSlackVariable(RowIndex row) const
Definition: lp_data.cc:753
Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method)
Definition: lp_data.cc:1186
const DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
const DenseColumn & constraint_upper_bounds() const
Definition: lp_data.h:217
Fractional VariableScalingFactor(ColIndex col) const
Fractional UnscaleVariableValue(ColIndex col, Fractional value) const
Fractional UnscaleReducedCost(ColIndex col, Fractional value) const
void UnscaleUnitRowLeftSolve(ColIndex basis_col, ScatteredRow *left_inverse) const
void UnscaleColumnRightSolve(const RowToColMapping &basis, ColIndex col, ScatteredColumn *right_inverse) const
Fractional UnscaleDualValue(RowIndex row, Fractional value) const
Fractional UnscaleConstraintActivity(RowIndex row, Fractional value) 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
int64 value
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
void Scale(LinearProgram *lp, SparseMatrixScaler *scaler, GlopParameters::ScalingAlgorithm scaling_method)
const ColIndex kInvalidCol(-1)
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
void ComputeSlackVariablesValues(const LinearProgram &linear_program, DenseRow *values)
void Scale(LinearProgram *lp, SparseMatrixScaler *scaler)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
StrictITIVector< Index, Fractional > values