OR-Tools  8.2
variable_values.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
18
19namespace operations_research {
20namespace glop {
21
23 const CompactSparseMatrix& matrix,
24 const RowToColMapping& basis,
25 const VariablesInfo& variables_info,
26 const BasisFactorization& basis_factorization)
27 : parameters_(parameters),
28 matrix_(matrix),
29 basis_(basis),
30 variables_info_(variables_info),
31 basis_factorization_(basis_factorization),
32 stats_("VariableValues") {}
33
35 SCOPED_TIME_STAT(&stats_);
36 const DenseRow& lower_bounds = variables_info_.GetVariableLowerBounds();
37 const DenseRow& upper_bounds = variables_info_.GetVariableUpperBounds();
38 variable_values_.resize(matrix_.num_cols(), 0.0);
39 switch (variables_info_.GetStatusRow()[col]) {
43 variable_values_[col] = lower_bounds[col];
44 break;
47 variable_values_[col] = lower_bounds[col];
48 break;
51 variable_values_[col] = upper_bounds[col];
52 break;
56 variable_values_[col] = 0.0;
57 break;
59 LOG(DFATAL) << "SetNonBasicVariableValueFromStatus() shouldn't "
60 << "be called on a BASIC variable.";
61 break;
62 }
63 // Note that there is no default value in the switch() statement above to
64 // get a compile-time error if a value is missing.
65}
66
68 const DenseRow& lower_bounds = variables_info_.GetVariableLowerBounds();
69 const DenseRow& upper_bounds = variables_info_.GetVariableUpperBounds();
70 const VariableStatusRow& statuses = variables_info_.GetStatusRow();
71 const ColIndex num_cols = matrix_.num_cols();
72 variable_values_.resize(num_cols, 0.0);
73 for (ColIndex col(0); col < num_cols; ++col) {
74 switch (statuses[col]) {
76 ABSL_FALLTHROUGH_INTENDED;
78 variable_values_[col] = lower_bounds[col];
79 break;
81 variable_values_[col] = upper_bounds[col];
82 break;
84 variable_values_[col] = 0.0;
85 break;
87 break;
88 }
89 }
90}
91
93 SCOPED_TIME_STAT(&stats_);
94 DCHECK(basis_factorization_.IsRefactorized());
95 const RowIndex num_rows = matrix_.num_rows();
96 scratchpad_.non_zeros.clear();
97 scratchpad_.values.AssignToZero(num_rows);
98 for (const ColIndex col : variables_info_.GetNotBasicBitRow()) {
99 const Fractional value = variable_values_[col];
100 matrix_.ColumnAddMultipleToDenseColumn(col, -value, &scratchpad_.values);
101 }
102 basis_factorization_.RightSolve(&scratchpad_);
103 for (RowIndex row(0); row < num_rows; ++row) {
104 variable_values_[basis_[row]] = scratchpad_[row];
105 }
106}
107
109 SCOPED_TIME_STAT(&stats_);
110 scratchpad_.non_zeros.clear();
111 scratchpad_.values.AssignToZero(matrix_.num_rows());
112 const ColIndex num_cols = matrix_.num_cols();
113 for (ColIndex col(0); col < num_cols; ++col) {
114 const Fractional value = variable_values_[col];
115 matrix_.ColumnAddMultipleToDenseColumn(col, value, &scratchpad_.values);
116 }
117 return InfinityNorm(scratchpad_.values);
118}
119
121 SCOPED_TIME_STAT(&stats_);
122 Fractional primal_infeasibility = 0.0;
123 const ColIndex num_cols = matrix_.num_cols();
124 for (ColIndex col(0); col < num_cols; ++col) {
125 const Fractional col_infeasibility = std::max(
126 GetUpperBoundInfeasibility(col), GetLowerBoundInfeasibility(col));
127 primal_infeasibility = std::max(primal_infeasibility, col_infeasibility);
128 }
129 return primal_infeasibility;
130}
131
133 SCOPED_TIME_STAT(&stats_);
134 Fractional sum = 0.0;
135 const ColIndex num_cols = matrix_.num_cols();
136 for (ColIndex col(0); col < num_cols; ++col) {
137 const Fractional col_infeasibility = std::max(
138 GetUpperBoundInfeasibility(col), GetLowerBoundInfeasibility(col));
139 sum += std::max(0.0, col_infeasibility);
140 }
141 return sum;
142}
143
145 ColIndex entering_col, Fractional step) {
146 SCOPED_TIME_STAT(&stats_);
147 DCHECK(IsFinite(step));
148
149 // Note(user): Some positions are ignored during the primal ratio test:
150 // - The rows for which direction_[row] < tolerance.
151 // - The non-zeros of direction_ignored_position_ in case of degeneracy.
152 // Such positions may result in basic variables going out of their bounds by
153 // more than the allowed tolerance. We could choose not to update these
154 // variables or not make them take out-of-bound values, but this would
155 // introduce artificial errors.
156
157 // Note that there is no need to call variables_info_.Update() on basic
158 // variables when they change values. Note also that the status of
159 // entering_col will be updated later.
160 for (const auto e : direction) {
161 const ColIndex col = basis_[e.row()];
162 variable_values_[col] -= e.coefficient() * step;
163 }
164 variable_values_[entering_col] += step;
165}
166
168 const std::vector<ColIndex>& cols_to_update, bool update_basic_variables) {
169 SCOPED_TIME_STAT(&stats_);
170 if (!update_basic_variables) {
171 for (ColIndex col : cols_to_update) {
173 }
174 return;
175 }
176
177 const RowIndex num_rows = matrix_.num_rows();
178 initially_all_zero_scratchpad_.values.resize(num_rows, 0.0);
179 DCHECK(IsAllZero(initially_all_zero_scratchpad_.values));
180 initially_all_zero_scratchpad_.ClearSparseMask();
181 bool use_dense = false;
182 for (ColIndex col : cols_to_update) {
183 const Fractional old_value = variable_values_[col];
185 if (use_dense) {
187 col, variable_values_[col] - old_value,
188 &initially_all_zero_scratchpad_.values);
189 } else {
191 col, variable_values_[col] - old_value,
192 &initially_all_zero_scratchpad_);
193 use_dense = initially_all_zero_scratchpad_.ShouldUseDenseIteration();
194 }
195 }
196 initially_all_zero_scratchpad_.ClearSparseMask();
197 initially_all_zero_scratchpad_.ClearNonZerosIfTooDense();
198
199 basis_factorization_.RightSolve(&initially_all_zero_scratchpad_);
200 if (initially_all_zero_scratchpad_.non_zeros.empty()) {
201 for (RowIndex row(0); row < num_rows; ++row) {
202 variable_values_[basis_[row]] -= initially_all_zero_scratchpad_[row];
203 }
204 initially_all_zero_scratchpad_.values.AssignToZero(num_rows);
206 return;
207 }
208
209 for (const auto e : initially_all_zero_scratchpad_) {
210 variable_values_[basis_[e.row()]] -= e.coefficient();
211 initially_all_zero_scratchpad_[e.row()] = 0.0;
212 }
214 initially_all_zero_scratchpad_.non_zeros);
215 initially_all_zero_scratchpad_.non_zeros.clear();
216}
217
219 return primal_squared_infeasibilities_;
220}
221
223 return primal_infeasible_positions_;
224}
225
227 SCOPED_TIME_STAT(&stats_);
228 const RowIndex num_rows = matrix_.num_rows();
229 primal_squared_infeasibilities_.resize(num_rows, 0.0);
230 primal_infeasible_positions_.ClearAndResize(num_rows);
231
232 const Fractional tolerance = parameters_.primal_feasibility_tolerance();
233 for (RowIndex row(0); row < num_rows; ++row) {
234 const ColIndex col = basis_[row];
235 const Fractional infeasibility = std::max(GetUpperBoundInfeasibility(col),
236 GetLowerBoundInfeasibility(col));
237 if (infeasibility > tolerance) {
238 primal_squared_infeasibilities_[row] = Square(infeasibility);
239 primal_infeasible_positions_.Set(row);
240 }
241 }
242}
243
245 const std::vector<RowIndex>& rows) {
246 if (primal_squared_infeasibilities_.size() != matrix_.num_rows()) {
248 return;
249 }
250
251 // Note(user): this is the same as the code in
252 // ResetPrimalInfeasibilityInformation(), but we do need the clear part.
253 SCOPED_TIME_STAT(&stats_);
254 const Fractional tolerance = parameters_.primal_feasibility_tolerance();
255 for (const RowIndex row : rows) {
256 const ColIndex col = basis_[row];
257 const Fractional infeasibility = std::max(GetUpperBoundInfeasibility(col),
258 GetLowerBoundInfeasibility(col));
259 if (infeasibility > tolerance) {
260 primal_squared_infeasibilities_[row] = Square(infeasibility);
261 primal_infeasible_positions_.Set(row);
262 } else {
263 primal_infeasible_positions_.Clear(row);
264 }
265 }
266}
267
268} // namespace glop
269} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void ClearAndResize(IndexType size)
Definition: bitset.h:436
void Clear(IndexType i)
Definition: bitset.h:453
void Set(IndexType i)
Definition: bitset.h:491
void ColumnAddMultipleToSparseScatteredColumn(ColIndex col, Fractional multiplier, ScatteredColumn *column) const
Definition: sparse.h:405
void ColumnAddMultipleToDenseColumn(ColIndex col, Fractional multiplier, DenseColumn *dense_column) const
Definition: sparse.h:393
VariableValues(const GlopParameters &parameters, const CompactSparseMatrix &matrix, const RowToColMapping &basis, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization)
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)
void UpdatePrimalInfeasibilityInformation(const std::vector< RowIndex > &rows)
const DenseRow & GetVariableLowerBounds() const
const DenseBitRow & GetNotBasicBitRow() const
const VariableStatusRow & GetStatusRow() const
const DenseRow & GetVariableUpperBounds() const
SatParameters parameters
int64 value
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
bool IsFinite(Fractional value)
Definition: lp_types.h:90
Fractional InfinityNorm(const DenseColumn &v)
bool IsAllZero(const Container &input)
Fractional Square(Fractional f)
const double kInfinity
Definition: lp_types.h:83
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< double > lower_bounds
std::vector< double > upper_bounds
#define SCOPED_TIME_STAT(stats)
Definition: stats.h:438
bool ShouldUseDenseIteration(double ratio_for_using_dense_representation) const
void ClearNonZerosIfTooDense(double ratio_for_using_dense_representation)
StrictITIVector< Index, Fractional > values