OR-Tools  8.2
variable_values.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#ifndef OR_TOOLS_GLOP_VARIABLE_VALUES_H_
15#define OR_TOOLS_GLOP_VARIABLE_VALUES_H_
16
21#include "ortools/util/stats.h"
22
23namespace operations_research {
24namespace glop {
25
26// Class holding all the variable values and responsible for updating them. The
27// variable values 'x' are such that 'A.x = 0' where A is the linear program
28// matrix. This is because slack variables with bounds corresponding to the
29// constraints bounds were added to the linear program matrix A.
30//
31// Some remarks:
32// - For convenience, the variable values are stored in a DenseRow and indexed
33// by ColIndex, like the variables and the columns of A.
34// - During the dual-simplex, all non-basic variable values are at their exact
35// bounds or exactly at 0.0 for a free variable.
36// - During the primal-simplex, the non-basic variable values may not be exactly
37// at their bounds because of bound-shifting during degenerate simplex
38// pivoting which is implemented by not setting the variable values exactly at
39// their bounds to have a lower primal residual error.
41 public:
42 VariableValues(const GlopParameters& parameters,
43 const CompactSparseMatrix& matrix,
44 const RowToColMapping& basis,
45 const VariablesInfo& variables_info,
46 const BasisFactorization& basis_factorization);
47
48 // Getters for the variable values.
49 const Fractional Get(ColIndex col) const { return variable_values_[col]; }
50 const DenseRow& GetDenseRow() const { return variable_values_; }
51
52 // Sets the value of a non-basic variable to the exact value implied by its
53 // current status. Note that the basic variable values are NOT updated by this
54 // function and it is up to the client to call RecomputeBasicVariableValues().
56
57 // Calls SetNonBasicVariableValueFromStatus() on all non-basic variables.
59
60 // Recomputes the value of the basic variables from the non-basic ones knowing
61 // that the linear program matrix A times the variable values vector must be
62 // zero. It is better to call this when the basis is refactorized. This
63 // is checked in debug mode.
65
66 // Computes the infinity norm of A.x where A is the linear_program matrix and
67 // x is the variable values column.
69
70 // Computes the maximum bound error for all the variables, defined as the
71 // distance of the current value of the variable to its interval
72 // [lower bound, upper bound]. The infeasibility is thus equal to 0.0 if the
73 // current value falls within the bounds, to the distance to lower_bound
74 // (resp. upper_bound), if the current value is below (resp. above)
75 // lower_bound (resp. upper_bound).
78
79 // Updates the variable during a simplex pivot:
80 // - step * direction is substracted from the basic variables value.
81 // - step is added to the entering column value.
82 void UpdateOnPivoting(const ScatteredColumn& direction, ColIndex entering_col,
83 Fractional step);
84
85 // Batch version of SetNonBasicVariableValueFromStatus(). This function also
86 // updates the basic variable values and infeasibility statuses if
87 // update_basic_variables is true. The update is done in an incremental way
88 // and is thus more efficient than calling afterwards
89 // RecomputeBasicVariableValues() and ResetPrimalInfeasibilityInformation().
90 void UpdateGivenNonBasicVariables(const std::vector<ColIndex>& cols_to_update,
91 bool update_basic_variables);
92
93 // Functions dealing with the primal-infeasible basic variables. A basic
94 // variable is primal-infeasible if its infeasibility is stricly greater than
95 // the primal feasibility tolerance.
96 //
97 // This information is only available after a call to
98 // ResetPrimalInfeasibilityInformation() and has to be kept in sync by calling
99 // UpdatePrimalInfeasibilityInformation() for the rows that changed values.
103 void UpdatePrimalInfeasibilityInformation(const std::vector<RowIndex>& rows);
104
105 // The primal phase I objective is related to the primal infeasible
106 // information above. The cost of a basic column will be 1 if the variable is
107 // above its upper bound by strictly more than the primal tolerance, and -1 if
108 // it is lower than its lower bound by strictly less than the same tolerance.
109 //
110 // Returns true iff some cost changed.
111 template <typename Rows>
112 bool UpdatePrimalPhaseICosts(const Rows& rows, DenseRow* objective);
113
114 // Sets the variable value of a given column.
115 void Set(ColIndex col, Fractional value) { variable_values_[col] = value; }
116
117 // Parameters and stats functions.
118 std::string StatString() const { return stats_.StatString(); }
119
120 private:
121 // It is important that the infeasibility is always computed in the same
122 // way. So the code should always use these functions that returns a positive
123 // value when the variable is out of bounds.
124 Fractional GetUpperBoundInfeasibility(ColIndex col) const {
125 return variable_values_[col] -
126 variables_info_.GetVariableUpperBounds()[col];
127 }
128 Fractional GetLowerBoundInfeasibility(ColIndex col) const {
129 return variables_info_.GetVariableLowerBounds()[col] -
130 variable_values_[col];
131 }
132
133 // Input problem data.
134 const GlopParameters& parameters_;
135 const CompactSparseMatrix& matrix_;
136 const RowToColMapping& basis_;
137 const VariablesInfo& variables_info_;
138 const BasisFactorization& basis_factorization_;
139
140 // Values of the variables.
141 DenseRow variable_values_;
142
143 // Members used for the basic primal-infeasible variables.
144 DenseColumn primal_squared_infeasibilities_;
145 DenseBitColumn primal_infeasible_positions_;
146
147 mutable StatsGroup stats_;
148 mutable ScatteredColumn scratchpad_;
149
150 // A temporary scattered column that is always reset to all zero after use.
151 ScatteredColumn initially_all_zero_scratchpad_;
152
153 DISALLOW_COPY_AND_ASSIGN(VariableValues);
154};
155
156template <typename Rows>
158 DenseRow* objective) {
159 SCOPED_TIME_STAT(&stats_);
160 bool changed = false;
161 const Fractional tolerance = parameters_.primal_feasibility_tolerance();
162 for (const RowIndex row : rows) {
163 const ColIndex col = basis_[row];
164 Fractional new_cost = 0.0;
165 if (GetUpperBoundInfeasibility(col) > tolerance) {
166 new_cost = 1.0;
167 } else if (GetLowerBoundInfeasibility(col) > tolerance) {
168 new_cost = -1.0;
169 }
170 if (new_cost != (*objective)[col]) {
171 changed = true;
172 (*objective)[col] = new_cost;
173 }
174 }
175 return changed;
176}
177
178} // namespace glop
179} // namespace operations_research
180
181#endif // OR_TOOLS_GLOP_VARIABLE_VALUES_H_
std::string StatString() const
Definition: stats.cc:71
VariableValues(const GlopParameters &parameters, const CompactSparseMatrix &matrix, const RowToColMapping &basis, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization)
void Set(ColIndex col, Fractional value)
const DenseColumn & GetPrimalSquaredInfeasibilities() const
void UpdateGivenNonBasicVariables(const std::vector< ColIndex > &cols_to_update, bool update_basic_variables)
const DenseBitColumn & GetPrimalInfeasiblePositions() const
void UpdateOnPivoting(const ScatteredColumn &direction, ColIndex entering_col, Fractional step)
const Fractional Get(ColIndex col) const
void UpdatePrimalInfeasibilityInformation(const std::vector< RowIndex > &rows)
bool UpdatePrimalPhaseICosts(const Rows &rows, DenseRow *objective)
const DenseRow & GetVariableLowerBounds() const
const DenseRow & GetVariableUpperBounds() const
SatParameters parameters
int64 value
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
Bitset64< RowIndex > DenseBitColumn
Definition: lp_types.h:334
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
StrictITIVector< RowIndex, ColIndex > RowToColMapping
Definition: lp_types.h:342
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define SCOPED_TIME_STAT(stats)
Definition: stats.h:438