Detailed Description

Helper class for cumulative constraint to wrap demands and expose concept like energy.

In a cumulative constraint, an interval always has a size and a demand, but it can also have a set of "selector" literals each associated with a fixed size / fixed demands. This allows more precise energy estimation.

Todo: (user): Cache energy min and reason for the non O(1) cases.

Definition at line 487 of file scheduling_helpers.h.

#include <scheduling_helpers.h>

Public Member Functions
	SchedulingDemandHelper (absl::Span< const AffineExpression > demands, SchedulingConstraintHelper helper, Model model)
IntegerValue	DemandMin (int t) const
IntegerValue	DemandMax (int t) const
IntegerValue	LevelZeroDemandMin (int t) const
bool	DemandIsFixed (int t) const
void	AddDemandMinReason (int t)
void	AddDemandMinReason (int t, IntegerValue min_demand)
const std::vector< AffineExpression > &	Demands () const
ABSL_MUST_USE_RESULT bool	AddLinearizedDemand (int t, LinearConstraintBuilder *builder) const
bool	CacheAllEnergyValues ()
IntegerValue	EnergyMin (int t) const
IntegerValue	EnergyMax (int t) const
bool	EnergyIsQuadratic (int t) const
void	AddEnergyMinReason (int t)
IntegerValue	EnergyMinInWindow (int t, IntegerValue window_start, IntegerValue window_end)
void	AddEnergyMinInWindowReason (int t, IntegerValue window_start, IntegerValue window_end)
ABSL_MUST_USE_RESULT bool	DecreaseEnergyMax (int t, IntegerValue value)
const std::vector< std::vector< LiteralValueValue > > &	DecomposedEnergies () const
void	OverrideDecomposedEnergies (const std::vector< std::vector< LiteralValueValue > > &energies)
	Visible for testing.
std::vector< LiteralValueValue >	FilteredDecomposedEnergy (int index)
void	InitDecomposedEnergies ()

Constructor & Destructor Documentation

◆ SchedulingDemandHelper()

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

Hack: this can be called with and empty demand vector as long as OverrideEnergies() is called to define the energies.

We try to init decomposed energies. This is needed for the cuts that are created after we call InitAllDecomposedEnergies().

Definition at line 723 of file scheduling_helpers.cc.

Member Function Documentation

◆ AddDemandMinReason() [1/2]

void operations_research::sat::SchedulingDemandHelper::AddDemandMinReason ( int t )

Definition at line 868 of file scheduling_helpers.cc.

◆ AddDemandMinReason() [2/2]

void operations_research::sat::SchedulingDemandHelper::AddDemandMinReason	(	int	t,
		IntegerValue	min_demand )

Definition at line 876 of file scheduling_helpers.cc.

◆ AddEnergyMinInWindowReason()

void operations_research::sat::SchedulingDemandHelper::AddEnergyMinInWindowReason	(	int	t,
		IntegerValue	window_start,
		IntegerValue	window_end )

Since we usually ask way less often for the reason, we redo the computation here.

Return simple reason right away if there is no decomposition or the simple energy is enough.

Todo: (user): only include the one we need?

Should be the same in most cases.

Definition at line 958 of file scheduling_helpers.cc.

◆ AddEnergyMinReason()

void operations_research::sat::SchedulingDemandHelper::AddEnergyMinReason ( int t )

We prefer these reason in order.

Definition at line 885 of file scheduling_helpers.cc.

◆ AddLinearizedDemand()

bool operations_research::sat::SchedulingDemandHelper::AddLinearizedDemand	(	int	t,
		LinearConstraintBuilder *	builder ) const

Adds the linearized demand (either the affine demand expression, or the demand part of the decomposed energy if present) to the builder. It returns false and do not add any term to the builder.if any literal involved has no integer view.

Definition at line 907 of file scheduling_helpers.cc.

◆ CacheAllEnergyValues()

bool operations_research::sat::SchedulingDemandHelper::CacheAllEnergyValues ( )

The "energy" is usually size * demand, but in some non-conventional usage it might have a more complex formula. In all case, the energy is assumed to be only consumed during the interval duration.

Returns false if the energy can overflow and was not computed.

IMPORTANT: One must call CacheAllEnergyValues() for the values to be updated.

Todo: (user): this is error prone, maybe we should revisit. But if there is many alternatives, we don't want to rescan the list more than a linear number of time per propagation.

Todo: (user): Add more complex EnergyMinBefore(time) once we also support expressing the interval as a set of alternatives.

At level 0, it will filter false literals from decomposed energies.

Try to reduce the size of the decomposed energy vector.

Definition at line 792 of file scheduling_helpers.cc.

◆ DecomposedEnergies()

const std::vector< std::vector< LiteralValueValue > > & operations_research::sat::SchedulingDemandHelper::DecomposedEnergies ( ) const

inline

Different optional representation of the energy of an interval.

Important: first value is size, second value is demand.

Definition at line 551 of file scheduling_helpers.h.

◆ DecreaseEnergyMax()

bool operations_research::sat::SchedulingDemandHelper::DecreaseEnergyMax	(	int	t,
		IntegerValue	value )

Important: This might not do anything depending on the representation of the energy we have.

lit encodes that the energy is higher than value. So either lit must be false or the task must be absent.

Task must be absent.

Task is present, lit must be false.

Todo: (user): Propagate if possible.

Definition at line 836 of file scheduling_helpers.cc.

◆ DemandIsFixed()

bool operations_research::sat::SchedulingDemandHelper::DemandIsFixed ( int t ) const

Definition at line 832 of file scheduling_helpers.cc.

◆ DemandMax()

IntegerValue operations_research::sat::SchedulingDemandHelper::DemandMax ( int t ) const

Definition at line 827 of file scheduling_helpers.cc.

◆ DemandMin()

IntegerValue operations_research::sat::SchedulingDemandHelper::DemandMin ( int t ) const

When defined, the interval will consume this much demand during its whole duration. Some propagator only relies on the "energy" and thus never uses this.

Definition at line 822 of file scheduling_helpers.cc.

◆ Demands()

const std::vector< AffineExpression > & operations_research::sat::SchedulingDemandHelper::Demands ( ) const

inline

Definition at line 505 of file scheduling_helpers.h.

◆ EnergyIsQuadratic()

bool operations_research::sat::SchedulingDemandHelper::EnergyIsQuadratic ( int t ) const

inline

Definition at line 532 of file scheduling_helpers.h.

◆ EnergyMax()

IntegerValue operations_research::sat::SchedulingDemandHelper::EnergyMax ( int t ) const

inline

Definition at line 531 of file scheduling_helpers.h.

◆ EnergyMin()

IntegerValue operations_research::sat::SchedulingDemandHelper::EnergyMin ( int t ) const

inline

Definition at line 530 of file scheduling_helpers.h.

◆ EnergyMinInWindow()

IntegerValue operations_research::sat::SchedulingDemandHelper::EnergyMinInWindow	(	int	t,
		IntegerValue	window_start,
		IntegerValue	window_end )

Returns the energy min in [start, end].

Note(user): These functions are not in O(1) if the decomposition is used, so we have to be careful in not calling them too often.

Definition at line 948 of file scheduling_helpers.cc.

◆ FilteredDecomposedEnergy()

std::vector< LiteralValueValue > operations_research::sat::SchedulingDemandHelper::FilteredDecomposedEnergy ( int index )

Returns the decomposed energy terms compatible with the current literal assignment. It must not be used to create reasons if not at level 0. It returns en empty vector if the decomposed energy is not available.

Important: first value is size, second value is demand.

CacheAllEnergyValues has already filtered false literals.

Scan and filter false literals.

Definition at line 925 of file scheduling_helpers.cc.

◆ InitDecomposedEnergies()

void operations_research::sat::SchedulingDemandHelper::InitDecomposedEnergies ( )

Init all decomposed energies. It needs probing to be finished. This happens after the creation of the helper.

For the special case were demands is empty.

Definition at line 743 of file scheduling_helpers.cc.

◆ LevelZeroDemandMin()

IntegerValue operations_research::sat::SchedulingDemandHelper::LevelZeroDemandMin ( int t ) const

inline

Definition at line 499 of file scheduling_helpers.h.

◆ OverrideDecomposedEnergies()

void operations_research::sat::SchedulingDemandHelper::OverrideDecomposedEnergies ( const std::vector< std::vector< LiteralValueValue > > & energies )

Visible for testing.

Definition at line 942 of file scheduling_helpers.cc.

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

ortools/sat/scheduling_helpers.h
ortools/sat/scheduling_helpers.cc

Detailed Description

Public Member Functions

Constructor & Destructor Documentation

◆ SchedulingDemandHelper()

Member Function Documentation

◆ AddDemandMinReason() [1/2]

◆ AddDemandMinReason() [2/2]

◆ AddEnergyMinInWindowReason()

◆ AddEnergyMinReason()

◆ AddLinearizedDemand()

◆ CacheAllEnergyValues()

◆ DecomposedEnergies()

◆ DecreaseEnergyMax()

◆ DemandIsFixed()

◆ DemandMax()

◆ DemandMin()

◆ Demands()

◆ EnergyIsQuadratic()

◆ EnergyMax()

◆ EnergyMin()

◆ EnergyMinInWindow()

◆ FilteredDecomposedEnergy()

◆ InitDecomposedEnergies()

◆ LevelZeroDemandMin()

◆ OverrideDecomposedEnergies()