OR-Tools  8.2
theta_tree.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#include <algorithm>
17#include <memory>
18
20
21namespace operations_research {
22namespace sat {
23
24template <typename IntegerType>
26
27template <typename IntegerType>
29ThetaLambdaTree<IntegerType>::ComposeTreeNodes(TreeNode left, TreeNode right) {
30 return {std::max(right.envelope, left.envelope + right.sum_of_energy_min),
31 std::max(right.envelope_opt,
32 right.sum_of_energy_min +
33 std::max(left.envelope_opt,
34 left.envelope + right.max_of_energy_delta)),
35 left.sum_of_energy_min + right.sum_of_energy_min,
36 std::max(right.max_of_energy_delta, left.max_of_energy_delta)};
37}
38
39template <typename IntegerType>
41#ifndef NDEBUG
42 leaf_nodes_have_delayed_operations_ = false;
43#endif
44 // Because the algorithm needs to access a node sibling (i.e. node_index ^ 1),
45 // our tree will always have an even number of leaves, just large enough to
46 // fit our number of events. And at least 2 for the empty tree case.
47 num_events_ = num_events;
48 num_leaves_ = std::max(2, num_events + (num_events & 1));
49
50 const int num_nodes = 2 * num_leaves_;
51 tree_.assign(num_nodes, TreeNode{IntegerTypeMinimumValue<IntegerType>(),
52 IntegerTypeMinimumValue<IntegerType>(),
53 IntegerType{0}, IntegerType{0}});
54
55 // If num_leaves is not a power or two, the last depth of the tree will not be
56 // full, and the array will look like:
57 // [( num_leafs parents)(leaves at depth d - 1)(leaves at depth d)
58 // The first leaves at depth p will have power_of_two_ as index.
59 for (power_of_two_ = 2; power_of_two_ < num_leaves_; power_of_two_ <<= 1) {
60 }
61}
62
63template <typename IntegerType>
65 DCHECK_LE(0, event);
66 DCHECK_LT(event, num_events_);
67 // Keeping the ordering of events is important, so the first set of events
68 // must be mapped to the set of leaves at depth d, and the second set of
69 // events must be mapped to the set of leaves at depth d-1.
70 const int r = power_of_two_ + event;
71 return r < 2 * num_leaves_ ? r : r - num_leaves_;
72}
73
74template <typename IntegerType>
75int ThetaLambdaTree<IntegerType>::GetEventFromLeaf(int leaf) const {
76 DCHECK_GE(leaf, num_leaves_);
77 DCHECK_LT(leaf, 2 * num_leaves_);
78 const int r = leaf - power_of_two_;
79 return r >= 0 ? r : r + num_leaves_;
80}
81
82template <typename IntegerType>
84#ifndef NDEBUG
85 leaf_nodes_have_delayed_operations_ = false;
86#endif
87 // Only recompute internal nodes.
88 const int last_internal_node = tree_.size() / 2 - 1;
89 for (int node = last_internal_node; node >= 1; --node) {
90 const int right = 2 * node + 1;
91 const int left = 2 * node;
92 tree_[node] = ComposeTreeNodes(tree_[left], tree_[right]);
93 }
94}
95
96template <typename IntegerType>
98 int event, IntegerType initial_envelope, IntegerType energy_min,
99 IntegerType energy_max) {
100#ifndef NDEBUG
101 leaf_nodes_have_delayed_operations_ = true;
102#endif
103 DCHECK_LE(0, energy_min);
104 DCHECK_LE(energy_min, energy_max);
105 const int node = GetLeafFromEvent(event);
106 tree_[node] = {initial_envelope + energy_min, initial_envelope + energy_max,
107 energy_min, energy_max - energy_min};
108}
109
110template <typename IntegerType>
112 int event, IntegerType initial_envelope, IntegerType energy_min,
113 IntegerType energy_max) {
114 DCHECK(!leaf_nodes_have_delayed_operations_);
115 DCHECK_LE(0, energy_min);
116 DCHECK_LE(energy_min, energy_max);
117 const int node = GetLeafFromEvent(event);
118 tree_[node] = {initial_envelope + energy_min, initial_envelope + energy_max,
119 energy_min, energy_max - energy_min};
120 RefreshNode(node);
121}
123template <typename IntegerType>
125 int event, IntegerType initial_envelope_opt, IntegerType energy_max) {
126 DCHECK(!leaf_nodes_have_delayed_operations_);
127 DCHECK_LE(0, energy_max);
128 const int node = GetLeafFromEvent(event);
129 tree_[node] = {IntegerTypeMinimumValue<IntegerType>(),
130 initial_envelope_opt + energy_max, IntegerType{0}, energy_max};
131 RefreshNode(node);
133
134template <typename IntegerType>
136 int event, IntegerType initial_envelope_opt, IntegerType energy_max) {
137#ifndef NDEBUG
138 leaf_nodes_have_delayed_operations_ = true;
139#endif
140 DCHECK_LE(0, energy_max);
141 const int node = GetLeafFromEvent(event);
142 tree_[node] = {IntegerTypeMinimumValue<IntegerType>(),
143 initial_envelope_opt + energy_max, IntegerType{0}, energy_max};
144}
146template <typename IntegerType>
148 DCHECK(!leaf_nodes_have_delayed_operations_);
149 const int node = GetLeafFromEvent(event);
150 tree_[node] = {IntegerTypeMinimumValue<IntegerType>(),
151 IntegerTypeMinimumValue<IntegerType>(), IntegerType{0},
152 IntegerType{0}};
153 RefreshNode(node);
154}
155
156template <typename IntegerType>
158#ifndef NDEBUG
159 leaf_nodes_have_delayed_operations_ = true;
160#endif
161 const int node = GetLeafFromEvent(event);
162 tree_[node] = {IntegerTypeMinimumValue<IntegerType>(),
163 IntegerTypeMinimumValue<IntegerType>(), IntegerType{0},
164 IntegerType{0}};
165}
166
167template <typename IntegerType>
169 DCHECK(!leaf_nodes_have_delayed_operations_);
170 return tree_[1].envelope;
171}
172template <typename IntegerType>
174 DCHECK(!leaf_nodes_have_delayed_operations_);
175 return tree_[1].envelope_opt;
176}
177
178template <typename IntegerType>
180 IntegerType target_envelope) const {
181 DCHECK(!leaf_nodes_have_delayed_operations_);
182 DCHECK_LT(target_envelope, tree_[1].envelope);
183 IntegerType unused;
184 return GetEventFromLeaf(
185 GetMaxLeafWithEnvelopeGreaterThan(1, target_envelope, &unused));
186}
187
188template <typename IntegerType>
190 IntegerType target_envelope, int* critical_event, int* optional_event,
191 IntegerType* available_energy) const {
192 DCHECK(!leaf_nodes_have_delayed_operations_);
193 int critical_leaf;
194 int optional_leaf;
195 GetLeavesWithOptionalEnvelopeGreaterThan(target_envelope, &critical_leaf,
196 &optional_leaf, available_energy);
197 *critical_event = GetEventFromLeaf(critical_leaf);
198 *optional_event = GetEventFromLeaf(optional_leaf);
199}
200
201template <typename IntegerType>
203 DCHECK(!leaf_nodes_have_delayed_operations_);
204 const int leaf = GetLeafFromEvent(event);
205 IntegerType envelope = tree_[leaf].envelope;
206 for (int node = leaf; node > 1; node >>= 1) {
207 const int right = node | 1;
208 if (node != right) envelope += tree_[right].sum_of_energy_min;
209 }
210 return envelope;
211}
212
213template <typename IntegerType>
215 do {
216 const int right = node | 1;
217 const int left = right ^ 1;
218 node >>= 1;
219 tree_[node] = ComposeTreeNodes(tree_[left], tree_[right]);
220 } while (node > 1);
221}
222
223template <typename IntegerType>
224int ThetaLambdaTree<IntegerType>::GetMaxLeafWithEnvelopeGreaterThan(
225 int node, IntegerType target_envelope, IntegerType* extra) const {
226 DCHECK(!leaf_nodes_have_delayed_operations_);
227 DCHECK_LT(target_envelope, tree_[node].envelope);
228 while (node < num_leaves_) {
229 const int left = node << 1;
230 const int right = left | 1;
231 DCHECK_LT(right, tree_.size());
232
233 if (target_envelope < tree_[right].envelope) {
234 node = right;
235 } else {
236 target_envelope -= tree_[right].sum_of_energy_min;
237 node = left;
238 }
239 }
240 *extra = tree_[node].envelope - target_envelope;
241 return node;
242}
243
244template <typename IntegerType>
245int ThetaLambdaTree<IntegerType>::GetLeafWithMaxEnergyDelta(int node) const {
246 DCHECK(!leaf_nodes_have_delayed_operations_);
247 const IntegerType delta_node = tree_[node].max_of_energy_delta;
248 while (node < num_leaves_) {
249 const int left = node << 1;
250 const int right = left | 1;
251 DCHECK_LT(right, tree_.size());
252 if (tree_[right].max_of_energy_delta == delta_node) {
253 node = right;
254 } else {
255 DCHECK_EQ(tree_[left].max_of_energy_delta, delta_node);
256 node = left;
257 }
258 }
259 return node;
260}
261
262template <typename IntegerType>
263void ThetaLambdaTree<IntegerType>::GetLeavesWithOptionalEnvelopeGreaterThan(
264 IntegerType target_envelope, int* critical_leaf, int* optional_leaf,
265 IntegerType* available_energy) const {
266 DCHECK(!leaf_nodes_have_delayed_operations_);
267 DCHECK_LT(target_envelope, tree_[1].envelope_opt);
268 int node = 1;
269 while (node < num_leaves_) {
270 const int left = node << 1;
271 const int right = left | 1;
272 DCHECK_LT(right, tree_.size());
273
274 if (target_envelope < tree_[right].envelope_opt) {
275 node = right;
276 } else {
277 const IntegerType opt_energy_right =
278 tree_[right].sum_of_energy_min + tree_[right].max_of_energy_delta;
279 if (target_envelope < tree_[left].envelope + opt_energy_right) {
280 *optional_leaf = GetLeafWithMaxEnergyDelta(right);
281 IntegerType extra;
282 *critical_leaf = GetMaxLeafWithEnvelopeGreaterThan(
283 left, target_envelope - opt_energy_right, &extra);
284 *available_energy = tree_[*optional_leaf].sum_of_energy_min +
285 tree_[*optional_leaf].max_of_energy_delta - extra;
286 return;
287 } else { // < tree_[left].envelope_opt + tree_[right].sum_of_energy_min
288 target_envelope -= tree_[right].sum_of_energy_min;
289 node = left;
290 }
291 }
292 }
293 *critical_leaf = node;
294 *optional_leaf = node;
295 *available_energy = target_envelope - (tree_[node].envelope_opt -
296 tree_[node].sum_of_energy_min -
297 tree_[node].max_of_energy_delta);
298}
299
300template class ThetaLambdaTree<IntegerValue>;
301template class ThetaLambdaTree<int64>;
302
303} // namespace sat
304} // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
IntegerType GetEnvelopeOf(int event) const
Definition: theta_tree.cc:202
void GetEventsWithOptionalEnvelopeGreaterThan(IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const
Definition: theta_tree.cc:189
int GetMaxEventWithEnvelopeGreaterThan(IntegerType target_envelope) const
Definition: theta_tree.cc:179
void AddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt, IntegerType energy_max)
Definition: theta_tree.cc:124
void DelayedAddOrUpdateEvent(int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
Definition: theta_tree.cc:97
void DelayedAddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt, IntegerType energy_max)
Definition: theta_tree.cc:135
void AddOrUpdateEvent(int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
Definition: theta_tree.cc:111
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...