OR-Tools  8.2
lp_data_utils.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 // Utility helpers for manipulating LinearProgram and other types defined in
15 // lp_data.
16 
17 #ifndef OR_TOOLS_LP_DATA_LP_DATA_UTILS_H_
18 #define OR_TOOLS_LP_DATA_LP_DATA_UTILS_H_
19 
20 #include "ortools/glop/parameters.pb.h"
24 
25 namespace operations_research {
26 namespace glop {
27 
28 // For all constraints in linear_program, if the constraint has a slack
29 // variable, change its value in *values so that the constraints itself is
30 // satisfied.
31 // Note that this obviously won't always imply that the bounds of the slack
32 // variable itself will be satisfied.
33 // The code assumes (and DCHECKs) that all constraints with a slack variable
34 // have their upper and lower bounds both set to 0. This is ensured by
35 // LinearProgram::AddSlackVariablesWhereNecessary().
36 void ComputeSlackVariablesValues(const LinearProgram& linear_program,
37  DenseRow* values);
38 
39 // This is separated from LinearProgram class because of a cyclic dependency
40 // when scaling as an LP.
41 void Scale(LinearProgram* lp, SparseMatrixScaler* scaler,
42  GlopParameters::ScalingAlgorithm scaling_method);
43 
44 // A convenience method for above providing a default algorithm for callers that
45 // don't specify one.
46 void Scale(LinearProgram* lp, SparseMatrixScaler* scaler);
47 
48 // Class to facilitate the conversion between an original "unscaled" LP problem
49 // and its scaled version. It is easy to get the direction wrong, so it make
50 // sense to have a single place where all the scaling formulas are kept.
52  public:
53  // Scale the given LP.
54  void Scale(LinearProgram* lp);
55  void Scale(const GlopParameters& params, LinearProgram* lp);
56 
57  // Clear all scaling coefficients.
58  void Clear();
59 
60  // A variable value in the original domain must be multiplied by this factor
61  // to be in the scaled domain.
62  Fractional VariableScalingFactor(ColIndex col) const;
63 
64  // Transforms corresponding value from the scaled domain to the original one.
69 
70  // Unscale a row vector v such that v.B = unit_row. When basis_col is the
71  // index of the Column that correspond to the unit position in matrix B.
72  void UnscaleUnitRowLeftSolve(ColIndex basis_col,
73  ScatteredRow* left_inverse) const;
74 
75  // Unscale a col vector v such that B.c = matrix_column_col.
76  void UnscaleColumnRightSolve(const RowToColMapping& basis, ColIndex col,
77  ScatteredColumn* right_inverse) const;
78 
79  // Visible for testing. All objective coefficients of the original LP where
80  // multiplied by this factor. Nothing else changed.
81  Fractional BoundsScalingFactor() const { return bound_scaling_factor_; }
82 
83  // Visible for testing. All variable/constraint bounds of the original LP
84  // where multiplied by this factor. Nothing else changed.
86  return objective_scaling_factor_;
87  }
88 
89  private:
90  SparseMatrixScaler scaler_;
91  Fractional bound_scaling_factor_ = 1.0;
92  Fractional objective_scaling_factor_ = 1.0;
93 };
94 
95 } // namespace glop
96 } // namespace operations_research
97 
98 #endif // OR_TOOLS_LP_DATA_LP_DATA_UTILS_H_
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
int64 value
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
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...