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 
16 namespace operations_research {
17 namespace glop {
18 
19 void 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 
76 void LpScalingHelper::Scale(LinearProgram* lp) { Scale(GlopParameters(), lp); }
77 
78 void 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
const DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method)
Definition: lp_data.cc:1186
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
void Scale(LinearProgram *lp, SparseMatrixScaler *scaler, GlopParameters::ScalingAlgorithm scaling_method)
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
RowIndex ColToRowIndex(ColIndex col)
Definition: lp_types.h:51
void ComputeSlackVariablesValues(const LinearProgram &linear_program, DenseRow *values)
void Scale(LinearProgram *lp, SparseMatrixScaler *scaler)
const ColIndex kInvalidCol(-1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
StrictITIVector< Index, Fractional > values