OR-Tools  8.1
variables_info.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 
16 namespace operations_research {
17 namespace glop {
18 
20  const DenseRow& lower_bound,
21  const DenseRow& upper_bound)
22  : matrix_(matrix),
23  lower_bound_(lower_bound),
24  upper_bound_(upper_bound),
25  boxed_variables_are_relevant_(true) {}
26 
28  const ColIndex num_cols = matrix_.num_cols();
29  can_increase_.ClearAndResize(num_cols);
30  can_decrease_.ClearAndResize(num_cols);
31  is_basic_.ClearAndResize(num_cols);
32  not_basic_.ClearAndResize(num_cols);
33  non_basic_boxed_variables_.ClearAndResize(num_cols);
34 
35  num_entries_in_relevant_columns_ = 0;
36  boxed_variables_are_relevant_ = true;
37  relevance_.ClearAndResize(num_cols);
38 
39  variable_status_.resize(num_cols, VariableStatus::FREE);
40  variable_type_.resize(num_cols, VariableType::UNCONSTRAINED);
41  for (ColIndex col(0); col < num_cols; ++col) {
42  variable_type_[col] = ComputeVariableType(col);
43  }
44 }
45 
47  if (value == boxed_variables_are_relevant_) return;
48  boxed_variables_are_relevant_ = value;
49  if (value) {
50  for (const ColIndex col : non_basic_boxed_variables_) {
51  SetRelevance(col, variable_type_[col] != VariableType::FIXED_VARIABLE);
52  }
53  } else {
54  for (const ColIndex col : non_basic_boxed_variables_) {
55  SetRelevance(col, false);
56  }
57  }
58 }
59 
60 void VariablesInfo::Update(ColIndex col, VariableStatus status) {
61  if (status == VariableStatus::BASIC) {
63  } else {
64  UpdateToNonBasicStatus(col, status);
65  }
66 }
67 
69  variable_status_[col] = VariableStatus::BASIC;
70  is_basic_.Set(col, true);
71  not_basic_.Set(col, false);
72  can_increase_.Set(col, false);
73  can_decrease_.Set(col, false);
74  non_basic_boxed_variables_.Set(col, false);
75  SetRelevance(col, false);
76 }
77 
79  VariableStatus status) {
81  variable_status_[col] = status;
82  is_basic_.Set(col, false);
83  not_basic_.Set(col, true);
84  can_increase_.Set(col, status == VariableStatus::AT_LOWER_BOUND ||
85  status == VariableStatus::FREE);
86  can_decrease_.Set(col, status == VariableStatus::AT_UPPER_BOUND ||
87  status == VariableStatus::FREE);
88 
89  const bool boxed =
90  variable_type_[col] == VariableType::UPPER_AND_LOWER_BOUNDED;
91  non_basic_boxed_variables_.Set(col, boxed);
92  const bool relevance = status != VariableStatus::FIXED_VALUE &&
93  (boxed_variables_are_relevant_ || !boxed);
94  SetRelevance(col, relevance);
95 }
96 
98  return variable_type_;
99 }
100 
102  return variable_status_;
103 }
104 
106  return can_increase_;
107 }
108 
110  return can_decrease_;
111 }
112 
114  return relevance_;
115 }
116 
117 const DenseBitRow& VariablesInfo::GetIsBasicBitRow() const { return is_basic_; }
118 
120  return not_basic_;
121 }
122 
124  return non_basic_boxed_variables_;
125 }
126 
128  return num_entries_in_relevant_columns_;
129 }
130 
131 VariableType VariablesInfo::ComputeVariableType(ColIndex col) const {
132  DCHECK_LE(lower_bound_[col], upper_bound_[col]);
133  if (lower_bound_[col] == -kInfinity) {
134  if (upper_bound_[col] == kInfinity) {
135  return VariableType::UNCONSTRAINED;
136  }
137  return VariableType::UPPER_BOUNDED;
138  } else if (upper_bound_[col] == kInfinity) {
139  return VariableType::LOWER_BOUNDED;
140  } else if (lower_bound_[col] == upper_bound_[col]) {
142  } else {
143  return VariableType::UPPER_AND_LOWER_BOUNDED;
144  }
145 }
146 
147 void VariablesInfo::SetRelevance(ColIndex col, bool relevance) {
148  if (relevance_.IsSet(col) == relevance) return;
149  if (relevance) {
150  relevance_.Set(col);
151  num_entries_in_relevant_columns_ += matrix_.ColumnNumEntries(col);
152  } else {
153  relevance_.Clear(col);
154  num_entries_in_relevant_columns_ -= matrix_.ColumnNumEntries(col);
155  }
156 }
157 
158 } // namespace glop
159 } // namespace operations_research
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::Bitset64::IsSet
bool IsSet(IndexType i) const
Definition: bitset.h:483
operations_research::glop::VariablesInfo::GetNotBasicBitRow
const DenseBitRow & GetNotBasicBitRow() const
Definition: variables_info.cc:119
operations_research::glop::VariablesInfo::VariablesInfo
VariablesInfo(const CompactSparseMatrix &matrix, const DenseRow &lower_bound, const DenseRow &upper_bound)
Definition: variables_info.cc:19
operations_research::glop::VariablesInfo::UpdateToBasicStatus
void UpdateToBasicStatus(ColIndex col)
Definition: variables_info.cc:68
operations_research::glop::VariablesInfo::MakeBoxedVariableRelevant
void MakeBoxedVariableRelevant(bool value)
Definition: variables_info.cc:46
value
int64 value
Definition: demon_profiler.cc:43
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::CompactSparseMatrix::num_cols
ColIndex num_cols() const
Definition: sparse.h:345
operations_research::Bitset64< ColIndex >
operations_research::glop::VariablesInfo::GetStatusRow
const VariableStatusRow & GetStatusRow() const
Definition: variables_info.cc:101
operations_research::glop::VariablesInfo::GetNumEntriesInRelevantColumns
EntryIndex GetNumEntriesInRelevantColumns() const
Definition: variables_info.cc:127
DCHECK_NE
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
operations_research::glop::VariableStatus::FIXED_VALUE
@ FIXED_VALUE
operations_research::glop::kInfinity
const double kInfinity
Definition: lp_types.h:83
operations_research::glop::VariablesInfo::GetCanIncreaseBitRow
const DenseBitRow & GetCanIncreaseBitRow() const
Definition: variables_info.cc:105
operations_research::Bitset64::Clear
void Clear(IndexType i)
Definition: bitset.h:455
operations_research::glop::VariablesInfo::InitializeAndComputeType
void InitializeAndComputeType()
Definition: variables_info.cc:27
operations_research::glop::StrictITIVector< ColIndex, Fractional >
operations_research::glop::VariableType::FIXED_VARIABLE
@ FIXED_VARIABLE
operations_research::glop::VariablesInfo::GetCanDecreaseBitRow
const DenseBitRow & GetCanDecreaseBitRow() const
Definition: variables_info.cc:109
operations_research::glop::CompactSparseMatrix::ColumnNumEntries
EntryIndex ColumnNumEntries(ColIndex col) const
Definition: sparse.h:335
operations_research::glop::VariablesInfo::GetIsBasicBitRow
const DenseBitRow & GetIsBasicBitRow() const
Definition: variables_info.cc:117
operations_research::glop::VariablesInfo::GetIsRelevantBitRow
const DenseBitRow & GetIsRelevantBitRow() const
Definition: variables_info.cc:113
operations_research::Bitset64::Set
void Set(IndexType i)
Definition: bitset.h:493
col
ColIndex col
Definition: markowitz.cc:176
operations_research::glop::VariablesInfo::UpdateToNonBasicStatus
void UpdateToNonBasicStatus(ColIndex col, VariableStatus status)
Definition: variables_info.cc:78
operations_research::glop::VariablesInfo::GetNonBasicBoxedVariables
const DenseBitRow & GetNonBasicBoxedVariables() const
Definition: variables_info.cc:123
operations_research::glop::VariablesInfo::GetTypeRow
const VariableTypeRow & GetTypeRow() const
Definition: variables_info.cc:97
operations_research::glop::VariableType
VariableType
Definition: lp_types.h:174
operations_research::glop::VariableStatus
VariableStatus
Definition: lp_types.h:196
variables_info.h
operations_research::glop::VariableStatus::FREE
@ FREE
DCHECK_LE
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
operations_research::Bitset64::ClearAndResize
void ClearAndResize(IndexType size)
Definition: bitset.h:438
operations_research::glop::VariablesInfo::Update
void Update(ColIndex col, VariableStatus status)
Definition: variables_info.cc:60
operations_research::glop::VariableStatus::AT_LOWER_BOUND
@ AT_LOWER_BOUND