operations_research::sat::SchedulingDemandHelper Class Reference

#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 ()

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 482 of file scheduling_helpers.h.

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 713 of file scheduling_helpers.cc.

Member Function Documentation

AddDemandMinReason() [1/2]

void operations_research::sat::SchedulingDemandHelper::AddDemandMinReason

(

int

t

)

Definition at line 848 of file scheduling_helpers.cc.

AddDemandMinReason() [2/2]

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

Definition at line 856 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 938 of file scheduling_helpers.cc.

AddEnergyMinReason()

void operations_research::sat::SchedulingDemandHelper::AddEnergyMinReason

(

int

t

)

We prefer these reason in order.

Definition at line 865 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 887 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 782 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 546 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.

Todo

(user): Propagate if possible.

Definition at line 826 of file scheduling_helpers.cc.

DemandIsFixed()

bool operations_research::sat::SchedulingDemandHelper::DemandIsFixed

(

int

t

)

const

Definition at line 822 of file scheduling_helpers.cc.

DemandMax()

IntegerValue operations_research::sat::SchedulingDemandHelper::DemandMax

(

int

t

)

const

Definition at line 817 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 812 of file scheduling_helpers.cc.

Demands()

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

inline

Definition at line 500 of file scheduling_helpers.h.

EnergyIsQuadratic()

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

inline

Definition at line 527 of file scheduling_helpers.h.

EnergyMax()

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

inline

Definition at line 526 of file scheduling_helpers.h.

EnergyMin()

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

inline

Definition at line 525 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 928 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 905 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 733 of file scheduling_helpers.cc.

LevelZeroDemandMin()

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

inline

Definition at line 494 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 922 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