Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::ThetaLambdaTree< IntegerType > Class Template Reference

#include <scheduling.h>

Public Member Functions

 ThetaLambdaTree ()=default
 Builds a reusable tree. Initialization is done with Reset().
void Reset (int num_events)
void AddOrUpdateEvent (int event, IntegerType initial_envelope, IntegerType energy_min, IntegerType energy_max)
void AddOrUpdateOptionalEvent (int event, IntegerType initial_envelope_opt, IntegerType energy_max)
void RemoveEvent (int event)
 Makes event absent, compute the new envelope in O(log n).
IntegerType GetEnvelope () const
IntegerType GetOptionalEnvelope () const
int GetMaxEventWithEnvelopeGreaterThan (IntegerType target_envelope) const
IntegerType GetEnvelopeOf (int event) const
void GetEventsWithOptionalEnvelopeGreaterThan (IntegerType target_envelope, int *critical_event, int *optional_event, IntegerType *available_energy) const
IntegerType EnergyMin (int event) const
 Getters.

Detailed Description

template<typename IntegerType>
class operations_research::ThetaLambdaTree< IntegerType >

The Theta-Lambda tree can be used to implement several scheduling algorithms.

This template class is instantiated only for IntegerValue and int64_t.

The tree structure itself is a binary tree coded in a vector, where node 0 is unused, node 1 is the root, node 2 is the left child of the root, node 3 its right child, etc.

The API gives access to rightmost events that realize a given envelope.

See: _ (0) Petr Vilim's PhD thesis "Global Constraints in Scheduling". _ (1) Petr Vilim "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)" _ (2) Petr Vilim "Max energy filtering algorithm for discrete cumulative resources". _ (3) Wolf & Schrader "O(n log n) Overload Checking for the Cumulative Constraint and Its Application". _ (4) Kameugne & Fotso "A cumulative not-first/not-last filtering algorithm in O(n^2 log n)". _ (5) Ouellet & Quimper "Time-table extended-edge-finding for the cumulative constraint".

Instead of providing one declination of the theta-tree per possible filtering algorithm, this generalization intends to provide a data structure that can fit several algorithms. This tree is based around the notion of events. It has events at its leaves that can be present or absent, and present events come with an initial_envelope, a minimal and a maximal energy. All nodes maintain values on the set of present events under them: _ sum_energy_min(node) = sum_{leaf \in leaves(node)} energy_min(leaf) _ envelope(node) = max_{leaf \in leaves(node)} initial_envelope(leaf) + sum_{leaf' \in leaves(node), leaf' >= leaf} energy_min(leaf').

Thus, the envelope of a leaf representing an event, when present, is initial_envelope(event) + sum_energy_min(event).

We also maintain envelope_opt with is the maximum envelope a node could take if at most one of the events were at its maximum energy. _ energy_delta(leaf) = energy_max(leaf) - energy_min(leaf) _ max_energy_delta(node) = max_{leaf \in leaves(node)} energy_delta(leaf) _ envelope_opt(node) = max_{leaf \in leaves(node)} initial_envelope(leaf) + sum_{leaf' \in leaves(node), leaf' >= leaf} energy_min(leaf') + max_{leaf' \in leaves(node), leaf' >= leaf} energy_delta(leaf');

Most articles using theta-tree variants hack Vilim's original theta tree for the disjunctive resource constraint by manipulating envelope and energy: _ in (0), initial_envelope = start_min, energy = duration _ in (3), initial_envelope = C * start_min, energy = demand * duration _ in (5), there are several trees in parallel: initial_envelope = C * start_min or (C - h) * start_min energy = demand * duration, h * (Horizon - start_min), or h * (end_min). _ in (2), same as (3), but putting the max energy instead of min in lambda. _ in OscaR's TimeTableOverloadChecker, initial_envelope = C * start_min - energy of mandatory profile before start_min, energy = demand * duration

There is hope to unify the variants of these algorithms by abstracting the tasks away to reason only on events.

Definition at line 93 of file scheduling.h.

Constructor & Destructor Documentation

◆ ThetaLambdaTree()

template<typename IntegerType>
operations_research::ThetaLambdaTree< IntegerType >::ThetaLambdaTree ( )
default

Builds a reusable tree. Initialization is done with Reset().

Member Function Documentation

◆ AddOrUpdateEvent()

template<typename IntegerType>
void operations_research::ThetaLambdaTree< IntegerType >::AddOrUpdateEvent ( int event,
IntegerType initial_envelope,
IntegerType energy_min,
IntegerType energy_max )
inline

Makes event present and updates its initial envelope and min/max energies. This updates the tree in O(log n).

Definition at line 106 of file scheduling.h.

◆ AddOrUpdateOptionalEvent()

template<typename IntegerType>
void operations_research::ThetaLambdaTree< IntegerType >::AddOrUpdateOptionalEvent ( int event,
IntegerType initial_envelope_opt,
IntegerType energy_max )
inline

Adds event to the lambda part of the tree only. This will leave GetEnvelope() unchanged, only GetOptionalEnvelope() can be affected, by setting envelope to std::numeric_limits<>::min(), energy_min to 0, and initial_envelope_opt and energy_max to the parameters. This updates the tree in O(log n).

Definition at line 123 of file scheduling.h.

◆ EnergyMin()

template<typename IntegerType>
IntegerType operations_research::ThetaLambdaTree< IntegerType >::EnergyMin ( int event) const
inline

Getters.

Definition at line 198 of file scheduling.h.

◆ GetEnvelope()

template<typename IntegerType>
IntegerType operations_research::ThetaLambdaTree< IntegerType >::GetEnvelope ( ) const
inline

Returns the maximum envelope using all the energy_min in O(1). If theta is empty, returns std::numeric_limits<>::min().

Definition at line 146 of file scheduling.h.

◆ GetEnvelopeOf()

template<typename IntegerType>
IntegerType operations_research::ThetaLambdaTree< IntegerType >::GetEnvelopeOf ( int event) const

Returns initial_envelope(event) + sum_{event' >= event} energy_min(event'), in time O(log n).

Definition at line 293 of file scheduling.h.

◆ GetEventsWithOptionalEnvelopeGreaterThan()

template<typename IntegerType>
void operations_research::ThetaLambdaTree< IntegerType >::GetEventsWithOptionalEnvelopeGreaterThan ( IntegerType target_envelope,
int * critical_event,
int * optional_event,
IntegerType * available_energy ) const
inline

Computes a pair of events (critical_event, optional_event) such that if optional_event was at its maximum energy, the envelope of critical_event would be greater than target_envelope.

This assumes that such a pair exists, i.e. GetOptionalEnvelope() should be greater than target_envelope. More formally, this finds events such that: initial_envelope(critical_event) + sum_{event' >= critical_event} energy_min(event') + max_{optional_event >= critical_event} energy_delta(optional_event) > target envelope.

For efficiency reasons, this also fills available_energy with the maximum energy the optional task can take such that the optional envelope of the pair would be target_envelope, i.e. target_envelope - GetEnvelopeOf(event) + energy_min(optional_event).

This operation is O(log n).

Definition at line 186 of file scheduling.h.

◆ GetMaxEventWithEnvelopeGreaterThan()

template<typename IntegerType>
int operations_research::ThetaLambdaTree< IntegerType >::GetMaxEventWithEnvelopeGreaterThan ( IntegerType target_envelope) const
inline

Computes the maximum event s.t. GetEnvelopeOf(event) > envelope_max. There must be such an event, i.e. GetEnvelope() > envelope_max. This finds the maximum event e such that initial_envelope(e) + sum_{e' >= e} energy_min(e') > target_envelope. This operation is O(log n).

Definition at line 158 of file scheduling.h.

◆ GetOptionalEnvelope()

template<typename IntegerType>
IntegerType operations_research::ThetaLambdaTree< IntegerType >::GetOptionalEnvelope ( ) const
inline

Returns the maximum envelope using the energy min of all task but one and the energy max of the last one in O(1). If theta and lambda are empty, returns std::numeric_limits<>::min().

Definition at line 151 of file scheduling.h.

◆ RemoveEvent()

template<typename IntegerType>
void operations_research::ThetaLambdaTree< IntegerType >::RemoveEvent ( int event)
inline

Makes event absent, compute the new envelope in O(log n).

Definition at line 135 of file scheduling.h.

◆ Reset()

template<typename IntegerType>
void operations_research::ThetaLambdaTree< IntegerType >::Reset ( int num_events)

Initializes this class for events in [0, num_events) and makes all of them absent. Instead of allocating and de-allocating trees at every usage, i.e. at every Propagate() of the scheduling algorithms that uses it, this class allows to keep the same memory for each call.

Because the algorithm needs to access a node sibling (i.e. node_index ^ 1), our tree will always have an even number of leaves, just large enough to fit our number of events. And at least 2 for the empty tree case.

If num_leaves is not a power or two, the last depth of the tree will not be full, and the array will look like: [( num_leafs parents)(leaves at depth d - 1)(leaves at depth d) The first leaves at depth p will have power_of_two_ as index.

Definition at line 270 of file scheduling.h.


The documentation for this class was generated from the following file: