operations_research::sat::TimeTableEdgeFinding Class Reference

#include <timetable_edgefinding.h>

Inheritance diagram for operations_research::sat::TimeTableEdgeFinding:

Public Member Functions
	TimeTableEdgeFinding (AffineExpression capacity, SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands, Model *model)
	TimeTableEdgeFinding (const TimeTableEdgeFinding &)=delete
	This type is neither copyable nor movable.
TimeTableEdgeFinding &	operator= (const TimeTableEdgeFinding &)=delete
bool	Propagate () final
void	RegisterWith (GenericLiteralWatcher *watcher)
Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default
virtual	~PropagatorInterface ()=default
virtual bool	IncrementalPropagate (const std::vector< int > &)

Detailed Description

TimeTableEdgeFinding implements the timetable edge finding filtering rule presented in Vilim Petr, "Timetable edge finding filtering algorithm for discrete cumulative resources", CPAIOR 2011, http://vilim.eu/petr/cpaior2011.pdf.

This propagator runs in O(n^2) where n is the number of tasks. It increases both the start times and decreases the ending times of the tasks.

Note

this propagator does not ensure that the cumulative constraint holds. It should thus always be used with at least a timetable propagator.

ALOGRITHM:

The algorithm relies on free tasks. A free task is basically a task without its mandatory part. For instance:

       s_min       s_max            e_min       e_max
         v           v                v           v
task:    =============================
         ^           ^                ^
         | free part | Mandatory part |

Obviously, the free part of a task that has no mandatory part is equal to the task itself. Also, a free part cannot have a mandatory part by definition. A fixed task thus have no free part.

The idea of the algorithm is to use free and mandatory parts separately to have a better estimation of the energy contained in a task interval.

If the sum of the energy of all the free parts and mandatory subparts contained in a task interval exceeds the amount of energy available, then the problem is unfeasible. A task thus cannot be scheduled at its minimum start time if this would cause an overload in one of the task intervals.

Definition at line 61 of file timetable_edgefinding.h.

Constructor & Destructor Documentation

TimeTableEdgeFinding() [1/2]

operations_research::sat::TimeTableEdgeFinding::TimeTableEdgeFinding	(	AffineExpression	capacity,
		SchedulingConstraintHelper *	helper,
		SchedulingDemandHelper *	demands,
		Model *	model )

Edge finding structures.

Energy of free parts.

Definition at line 29 of file timetable_edgefinding.cc.

TimeTableEdgeFinding() [2/2]

operations_research::sat::TimeTableEdgeFinding::TimeTableEdgeFinding ( const TimeTableEdgeFinding & )

delete

This type is neither copyable nor movable.

Member Function Documentation

operator=()

TimeTableEdgeFinding & operations_research::sat::TimeTableEdgeFinding::operator= ( const TimeTableEdgeFinding & )

delete

Propagate()

bool operations_research::sat::TimeTableEdgeFinding::Propagate ( )

finalvirtual

This will be called after one or more literals that are watched by this propagator changed. It will also always be called on the first propagation cycle after registration.

Implements operations_research::sat::PropagatorInterface.

Definition at line 58 of file timetable_edgefinding.cc.

RegisterWith()

void operations_research::sat::TimeTableEdgeFinding::RegisterWith

(

GenericLiteralWatcher *

watcher

)

Definition at line 47 of file timetable_edgefinding.cc.

---

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

• ortools/sat/timetable_edgefinding.h
• ortools/sat/timetable_edgefinding.cc