OR-Tools  8.1
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 
19 namespace operations_research {
20 namespace 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
operations_research::glop::ScatteredVector::ClearSparseMask
void ClearSparseMask()
Definition: scattered_vector.h:133
operations_research::glop::VariableStatus::AT_UPPER_BOUND
@ AT_UPPER_BOUND
operations_research::glop::CompactSparseMatrix
Definition: sparse.h:288
operations_research::glop::StrictITIVector::resize
void resize(IntType size)
Definition: lp_types.h:269
operations_research::glop::VariableStatus::BASIC
@ BASIC
operations_research::glop::VariablesInfo::GetNotBasicBitRow
const DenseBitRow & GetNotBasicBitRow() const
Definition: variables_info.cc:119
operations_research::glop::VariableValues::RecomputeBasicVariableValues
void RecomputeBasicVariableValues()
Definition: variable_values.cc:92
max
int64 max
Definition: alldiff_cst.cc:139
operations_research::glop::VariableValues::ResetPrimalInfeasibilityInformation
void ResetPrimalInfeasibilityInformation()
Definition: variable_values.cc:226
LOG
#define LOG(severity)
Definition: base/logging.h:420
operations_research::glop::VariableValues::UpdateGivenNonBasicVariables
void UpdateGivenNonBasicVariables(const std::vector< ColIndex > &cols_to_update, bool update_basic_variables)
Definition: variable_values.cc:167
operations_research::glop::CompactSparseMatrix::ColumnAddMultipleToDenseColumn
void ColumnAddMultipleToDenseColumn(ColIndex col, Fractional multiplier, DenseColumn *dense_column) const
Definition: sparse.h:393
operations_research::glop::VariableValues::ComputeSumOfPrimalInfeasibilities
Fractional ComputeSumOfPrimalInfeasibilities() const
Definition: variable_values.cc:132
operations_research::glop::ScatteredVector::non_zeros
std::vector< Index > non_zeros
Definition: scattered_vector.h:63
operations_research::glop::VariableValues::UpdatePrimalInfeasibilityInformation
void UpdatePrimalInfeasibilityInformation(const std::vector< RowIndex > &rows)
Definition: variable_values.cc:244
value
int64 value
Definition: demon_profiler.cc:43
operations_research::glop::CompactSparseMatrix::num_rows
RowIndex num_rows() const
Definition: sparse.h:344
lp_utils.h
operations_research::glop::InfinityNorm
Fractional InfinityNorm(const DenseColumn &v)
Definition: lp_data/lp_utils.cc:81
operations_research::glop::VariableValues::ResetAllNonBasicVariableValues
void ResetAllNonBasicVariableValues()
Definition: variable_values.cc:67
operations_research::glop::StrictITIVector::size
IntType size() const
Definition: lp_types.h:276
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::glop::VariablesInfo::GetVariableUpperBounds
const DenseRow & GetVariableUpperBounds() const
Definition: variables_info.h:63
operations_research::glop::ScatteredVector::ShouldUseDenseIteration
bool ShouldUseDenseIteration(double ratio_for_using_dense_representation) const
Definition: scattered_vector.h:120
operations_research::glop::CompactSparseMatrix::num_cols
ColIndex num_cols() const
Definition: sparse.h:345
operations_research::Bitset64< RowIndex >
operations_research::glop::BasisFactorization::IsRefactorized
bool IsRefactorized() const
Definition: basis_representation.cc:214
operations_research::glop::VariablesInfo::GetStatusRow
const VariableStatusRow & GetStatusRow() const
Definition: variables_info.cc:101
operations_research::glop::Fractional
double Fractional
Definition: lp_types.h:77
DCHECK_NE
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
operations_research::glop::VariableStatus::FIXED_VALUE
@ FIXED_VALUE
SCOPED_TIME_STAT
#define SCOPED_TIME_STAT(stats)
Definition: stats.h:436
operations_research::glop::VariablesInfo::GetVariableLowerBounds
const DenseRow & GetVariableLowerBounds() const
Definition: variables_info.h:62
operations_research::glop::kInfinity
const double kInfinity
Definition: lp_types.h:83
operations_research::glop::IsFinite
bool IsFinite(Fractional value)
Definition: lp_types.h:90
operations_research::glop::BasisFactorization
Definition: basis_representation.h:151
operations_research::Bitset64::Clear
void Clear(IndexType i)
Definition: bitset.h:455
operations_research::glop::VariableValues::ComputeMaximumPrimalResidual
Fractional ComputeMaximumPrimalResidual() const
Definition: variable_values.cc:108
operations_research::glop::StrictITIVector< RowIndex, ColIndex >
operations_research::glop::StrictITIVector::AssignToZero
void AssignToZero(IntType size)
Definition: lp_types.h:290
operations_research::glop::VariableValues::SetNonBasicVariableValueFromStatus
void SetNonBasicVariableValueFromStatus(ColIndex col)
Definition: variable_values.cc:34
operations_research::glop::VariableValues::VariableValues
VariableValues(const GlopParameters &parameters, const CompactSparseMatrix &matrix, const RowToColMapping &basis, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization)
Definition: variable_values.cc:22
operations_research::glop::VariablesInfo
Definition: variables_info.h:29
operations_research::glop::BasisFactorization::RightSolve
void RightSolve(ScatteredColumn *d) const
Definition: basis_representation.cc:322
operations_research::glop::ScatteredVector::ClearNonZerosIfTooDense
void ClearNonZerosIfTooDense(double ratio_for_using_dense_representation)
Definition: scattered_vector.h:153
DCHECK
#define DCHECK(condition)
Definition: base/logging.h:884
operations_research::glop::VariableValues::UpdateOnPivoting
void UpdateOnPivoting(const ScatteredColumn &direction, ColIndex entering_col, Fractional step)
Definition: variable_values.cc:144
operations_research::Bitset64::Set
void Set(IndexType i)
Definition: bitset.h:493
operations_research::glop::VariableValues::GetPrimalInfeasiblePositions
const DenseBitColumn & GetPrimalInfeasiblePositions() const
Definition: variable_values.cc:222
col
ColIndex col
Definition: markowitz.cc:176
row
RowIndex row
Definition: markowitz.cc:175
iterators.h
operations_research::glop::Square
Fractional Square(Fractional f)
Definition: lp_data/lp_utils.h:36
operations_research::glop::ScatteredColumn
Definition: scattered_vector.h:192
lower_bounds
std::vector< double > lower_bounds
Definition: sat/lp_utils.cc:498
operations_research::glop::CompactSparseMatrix::ColumnAddMultipleToSparseScatteredColumn
void ColumnAddMultipleToSparseScatteredColumn(ColIndex col, Fractional multiplier, ScatteredColumn *column) const
Definition: sparse.h:405
DCHECK_EQ
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
operations_research::glop::VariableValues::GetPrimalSquaredInfeasibilities
const DenseColumn & GetPrimalSquaredInfeasibilities() const
Definition: variable_values.cc:218
variable_values.h
operations_research::glop::VariableValues::ComputeMaximumPrimalInfeasibility
Fractional ComputeMaximumPrimalInfeasibility() const
Definition: variable_values.cc:120
operations_research::glop::IsAllZero
bool IsAllZero(const Container &input)
Definition: lp_data/lp_utils.h:222
operations_research::glop::VariableStatus::FREE
@ FREE
upper_bounds
std::vector< double > upper_bounds
Definition: sat/lp_utils.cc:499
operations_research::Bitset64::ClearAndResize
void ClearAndResize(IndexType size)
Definition: bitset.h:438
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
operations_research::glop::ScatteredVector::values
StrictITIVector< Index, Fractional > values
Definition: scattered_vector.h:58
operations_research::glop::VariableStatus::AT_LOWER_BOUND
@ AT_LOWER_BOUND