![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
Helper class shared by the propagators that manage a given list of tasks.
One of the main advantage of this class is that it allows to share the vectors of tasks sorted by various criteria between propagator for a faster code. It is also helpful to allow in-processing: the intervals that are handled by this class are not necessarily the same as the ones in the model.
Definition at line 87 of file scheduling_helpers.h.
#include <scheduling_helpers.h>
Classes | |
struct | ProfileEvent |
Public Member Functions | |
SchedulingConstraintHelper (std::vector< AffineExpression > starts, std::vector< AffineExpression > ends, std::vector< AffineExpression > sizes, std::vector< LiteralIndex > reason_for_presence, Model *model) | |
SchedulingConstraintHelper (int num_tasks, Model *model) | |
bool | Propagate () final |
bool | IncrementalPropagate (const std::vector< int > &watch_indices) final |
void | RegisterWith (GenericLiteralWatcher *watcher) |
ABSL_MUST_USE_RESULT bool | ResetFromSubset (const SchedulingConstraintHelper &other, absl::Span< const int > tasks) |
int | NumTasks () const |
Returns the number of task. | |
void | SetTimeDirection (bool is_forward) |
bool | CurrentTimeIsForward () const |
ABSL_MUST_USE_RESULT bool | SynchronizeAndSetTimeDirection (bool is_forward) |
IntegerValue | SizeMin (int t) const |
IntegerValue | SizeMax (int t) const |
IntegerValue | StartMin (int t) const |
IntegerValue | EndMin (int t) const |
IntegerValue | StartMax (int t) const |
IntegerValue | EndMax (int t) const |
IntegerValue | LevelZeroSizeMin (int t) const |
IntegerValue | LevelZeroStartMin (int t) const |
IntegerValue | LevelZeroStartMax (int t) const |
IntegerValue | LevelZeroEndMax (int t) const |
IntegerValue | ShiftedStartMin (int t) const |
IntegerValue | ShiftedEndMax (int t) const |
bool | StartIsFixed (int t) const |
bool | EndIsFixed (int t) const |
bool | SizeIsFixed (int t) const |
bool | IsOptional (int t) const |
bool | IsPresent (int t) const |
bool | IsAbsent (int t) const |
bool | IsOptional (LiteralIndex lit) const |
Same if one already have the presence LiteralIndex of a task. | |
bool | IsPresent (LiteralIndex lit) const |
bool | IsAbsent (LiteralIndex lit) const |
IntegerValue | GetCurrentMinDistanceBetweenTasks (int a, int b, bool add_reason_if_after=false) |
bool | PropagatePrecedence (int a, int b) |
IntegerValue | GetMinOverlap (int t, IntegerValue start, IntegerValue end) const |
std::string | TaskDebugString (int t) const |
Returns a string with the current task bounds. | |
absl::Span< const TaskTime > | TaskByIncreasingStartMin () |
absl::Span< const TaskTime > | TaskByDecreasingEndMax () |
absl::Span< const TaskTime > | TaskByIncreasingNegatedStartMax () |
absl::Span< const TaskTime > | TaskByIncreasingEndMin () |
absl::Span< const CachedTaskBounds > | TaskByIncreasingShiftedStartMin () |
const std::vector< ProfileEvent > & | GetEnergyProfile () |
void | ClearReason () |
Functions to clear and then set the current reason. | |
void | AddPresenceReason (int t) |
void | AddAbsenceReason (int t) |
void | AddSizeMinReason (int t) |
void | AddSizeMinReason (int t, IntegerValue lower_bound) |
void | AddSizeMaxReason (int t, IntegerValue upper_bound) |
void | AddStartMinReason (int t, IntegerValue lower_bound) |
void | AddStartMaxReason (int t, IntegerValue upper_bound) |
void | AddEndMinReason (int t, IntegerValue lower_bound) |
void | AddEndMaxReason (int t, IntegerValue upper_bound) |
void | AddShiftedEndMaxReason (int t, IntegerValue upper_bound) |
void | AddEnergyAfterReason (int t, IntegerValue energy_min, IntegerValue time) |
void | AddEnergyMinInIntervalReason (int t, IntegerValue min, IntegerValue max) |
void | AddReasonForBeingBefore (int before, int after) |
Produces a relaxed reason for StartMax(before) < EndMin(after). | |
std::vector< Literal > * | MutableLiteralReason () |
std::vector< IntegerLiteral > * | MutableIntegerReason () |
ABSL_MUST_USE_RESULT bool | IncreaseStartMin (int t, IntegerValue value) |
ABSL_MUST_USE_RESULT bool | IncreaseEndMin (int t, IntegerValue value) |
ABSL_MUST_USE_RESULT bool | DecreaseEndMax (int t, IntegerValue value) |
ABSL_MUST_USE_RESULT bool | PushLiteral (Literal l) |
ABSL_MUST_USE_RESULT bool | PushTaskAbsence (int t) |
ABSL_MUST_USE_RESULT bool | PushTaskPresence (int t) |
ABSL_MUST_USE_RESULT bool | PushIntegerLiteral (IntegerLiteral lit) |
ABSL_MUST_USE_RESULT bool | ReportConflict () |
ABSL_MUST_USE_RESULT bool | PushIntegerLiteralIfTaskPresent (int t, IntegerLiteral lit) |
absl::Span< const AffineExpression > | Starts () const |
absl::Span< const AffineExpression > | Ends () const |
absl::Span< const AffineExpression > | Sizes () const |
IntervalDefinition | GetIntervalDefinition (int index) const |
Literal | PresenceLiteral (int index) const |
void | WatchAllTasks (int id) |
void | SetOtherHelper (SchedulingConstraintHelper *other_helper, absl::Span< const int > map_to_other_helper, IntegerValue event) |
bool | HasOtherHelper () const |
void | ClearOtherHelper () |
void | ImportOtherReasons (const SchedulingConstraintHelper &other_helper) |
bool | InPropagationLoop () const |
int | CurrentDecisionLevel () const |
Public Member Functions inherited from operations_research::sat::PropagatorInterface | |
PropagatorInterface ()=default | |
virtual | ~PropagatorInterface ()=default |
operations_research::sat::SchedulingConstraintHelper::SchedulingConstraintHelper | ( | std::vector< AffineExpression > | starts, |
std::vector< AffineExpression > | ends, | ||
std::vector< AffineExpression > | sizes, | ||
std::vector< LiteralIndex > | reason_for_presence, | ||
Model * | model ) |
All the functions below refer to a task by its index t in the tasks vector given at construction.
Definition at line 42 of file scheduling_helpers.cc.
operations_research::sat::SchedulingConstraintHelper::SchedulingConstraintHelper | ( | int | num_tasks, |
Model * | model ) |
Temporary constructor. The class will not be usable until ResetFromSubset() is called.
Definition at line 83 of file scheduling_helpers.cc.
|
inline |
Definition at line 676 of file scheduling_helpers.h.
|
inline |
Definition at line 753 of file scheduling_helpers.h.
|
inline |
Definition at line 745 of file scheduling_helpers.h.
|
inline |
Definition at line 765 of file scheduling_helpers.h.
|
inline |
Definition at line 775 of file scheduling_helpers.h.
|
inline |
Definition at line 668 of file scheduling_helpers.h.
void operations_research::sat::SchedulingConstraintHelper::AddReasonForBeingBefore | ( | int | before, |
int | after ) |
Produces a relaxed reason for StartMax(before) < EndMin(after).
Adds the reason why task "before" must be before task "after". That is StartMax(before) < EndMin(after).
The reason will be a linear expression greater than a value. Note that all coeff must be positive, and we will use the variable lower bound.
Reason for StartMax(before).
Reason for EndMin(after);
Definition at line 500 of file scheduling_helpers.cc.
|
inline |
Definition at line 760 of file scheduling_helpers.h.
|
inline |
Definition at line 724 of file scheduling_helpers.h.
|
inline |
Definition at line 684 of file scheduling_helpers.h.
|
inline |
Definition at line 715 of file scheduling_helpers.h.
|
inline |
Definition at line 738 of file scheduling_helpers.h.
|
inline |
Definition at line 731 of file scheduling_helpers.h.
|
inline |
Definition at line 346 of file scheduling_helpers.h.
|
inline |
Functions to clear and then set the current reason.
Definition at line 659 of file scheduling_helpers.h.
|
inline |
Definition at line 359 of file scheduling_helpers.h.
|
inline |
Definition at line 126 of file scheduling_helpers.h.
bool operations_research::sat::SchedulingConstraintHelper::DecreaseEndMax | ( | int | t, |
IntegerValue | value ) |
Definition at line 595 of file scheduling_helpers.cc.
|
inline |
Definition at line 615 of file scheduling_helpers.h.
|
inline |
Definition at line 150 of file scheduling_helpers.h.
|
inline |
Definition at line 148 of file scheduling_helpers.h.
|
inline |
Definition at line 308 of file scheduling_helpers.h.
IntegerValue operations_research::sat::SchedulingConstraintHelper::GetCurrentMinDistanceBetweenTasks | ( | int | a, |
int | b, | ||
bool | add_reason_if_after = false ) |
Return a value so that End(a) + dist <= Start(b). Returns kMinInterValue if we don't have any such relation.
We take the min of the level zero (end_a - start_b) and the one coming from a conditional precedence at true.
Definition at line 345 of file scheduling_helpers.cc.
const std::vector< SchedulingConstraintHelper::ProfileEvent > & operations_research::sat::SchedulingConstraintHelper::GetEnergyProfile | ( | ) |
Definition at line 475 of file scheduling_helpers.cc.
|
inline |
Definition at line 311 of file scheduling_helpers.h.
IntegerValue operations_research::sat::SchedulingConstraintHelper::GetMinOverlap | ( | int | t, |
IntegerValue | start, | ||
IntegerValue | end ) const |
Return the minimum overlap of interval i with the time window [start..end].
Definition at line 685 of file scheduling_helpers.cc.
|
inline |
Definition at line 344 of file scheduling_helpers.h.
void operations_research::sat::SchedulingConstraintHelper::ImportOtherReasons | ( | const SchedulingConstraintHelper & | other_helper | ) |
Adds to this helper reason all the explanation of the other helper. This checks that other_helper_ is null.
This is used in the 2D energetic reasoning in the diffn constraint.
Definition at line 664 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::IncreaseEndMin | ( | int | t, |
IntegerValue | value ) |
Definition at line 587 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::IncreaseStartMin | ( | int | t, |
IntegerValue | value ) |
Push something using the current reason. Note that IncreaseStartMin() will also increase the end-min, and DecreaseEndMax() will also decrease the start-max.
Important: IncreaseStartMin() and DecreaseEndMax() can be called on an optional interval whose presence is still unknown and push a bound conditioned on its presence. The functions will do the correct thing depending on whether or not the start_min/end_max are optional variables whose presence implies the interval presence.
Definition at line 579 of file scheduling_helpers.cc.
|
finalvirtual |
This will only be called on a non-empty vector, otherwise Propagate() will be called. The passed vector will contain the "watch index" of all the literals that were given one at registration and that changed since the last call to Propagate(). This is only true when going down in the search tree, on backjump this list will be cleared.
Notes:
Reimplemented from operations_research::sat::PropagatorInterface.
Definition at line 108 of file scheduling_helpers.cc.
|
inline |
Definition at line 357 of file scheduling_helpers.h.
|
inline |
Definition at line 637 of file scheduling_helpers.h.
|
inline |
Definition at line 654 of file scheduling_helpers.h.
|
inline |
Returns true if the corresponding fact is known for sure. A normal task is always present. For optional task for which the presence is still unknown, both of these function will return false.
Definition at line 623 of file scheduling_helpers.h.
|
inline |
Same if one already have the presence LiteralIndex of a task.
Definition at line 645 of file scheduling_helpers.h.
|
inline |
Definition at line 629 of file scheduling_helpers.h.
|
inline |
Definition at line 649 of file scheduling_helpers.h.
|
inline |
Definition at line 164 of file scheduling_helpers.h.
|
inline |
Note the variable that encodes the size of an absent task can be negative.
Definition at line 152 of file scheduling_helpers.h.
|
inline |
Definition at line 161 of file scheduling_helpers.h.
|
inline |
Definition at line 158 of file scheduling_helpers.h.
|
inline |
Definition at line 283 of file scheduling_helpers.h.
|
inline |
It is also possible to directly manipulates the underlying reason vectors that will be used when pushing something.
Definition at line 282 of file scheduling_helpers.h.
|
inline |
Returns the number of task.
Definition at line 119 of file scheduling_helpers.h.
|
inline |
Definition at line 321 of file scheduling_helpers.h.
|
finalvirtual |
This is a propagator so we can "cache" all the intervals relevant information. This gives good speedup. Note however that the info is stale except if a bound was pushed by this helper or if this was called. We run it at the highest priority, so that will mostly be the case at the beginning of each Propagate() call of the classes using this.
Implements operations_research::sat::PropagatorInterface.
Definition at line 102 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::PropagatePrecedence | ( | int | a, |
int | b ) |
We detected a precedence between two tasks. If we are at level zero, we might want to add the constraint. If we are at positive level, we might want to propagate the associated precedence literal if it exists.
Definition at line 371 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::PushIntegerLiteral | ( | IntegerLiteral | lit | ) |
Definition at line 552 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::PushIntegerLiteralIfTaskPresent | ( | int | t, |
IntegerLiteral | lit ) |
Definition at line 557 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::PushLiteral | ( | Literal | l | ) |
Definition at line 603 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::PushTaskAbsence | ( | int | t | ) |
Definition at line 608 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::PushTaskPresence | ( | int | t | ) |
Definition at line 624 of file scheduling_helpers.cc.
void operations_research::sat::SchedulingConstraintHelper::RegisterWith | ( | GenericLiteralWatcher * | watcher | ) |
This class do not need to be waked up on presence change, since this is not cached. However given that we can have many propagators that use the same helper, it is nicer to only register this one, and wake up all propagator through it rather than registering all of them individually.
Definition at line 115 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::ReportConflict | ( | ) |
Definition at line 640 of file scheduling_helpers.cc.
bool operations_research::sat::SchedulingConstraintHelper::ResetFromSubset | ( | const SchedulingConstraintHelper & | other, |
absl::Span< const int > | tasks ) |
Resets the class to the same state as if it was constructed with the given subset of tasks from other.
Definition at line 216 of file scheduling_helpers.cc.
|
inline |
Manages the other helper (used by the diffn constraint).
For each interval appearing in a reason on this helper, another reason will be added. This other reason specifies that on the other helper, the corresponding interval overlaps 'event'.
Definition at line 335 of file scheduling_helpers.h.
void operations_research::sat::SchedulingConstraintHelper::SetTimeDirection | ( | bool | is_forward | ) |
Make sure the cached values are up to date. Also sets the time direction to either forward/backward. This will impact all the functions below. This MUST be called at the beginning of all Propagate() call that uses this helper.
Definition at line 282 of file scheduling_helpers.cc.
|
inline |
As with ShiftedStartMin(), we can compute the shifted end max (that is start_max + size_min.
Definition at line 188 of file scheduling_helpers.h.
|
inline |
In the presence of tasks with a variable size, we do not necessarily have start_min + size_min = end_min, we can instead have a situation like: | |<— size-min --->| ^ ^ ^ start-min | end-min | We define the "shifted start min" to be the right most time such that we known that we must have min-size "energy" to the right of it if the task is present. Using it in our scheduling propagators allows to propagate more in the presence of tasks with variable size (or optional task where we also do not necessarily have start_min + size_min = end_min.
To explain this shifted start min, one must use the AddEnergyAfterReason().
Definition at line 182 of file scheduling_helpers.h.
|
inline |
Definition at line 619 of file scheduling_helpers.h.
|
inline |
This one is "rare" so we don't cache it.
Definition at line 143 of file scheduling_helpers.h.
|
inline |
Helpers for the current bounds on the current task time window. [ (size-min) ... (size-min) ] ^ ^ ^ ^ start-min end-min start-max end-max
Remark: We use cached values for most of these function as this is faster. In practice, the cache will almost always be up to date, but not in corner cases where pushing the start of one task will change values for many others. This is fine as the new values will be picked up as we reach the propagation fixed point.
Definition at line 142 of file scheduling_helpers.h.
|
inline |
Definition at line 309 of file scheduling_helpers.h.
|
inline |
SchedulingConstraintHelper inlined functions.
Definition at line 611 of file scheduling_helpers.h.
|
inline |
Definition at line 149 of file scheduling_helpers.h.
|
inline |
Definition at line 147 of file scheduling_helpers.h.
|
inline |
Definition at line 307 of file scheduling_helpers.h.
bool operations_research::sat::SchedulingConstraintHelper::SynchronizeAndSetTimeDirection | ( | bool | is_forward | ) |
If there was any backtracks since the last time this was called, we recompute our cache.
We also update non_fixed_intervals_ at level zero so that we will never scan them again.
Definition at line 304 of file scheduling_helpers.cc.
absl::Span< const TaskTime > operations_research::sat::SchedulingConstraintHelper::TaskByDecreasingEndMax | ( | ) |
Definition at line 446 of file scheduling_helpers.cc.
absl::Span< const TaskTime > operations_research::sat::SchedulingConstraintHelper::TaskByIncreasingEndMin | ( | ) |
Definition at line 422 of file scheduling_helpers.cc.
absl::Span< const TaskTime > operations_research::sat::SchedulingConstraintHelper::TaskByIncreasingNegatedStartMax | ( | ) |
Definition at line 434 of file scheduling_helpers.cc.
absl::Span< const CachedTaskBounds > operations_research::sat::SchedulingConstraintHelper::TaskByIncreasingShiftedStartMin | ( | ) |
Definition at line 456 of file scheduling_helpers.cc.
absl::Span< const TaskTime > operations_research::sat::SchedulingConstraintHelper::TaskByIncreasingStartMin | ( | ) |
Sorts and returns the tasks in corresponding order at the time of the call.
Definition at line 412 of file scheduling_helpers.cc.
std::string operations_research::sat::SchedulingConstraintHelper::TaskDebugString | ( | int | t | ) | const |
Returns a string with the current task bounds.
Definition at line 674 of file scheduling_helpers.cc.
void operations_research::sat::SchedulingConstraintHelper::WatchAllTasks | ( | int | id | ) |
Registers the given propagator id to be called if any of the tasks in this class change. Note that we do not watch size max though.
It is more efficient to enqueue the propagator when the helper Propagate() is called. This result in less entries in our watched lists.
Definition at line 645 of file scheduling_helpers.cc.