Implementation of AddCumulativeOverloadCheckerDff(). More...

#include <cumulative_energy.h>

Inheritance diagram for operations_research::sat::CumulativeDualFeasibleEnergyConstraint:

Public Member Functions
	CumulativeDualFeasibleEnergyConstraint (AffineExpression capacity, SchedulingConstraintHelper helper, SchedulingDemandHelper demands, Model *model)

	~CumulativeDualFeasibleEnergyConstraint () override

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

Implementation of AddCumulativeOverloadCheckerDff().

Definition at line 123 of file cumulative_energy.h.

Constructor & Destructor Documentation

◆ CumulativeDualFeasibleEnergyConstraint()

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

Definition at line 393 of file cumulative_energy.cc.

◆ ~CumulativeDualFeasibleEnergyConstraint()

operations_research::sat::CumulativeDualFeasibleEnergyConstraint::~CumulativeDualFeasibleEnergyConstraint ( )

override

Definition at line 407 of file cumulative_energy.cc.

Member Function Documentation

◆ Propagate()

bool operations_research::sat::CumulativeDualFeasibleEnergyConstraint::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.

Set up theta tree.

Since checking all possible dual-feasible functions is expensive, we only look for energy conflicts on time windows where a conflict with a DFF is possible. To rule out time windows where DFF conflicts are impossible, we use the following nice property stated in [1]:

If f is a DFF, then for all possible sizes h_i of a problem of height H: f(h_i)/f(H) <= 1 / floor(H / h_i).

This follows from the fact that floor(H / h_i) copies of h_i can fit sideways on the original problem and that those copies must still fit after any arbitrary DFF is applied.

So, in practice, for a cumulative constraint with maximum capacity C and demands d_i, we look for time windows with energy conflicts for the modified problem: Capacity: L Demand for item i: L / (C / d_i) where L is any sufficiently large integer used to compute inverses without losing too much precision.

[1] Carlier, Jacques, François Clautiaux, and Aziz Moukrim. "New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation." Computers & Operations Research 34.8 (2007): 2223-2250.

Add the current task to the tree.

Find the critical interval.

The code above is efficient for pruning the initial problem to a set of windows with potential conflict, but it might produce some "overly large" windows: ie., a window that has no conflict but would show one if narrowed.

Todo: (user): explore with using Theta-trees with a multi-valued energy value.

Implements operations_research::sat::PropagatorInterface.

Definition at line 507 of file cumulative_energy.cc.

◆ RegisterWith()

void operations_research::sat::CumulativeDualFeasibleEnergyConstraint::RegisterWith ( GenericLiteralWatcher * watcher )

Definition at line 421 of file cumulative_energy.cc.

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

ortools/sat/cumulative_energy.h
ortools/sat/cumulative_energy.cc