#include <intervals.h>

Classes
struct	CumulativeHelper

Public Member Functions
	IntervalsRepository (Model *model)

	IntervalsRepository (const IntervalsRepository &)=delete
	This type is neither copyable nor movable.

IntervalsRepository &	operator= (const IntervalsRepository &)=delete

int	NumIntervals () const

IntervalVariable	CreateInterval (IntegerVariable start, IntegerVariable end, IntegerVariable size, IntegerValue fixed_size, LiteralIndex is_present)

IntervalVariable	CreateInterval (AffineExpression start, AffineExpression end, AffineExpression size, LiteralIndex is_present=kNoLiteralIndex, bool add_linear_relation=false)

bool	IsOptional (IntervalVariable i) const
	Returns whether or not a interval is optional and the associated literal.

Literal	PresenceLiteral (IntervalVariable i) const

bool	IsPresent (IntervalVariable i) const

bool	IsAbsent (IntervalVariable i) const

AffineExpression	Size (IntervalVariable i) const

AffineExpression	Start (IntervalVariable i) const

AffineExpression	End (IntervalVariable i) const

IntegerValue	MinSize (IntervalVariable i) const
	Return the minimum size of the given IntervalVariable.

IntegerValue	MaxSize (IntervalVariable i) const
	Return the maximum size of the given IntervalVariable.

std::vector< IntervalVariable >	AllIntervals () const
	Utility function that returns a vector will all intervals.

SchedulingConstraintHelper *	GetOrCreateHelper (const std::vector< IntervalVariable > &variables, bool register_as_disjunctive_helper=false)

SchedulingDemandHelper *	GetOrCreateDemandHelper (SchedulingConstraintHelper *helper, absl::Span< const AffineExpression > demands)

void	InitAllDecomposedEnergies ()
	Calls InitDecomposedEnergies on all SchedulingDemandHelper created.

void	CreateDisjunctivePrecedenceLiteral (IntervalVariable a, IntervalVariable b)

bool	CreatePrecedenceLiteral (IntervalVariable a, IntervalVariable b)

LiteralIndex	GetPrecedenceLiteral (IntervalVariable a, IntervalVariable b) const

const std::vector< SchedulingConstraintHelper * > &	AllDisjunctiveHelpers () const

void	RegisterCumulative (CumulativeHelper helper)

const std::vector< CumulativeHelper > &	AllCumulativeHelpers () const

Detailed Description

This class maintains a set of intervals which correspond to three integer variables (start, end and size). It automatically registers with the PrecedencesPropagator the relation between the bounds of each interval and provides many helper functions to add precedences relation between intervals.

Definition at line 57 of file intervals.h.

Constructor & Destructor Documentation

◆ IntervalsRepository() [1/2]

operations_research::sat::IntervalsRepository::IntervalsRepository ( Model * model )

inlineexplicit

Definition at line 59 of file intervals.h.

◆ IntervalsRepository() [2/2]

operations_research::sat::IntervalsRepository::IntervalsRepository ( const IntervalsRepository & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AllCumulativeHelpers()

const std::vector< CumulativeHelper > & operations_research::sat::IntervalsRepository::AllCumulativeHelpers ( ) const

inline

Definition at line 190 of file intervals.h.

◆ AllDisjunctiveHelpers()

const std::vector< SchedulingConstraintHelper * > & operations_research::sat::IntervalsRepository::AllDisjunctiveHelpers ( ) const

inline

Definition at line 175 of file intervals.h.

◆ AllIntervals()

std::vector< IntervalVariable > operations_research::sat::IntervalsRepository::AllIntervals ( ) const

inline

Utility function that returns a vector will all intervals.

Definition at line 125 of file intervals.h.

◆ CreateDisjunctivePrecedenceLiteral()

void operations_research::sat::IntervalsRepository::CreateDisjunctivePrecedenceLiteral	(	IntervalVariable	a,
		IntervalVariable	b )

Assuming a and b cannot overlap if they are present, this create a new literal such that:

literal & presences => a is before b.
not(literal) & presences => b is before a.
not present => literal @ true for disallowing multiple solutions.

If such literal already exists this returns it.

We can ignore always absent interval, and skip the literal of the interval that are now always present.

task_a is always before task_b ?

task_b is always before task_a ?

Create a new literal.

Also insert it in precedences.

Todo: (user): also add the reverse like start_b + 1 <= end_a if negated?

Force the value of boolean_var in case the precedence is not active. This avoids duplicate solutions when enumerating all possible solutions.

Definition at line 85 of file intervals.cc.

◆ CreateInterval() [1/2]

IntervalVariable operations_research::sat::IntervalsRepository::CreateInterval	(	AffineExpression	start,
		AffineExpression	end,
		AffineExpression	size,
		LiteralIndex	is_present = kNoLiteralIndex,
		bool	add_linear_relation = false )

Create the interval.

Definition at line 56 of file intervals.cc.

◆ CreateInterval() [2/2]

IntervalVariable operations_research::sat::IntervalsRepository::CreateInterval	(	IntegerVariable	start,
		IntegerVariable	end,
		IntegerVariable	size,
		IntegerValue	fixed_size,
		LiteralIndex	is_present )

Functions to add a new interval to the repository. If add_linear_relation is true, then we also link start, size and end.

If size == kNoIntegerVariable, then the size is fixed to fixed_size.
If is_present != kNoLiteralIndex, then this is an optional interval.

Definition at line 44 of file intervals.cc.

◆ CreatePrecedenceLiteral()

bool operations_research::sat::IntervalsRepository::CreatePrecedenceLiteral	(	IntervalVariable	a,
		IntervalVariable	b )

Creates a literal l <=> start_b >= end_a. Returns true if such literal is "non-trivial" and was created.

Note: this ignore the optionality of a or b, it just creates a literal comparing the two affine expression.

We want l => x <= y and not(l) => x > y <=> y + 1 <= x Do not create l if the relation is always true or false.

Create a new literal.

Todo: (user): Also add {{y_plus_one, x}, x_before_y.Negated()} ?

Definition at line 149 of file intervals.cc.

◆ End()

AffineExpression operations_research::sat::IntervalsRepository::End ( IntervalVariable i ) const

inline

Definition at line 112 of file intervals.h.

◆ GetOrCreateDemandHelper()

SchedulingDemandHelper * operations_research::sat::IntervalsRepository::GetOrCreateDemandHelper	(	SchedulingConstraintHelper *	helper,
		absl::Span< const AffineExpression >	demands )

Returns a SchedulingDemandHelper corresponding to the given helper and demands. Note that the order of interval in the helper and the order of demands must be the compatible.

Definition at line 206 of file intervals.cc.

◆ GetOrCreateHelper()

SchedulingConstraintHelper * operations_research::sat::IntervalsRepository::GetOrCreateHelper	(	const std::vector< IntervalVariable > &	variables,
		bool	register_as_disjunctive_helper = false )

Returns a SchedulingConstraintHelper corresponding to the given variables.

Note: the order of interval in the helper will be the same.

It is possible to indicate that this correspond to a disjunctive constraint by setting the Boolean to true. This is used by our scheduling heuristic based on precedences.

Todo: (user): Ideally we should sort the vector of variables, but right now we cannot since we often use this with a parallel vector of demands. So this "sorting" should happen in the presolver so we can share as much as possible.

Definition at line 190 of file intervals.cc.

◆ GetPrecedenceLiteral()

LiteralIndex operations_research::sat::IntervalsRepository::GetPrecedenceLiteral	(	IntervalVariable	a,
		IntervalVariable	b ) const

Returns a literal l <=> start_b >= end_a if it exist or kNoLiteralIndex otherwise. This could be the one created by CreateDisjunctivePrecedenceLiteral() or CreatePrecedenceLiteral().

Definition at line 178 of file intervals.cc.

◆ InitAllDecomposedEnergies()

void operations_research::sat::IntervalsRepository::InitAllDecomposedEnergies ( )

Calls InitDecomposedEnergies on all SchedulingDemandHelper created.

Definition at line 222 of file intervals.cc.

◆ IsAbsent()

bool operations_research::sat::IntervalsRepository::IsAbsent ( IntervalVariable i ) const

inline

Definition at line 98 of file intervals.h.

◆ IsOptional()

bool operations_research::sat::IntervalsRepository::IsOptional ( IntervalVariable i ) const

inline

Returns whether or not a interval is optional and the associated literal.

Definition at line 88 of file intervals.h.

◆ IsPresent()

bool operations_research::sat::IntervalsRepository::IsPresent ( IntervalVariable i ) const

inline

Definition at line 94 of file intervals.h.

◆ MaxSize()

IntegerValue operations_research::sat::IntervalsRepository::MaxSize ( IntervalVariable i ) const

inline

Return the maximum size of the given IntervalVariable.

Definition at line 120 of file intervals.h.

◆ MinSize()

IntegerValue operations_research::sat::IntervalsRepository::MinSize ( IntervalVariable i ) const

inline

Return the minimum size of the given IntervalVariable.

Definition at line 115 of file intervals.h.

◆ NumIntervals()

int operations_research::sat::IntervalsRepository::NumIntervals ( ) const

inline

Returns the current number of intervals in the repository. The interval will always be identified by an integer in [0, num_intervals).

Definition at line 72 of file intervals.h.

◆ operator=()

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

delete

◆ PresenceLiteral()

Literal operations_research::sat::IntervalsRepository::PresenceLiteral ( IntervalVariable i ) const

inline

Definition at line 91 of file intervals.h.

◆ RegisterCumulative()

void operations_research::sat::IntervalsRepository::RegisterCumulative ( CumulativeHelper helper )

inline

Definition at line 187 of file intervals.h.

◆ Size()

AffineExpression operations_research::sat::IntervalsRepository::Size ( IntervalVariable i ) const

inline

The 3 integer variables associated to a interval. Fixed size intervals will have a kNoIntegerVariable as size.

Note: For an optional interval, the start/end variables are propagated assuming the interval is present. Because of that, these variables can cross each other or have an empty domain. If any of this happen, then the PresenceLiteral() of this interval will be propagated to false.

Definition at line 110 of file intervals.h.

◆ Start()

AffineExpression operations_research::sat::IntervalsRepository::Start ( IntervalVariable i ) const

inline

Definition at line 111 of file intervals.h.

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

ortools/sat/intervals.h
ortools/sat/intervals.cc

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ IntervalsRepository() [1/2]

◆ IntervalsRepository() [2/2]

Member Function Documentation

◆ AllCumulativeHelpers()

◆ AllDisjunctiveHelpers()

◆ AllIntervals()

◆ CreateDisjunctivePrecedenceLiteral()

◆ CreateInterval() [1/2]

◆ CreateInterval() [2/2]

◆ CreatePrecedenceLiteral()

◆ End()

◆ GetOrCreateDemandHelper()

◆ GetOrCreateHelper()

◆ GetPrecedenceLiteral()

◆ InitAllDecomposedEnergies()

◆ IsAbsent()

◆ IsOptional()

◆ IsPresent()

◆ MaxSize()

◆ MinSize()

◆ NumIntervals()

◆ operator=()

◆ PresenceLiteral()

◆ RegisterCumulative()

◆ Size()

◆ Start()