OR-Tools  8.2
theta_tree.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_SAT_THETA_TREE_H_
15#define OR_TOOLS_SAT_THETA_TREE_H_
16
17#include <vector>
18
20#include "ortools/sat/integer.h"
21
22namespace operations_research {
23namespace sat {
24
25// The Theta-Lambda tree can be used to implement several scheduling algorithms.
26//
27// This template class is instantiated only for IntegerValue and int64.
28//
29// The tree structure itself is a binary tree coded in a vector, where node 0 is
30// unused, node 1 is the root, node 2 is the left child of the root, node 3 its
31// right child, etc.
32//
33// The API gives access to rightmost events that realize a given envelope.
34//
35// See:
36// _ (0) Petr Vilim's PhD thesis "Global Constraints in Scheduling".
37// _ (1) Petr Vilim "Edge Finding Filtering Algorithm for Discrete Cumulative
38// Resources in O(kn log n)"
39// _ (2) Petr Vilim "Max energy filtering algorithm for discrete cumulative
40// resources".
41// _ (3) Wolf & Schrader "O(n log n) Overload Checking for the Cumulative
42// Constraint and Its Application".
43// _ (4) Kameugne & Fotso "A cumulative not-first/not-last filtering algorithm
44// in O(n^2 log n)".
45// _ (5) Ouellet & Quimper "Time-table extended-edge-finding for the cumulative
46// constraint".
47//
48// Instead of providing one declination of the theta-tree per possible filtering
49// algorithm, this generalization intends to provide a data structure that can
50// fit several algorithms.
51// This tree is based around the notion of events. It has events at its leaves
52// that can be present or absent, and present events come with an
53// initial_envelope, a minimal and a maximal energy.
54// All nodes maintain values on the set of present events under them:
55// _ sum_energy_min(node) = sum_{leaf \in leaves(node)} energy_min(leaf)
56// _ envelope(node) =
57// max_{leaf \in leaves(node)}
58// initial_envelope(leaf) +
59// sum_{leaf' \in leaves(node), leaf' >= leaf} energy_min(leaf').
60//
61// Thus, the envelope of a leaf representing an event, when present, is
62// initial_envelope(event) + sum_energy_min(event).
63//
64// We also maintain envelope_opt with is the maximum envelope a node could take
65// if at most one of the events were at its maximum energy.
66// _ energy_delta(leaf) = energy_max(leaf) - energy_min(leaf)
67// _ max_energy_delta(node) = max_{leaf \in leaves(node)} energy_delta(leaf)
68// _ envelope_opt(node) =
69// max_{leaf \in leaves(node)}
70// initial_envelope(leaf) +
71// sum_{leaf' \in leaves(node), leaf' >= leaf} energy_min(leaf') +
72// max_{leaf' \in leaves(node), leaf' >= leaf} energy_delta(leaf');
73//
74// Most articles using theta-tree variants hack Vilim's original theta tree
75// for the disjunctive resource constraint by manipulating envelope and
76// energy:
77// _ in (0), initial_envelope = start_min, energy = duration
78// _ in (3), initial_envelope = C * start_min, energy = demand * duration
79// _ in (5), there are several trees in parallel:
80// initial_envelope = C * start_min or (C - h) * start_min
81// energy = demand * duration, h * (Horizon - start_min),
82// or h * (end_min).
83// _ in (2), same as (3), but putting the max energy instead of min in lambda.
84// _ in OscaR's TimeTableOverloadChecker,
85// initial_envelope = C * start_min -
86// energy of mandatory profile before start_min,
87// energy = demand * duration
88//
89// There is hope to unify the variants of these algorithms by abstracting the
90// tasks away to reason only on events.
91
92// The minimal value of an envelope, for instance the envelope of the empty set.
93template <typename IntegerType>
94constexpr IntegerType IntegerTypeMinimumValue() {
96}
97template <>
98constexpr IntegerValue IntegerTypeMinimumValue() {
99 return kMinIntegerValue;
100}
101
102template <typename IntegerType>
104 public:
105 // Builds a reusable tree. Initialization is done with Reset().
107
108 // Initializes this class for events in [0, num_events) and makes all of them
109 // absent. Instead of allocating and de-allocating trees at every usage, i.e.
110 // at every Propagate() of the scheduling algorithms that uses it, this class
111 // allows to keep the same memory for each call.
112 void Reset(int num_events);
113
114 // Recomputes the values of internal nodes of the tree from the values in the
115 // leaves. We enable batching modifications to the tree by providing
116 // DelayedXXX() methods that run in O(1), but those methods do not
117 // update internal nodes. This breaks tree invariants, so that GetXXX()
118 // methods will not reflect modifications made to events.
119 // RecomputeTreeForDelayedOperations() restores those invariants in O(n).
120 // Thus, batching operations can be done by first doing calls to DelayedXXX()
121 // methods, then calling RecomputeTreeForDelayedOperations() once.
123
124 // Makes event present and updates its initial envelope and min/max energies.
125 // The initial_envelope must be >= ThetaLambdaTreeNegativeInfinity().
126 // This updates the tree in O(log n).
127 void AddOrUpdateEvent(int event, IntegerType initial_envelope,
128 IntegerType energy_min, IntegerType energy_max);
129
130 // Delayed version of AddOrUpdateEvent(),
131 // see RecomputeTreeForDelayedOperations().
132 void DelayedAddOrUpdateEvent(int event, IntegerType initial_envelope,
133 IntegerType energy_min, IntegerType energy_max);
134
135 // Adds event to the lambda part of the tree only.
136 // This will leave GetEnvelope() unchanged, only GetOptionalEnvelope() can
137 // be affected. This is done by setting envelope to IntegerTypeMinimumValue(),
138 // energy_min to 0, and initial_envelope_opt and energy_max to the parameters.
139 // This updates the tree in O(log n).
140 void AddOrUpdateOptionalEvent(int event, IntegerType initial_envelope_opt,
141 IntegerType energy_max);
142
143 // Delayed version of AddOrUpdateOptionalEvent(),
144 // see RecomputeTreeForDelayedOperations().
145 void DelayedAddOrUpdateOptionalEvent(int event,
146 IntegerType initial_envelope_opt,
147 IntegerType energy_max);
148
149 // Makes event absent, compute the new envelope in O(log n).
150 void RemoveEvent(int event);
151
152 // Delayed version of RemoveEvent(), see RecomputeTreeForDelayedOperations().
153 void DelayedRemoveEvent(int event);
154
155 // Returns the maximum envelope using all the energy_min in O(1).
156 // If theta is empty, returns ThetaLambdaTreeNegativeInfinity().
157 IntegerType GetEnvelope() const;
158
159 // Returns the maximum envelope using the energy min of all task but
160 // one and the energy max of the last one in O(1).
161 // If theta and lambda are empty, returns ThetaLambdaTreeNegativeInfinity().
162 IntegerType GetOptionalEnvelope() const;
163
164 // Computes the maximum event s.t. GetEnvelopeOf(event) > envelope_max.
165 // There must be such an event, i.e. GetEnvelope() > envelope_max.
166 // This finds the maximum event e such that
167 // initial_envelope(e) + sum_{e' >= e} energy_min(e') > target_envelope.
168 // This operation is O(log n).
169 int GetMaxEventWithEnvelopeGreaterThan(IntegerType target_envelope) const;
170
171 // Returns initial_envelope(event) + sum_{event' >= event} energy_min(event'),
172 // in time O(log n).
173 IntegerType GetEnvelopeOf(int event) const;
174
175 // Computes a pair of events (critical_event, optional_event) such that
176 // if optional_event was at its maximum energy, the envelope of critical_event
177 // would be greater than target_envelope.
178 //
179 // This assumes that such a pair exists, i.e. GetOptionalEnvelope() should be
180 // greater than target_envelope. More formally, this finds events such that:
181 // initial_envelope(critical_event) +
182 // sum_{event' >= critical_event} energy_min(event') +
183 // max_{optional_event >= critical_event} energy_delta(optional_event)
184 // > target envelope.
185 //
186 // For efficiency reasons, this also fills available_energy with the maximum
187 // energy the optional task can take such that the optional envelope of the
188 // pair would be target_envelope, i.e.
189 // target_envelope - GetEnvelopeOf(event) + energy_min(optional_event).
190 //
191 // This operation is O(log n).
193 IntegerType target_envelope, int* critical_event, int* optional_event,
194 IntegerType* available_energy) const;
195
196 // Getters.
197 IntegerType EnergyMin(int event) const {
198 return tree_[GetLeafFromEvent(event)].sum_of_energy_min;
199 }
200
201 private:
202 struct TreeNode {
203 IntegerType envelope;
204 IntegerType envelope_opt;
205 IntegerType sum_of_energy_min;
206 IntegerType max_of_energy_delta;
207 };
208
209 TreeNode ComposeTreeNodes(TreeNode left, TreeNode right);
210
211 int GetLeafFromEvent(int event) const;
212 int GetEventFromLeaf(int leaf) const;
213
214 // Propagates the change of leaf energies and envelopes towards the root.
215 void RefreshNode(int node);
216
217 // Finds the maximum leaf under node such that
218 // initial_envelope(leaf) + sum_{leaf' >= leaf} energy_min(leaf')
219 // > target_envelope.
220 // Fills extra with the difference.
221 int GetMaxLeafWithEnvelopeGreaterThan(int node, IntegerType target_envelope,
222 IntegerType* extra) const;
223
224 // Returns the leaf with maximum energy delta under node.
225 int GetLeafWithMaxEnergyDelta(int node) const;
226
227 // Finds the leaves and energy relevant for
228 // GetEventsWithOptionalEnvelopeGreaterThan().
229 void GetLeavesWithOptionalEnvelopeGreaterThan(
230 IntegerType target_envelope, int* critical_leaf, int* optional_leaf,
231 IntegerType* available_energy) const;
232
233 // Number of events of the last Reset().
234 int num_events_;
235 int num_leaves_;
236 int power_of_two_;
237
238 // A bool used in debug mode, to check that sequences of delayed operations
239 // are ended by Reset() or RecomputeTreeForDelayedOperations().
240 bool leaf_nodes_have_delayed_operations_ = false;
241
242 // Envelopes and energies of nodes.
243 std::vector<TreeNode> tree_;
244};
245
246// Explicit instantiations in theta_Tree.cc.
247extern template class ThetaLambdaTree<IntegerValue>;
248extern template class ThetaLambdaTree<int64>;
249
250} // namespace sat
251} // namespace operations_research
252
253#endif // OR_TOOLS_SAT_THETA_TREE_H_
int64 min
Definition: alldiff_cst.cc:138
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
IntegerType EnergyMin(int event) const
Definition: theta_tree.h:197
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
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
constexpr IntegerType IntegerTypeMinimumValue()
Definition: theta_tree.h:94
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...