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
25namespace operations_research {
26namespace 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().
36void 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.
41void 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.
46void 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...