#include <no_overlap_2d_helper.h>

Inheritance diagram for operations_research::sat::NoOverlap2DConstraintHelper:

Public Member Functions
	NoOverlap2DConstraintHelper (std::vector< AffineExpression > x_starts, std::vector< AffineExpression > x_ends, std::vector< AffineExpression > x_sizes, std::vector< LiteralIndex > x_reason_for_presence, std::vector< AffineExpression > y_starts, std::vector< AffineExpression > y_ends, std::vector< AffineExpression > y_sizes, std::vector< LiteralIndex > y_reason_for_presence, Model *model)

void	RegisterWith (GenericLiteralWatcher *watcher)

bool	SynchronizeAndSetDirection (bool x_is_forward_after_swap=true, bool y_is_forward_after_swap=true, bool swap_x_and_y=false)

bool	IsOptional (int index) const

bool	IsPresent (int index) const

bool	IsAbsent (int index) const

Rectangle	GetBoundingRectangle (int index) const

Rectangle	GetLevelZeroBoundingRectangle (int index) const

bool	IsFixed (int index) const

std::pair< IntegerValue, IntegerValue >	GetBoxSizesMax (int index) const

std::pair< IntegerValue, IntegerValue >	GetLevelZeroBoxSizesMin (int index) const

void	ClearReason ()

void	WatchAllBoxes (int id)

bool	PropagateRelativePosition (int first, int second, PairwiseRestriction::PairwiseRestrictionType type)

RectangleInRange	GetItemRangeForSizeMin (int index) const

ItemWithVariableSize	GetItemWithVariableSize (int index) const

bool	ReportConflictFromTwoBoxes (int box1, int box2)

bool	ReportConflictFromInfeasibleBoxRanges (absl::Span< const RectangleInRange > ranges)

void	AddXSizeMinReason (int index)

void	AddYSizeMinReason (int index)

void	AddSizeMinReason (int index)

void	AddLeftMinReason (int index, IntegerValue lower_bound)

void	AddLeftMaxReason (int index, IntegerValue upper_bound)

void	AddBottomMinReason (int index, IntegerValue lower_bound)

void	AddBottomMaxReason (int index, IntegerValue upper_bound)

void	AddPresenceReason (int index)

bool	IncreaseLeftMin (int index, IntegerValue new_lower_bound)

bool	ReportConflict ()

int	NumBoxes () const

bool	Propagate () override

SchedulingConstraintHelper &	x_helper () const

SchedulingConstraintHelper &	y_helper () const

SchedulingDemandHelper &	x_demands_helper ()

SchedulingDemandHelper &	y_demands_helper ()

const CompactVectorVector< int > &	connected_components () const

int64_t	InProcessingCount () const

int64_t	LastLevelZeroChangeIdx () const

Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default

virtual	~PropagatorInterface ()=default

virtual bool	IncrementalPropagate (const std::vector< int > &)

Detailed Description

Helper class shared by the propagators that handle no_overlap_2d constraints.

Having a helper class like this one makes much easier to do in-processing and to share pre-computed data between the two propagators.

Definition at line 38 of file no_overlap_2d_helper.h.

Constructor & Destructor Documentation

◆ NoOverlap2DConstraintHelper()

operations_research::sat::NoOverlap2DConstraintHelper::NoOverlap2DConstraintHelper	(	std::vector< AffineExpression >	x_starts,
		std::vector< AffineExpression >	x_ends,
		std::vector< AffineExpression >	x_sizes,
		std::vector< LiteralIndex >	x_reason_for_presence,
		std::vector< AffineExpression >	y_starts,
		std::vector< AffineExpression >	y_ends,
		std::vector< AffineExpression >	y_sizes,
		std::vector< LiteralIndex >	y_reason_for_presence,
		Model *	model )

inline

Definition at line 40 of file no_overlap_2d_helper.h.

Member Function Documentation

◆ AddBottomMaxReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddBottomMaxReason	(	int	index,
		IntegerValue	upper_bound )

inline

Push the explanation that the bottom edge of this box is to the bottom of the vertical line y=upper_bound.

Definition at line 196 of file no_overlap_2d_helper.h.

◆ AddBottomMinReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddBottomMinReason	(	int	index,
		IntegerValue	lower_bound )

inline

Push the explanation that the bottom edge of this box is to the top of the horizontal line y=lower_bound.

Definition at line 190 of file no_overlap_2d_helper.h.

◆ AddLeftMaxReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddLeftMaxReason	(	int	index,
		IntegerValue	upper_bound )

inline

Push the explanation that the left edge of this box is to the left of the vertical line x=upper_bound.

| <= | \/ <= | +------—|—+ | <= | | | <= | | +------—|—| |

Definition at line 184 of file no_overlap_2d_helper.h.

◆ AddLeftMinReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddLeftMinReason	(	int	index,
		IntegerValue	lower_bound )

inline

Push the explanation that the left edge of this box is to the right of the vertical line x=lower_bound.

| => | | => \/ | => +—+ | => | | | => +—+ |

Definition at line 170 of file no_overlap_2d_helper.h.

◆ AddPresenceReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddPresenceReason ( int index )

inline

Definition at line 200 of file no_overlap_2d_helper.h.

◆ AddSizeMinReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddSizeMinReason ( int index )

inline

Definition at line 156 of file no_overlap_2d_helper.h.

◆ AddXSizeMinReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddXSizeMinReason ( int index )

inline

Definition at line 154 of file no_overlap_2d_helper.h.

◆ AddYSizeMinReason()

void operations_research::sat::NoOverlap2DConstraintHelper::AddYSizeMinReason ( int index )

inline

Definition at line 155 of file no_overlap_2d_helper.h.

◆ ClearReason()

void operations_research::sat::NoOverlap2DConstraintHelper::ClearReason ( )

inline

Definition at line 113 of file no_overlap_2d_helper.h.

◆ connected_components()

const CompactVectorVector< int > & operations_research::sat::NoOverlap2DConstraintHelper::connected_components ( ) const

inline

Definition at line 227 of file no_overlap_2d_helper.h.

◆ GetBoundingRectangle()

Rectangle operations_research::sat::NoOverlap2DConstraintHelper::GetBoundingRectangle ( int index ) const

inline

Definition at line 84 of file no_overlap_2d_helper.h.

◆ GetBoxSizesMax()

std::pair< IntegerValue, IntegerValue > operations_research::sat::NoOverlap2DConstraintHelper::GetBoxSizesMax ( int index ) const

inline

Definition at line 103 of file no_overlap_2d_helper.h.

◆ GetItemRangeForSizeMin()

RectangleInRange operations_research::sat::NoOverlap2DConstraintHelper::GetItemRangeForSizeMin ( int index ) const

Returns a "fixed size projection" of the item of the item index. More precisely, returns item of index index with its sizes fixed to their minimum value alongside a bounding box that contains the item.

Definition at line 67 of file no_overlap_2d_helper.cc.

◆ GetItemWithVariableSize()

ItemWithVariableSize operations_research::sat::NoOverlap2DConstraintHelper::GetItemWithVariableSize ( int index ) const

Returns a {start_min, start_max, end_min, end_max} view of the item of the index index.

Definition at line 81 of file no_overlap_2d_helper.cc.

◆ GetLevelZeroBoundingRectangle()

Rectangle operations_research::sat::NoOverlap2DConstraintHelper::GetLevelZeroBoundingRectangle ( int index ) const

inline

Definition at line 91 of file no_overlap_2d_helper.h.

◆ GetLevelZeroBoxSizesMin()

std::pair< IntegerValue, IntegerValue > operations_research::sat::NoOverlap2DConstraintHelper::GetLevelZeroBoxSizesMin ( int index ) const

inline

Definition at line 107 of file no_overlap_2d_helper.h.

◆ IncreaseLeftMin()

bool operations_research::sat::NoOverlap2DConstraintHelper::IncreaseLeftMin	(	int	index,
		IntegerValue	new_lower_bound )

inline

Definition at line 205 of file no_overlap_2d_helper.h.

◆ InProcessingCount()

int64_t operations_research::sat::NoOverlap2DConstraintHelper::InProcessingCount ( ) const

inline

Definition at line 231 of file no_overlap_2d_helper.h.

◆ IsAbsent()

bool operations_research::sat::NoOverlap2DConstraintHelper::IsAbsent ( int index ) const

inline

Definition at line 80 of file no_overlap_2d_helper.h.

◆ IsFixed()

bool operations_research::sat::NoOverlap2DConstraintHelper::IsFixed ( int index ) const

inline

Definition at line 98 of file no_overlap_2d_helper.h.

◆ IsOptional()

bool operations_research::sat::NoOverlap2DConstraintHelper::IsOptional ( int index ) const

inline

Definition at line 72 of file no_overlap_2d_helper.h.

◆ IsPresent()

bool operations_research::sat::NoOverlap2DConstraintHelper::IsPresent ( int index ) const

inline

Definition at line 76 of file no_overlap_2d_helper.h.

◆ LastLevelZeroChangeIdx()

int64_t operations_research::sat::NoOverlap2DConstraintHelper::LastLevelZeroChangeIdx ( ) const

inline

Definition at line 232 of file no_overlap_2d_helper.h.

◆ NumBoxes()

int operations_research::sat::NoOverlap2DConstraintHelper::NumBoxes ( ) const

inline

Definition at line 215 of file no_overlap_2d_helper.h.

◆ Propagate()

bool operations_research::sat::NoOverlap2DConstraintHelper::Propagate ( )

overridevirtual

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.

Subtle: it is tempting to run this logic once for every connected component. However, this would be buggy, since the PresolveFixed2dRectangles() might grow a fixed box making it overlap with something on another component.

Implements operations_research::sat::PropagatorInterface.

Definition at line 318 of file no_overlap_2d_helper.cc.

◆ PropagateRelativePosition()

bool operations_research::sat::NoOverlap2DConstraintHelper::PropagateRelativePosition	(	int	first,
		int	second,
		PairwiseRestriction::PairwiseRestrictionType	type )

Propagate a relationship between two boxes (ie., first must be to the left of the second, etc).

Definition at line 194 of file no_overlap_2d_helper.cc.

◆ RegisterWith()

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

Definition at line 376 of file no_overlap_2d_helper.cc.

◆ ReportConflict()

bool operations_research::sat::NoOverlap2DConstraintHelper::ReportConflict ( )

inline

Definition at line 210 of file no_overlap_2d_helper.h.

◆ ReportConflictFromInfeasibleBoxRanges()

bool operations_research::sat::NoOverlap2DConstraintHelper::ReportConflictFromInfeasibleBoxRanges ( absl::Span< const RectangleInRange > ranges )

Reports a conflict due to a (potentially relaxed) infeasible subproblem of the no_overlap_2d constraint. More concretely, this function takes a list of fixed-size rectangles and their placement domains in ranges that satisfy:

the problem of placing all the rectangles in their domain is infeasible;
the x and y sizes of each box in ranges are smaller or equal than the corresponding current minimum sizes of the boxes;
for each range in ranges, range.box_index.bounding_box is fully contained inside GetItemRangeForSizeMin(range.box_index).bounding_box. In other terms, each element is infeasible in a domain at least as large as the current one.

Definition at line 122 of file no_overlap_2d_helper.cc.

◆ ReportConflictFromTwoBoxes()

bool operations_research::sat::NoOverlap2DConstraintHelper::ReportConflictFromTwoBoxes	(	int	box1,
		int	box2 )

If there is no possible placement for the two mandatory boxes (they will necessarily overlap), call this function to report this as a conflict. Returns true.

Definition at line 105 of file no_overlap_2d_helper.cc.

◆ SynchronizeAndSetDirection()

bool operations_research::sat::NoOverlap2DConstraintHelper::SynchronizeAndSetDirection	(	bool	x_is_forward_after_swap = true,
		bool	y_is_forward_after_swap = true,
		bool	swap_x_and_y = false )

Definition at line 36 of file no_overlap_2d_helper.cc.

◆ WatchAllBoxes()

void operations_research::sat::NoOverlap2DConstraintHelper::WatchAllBoxes ( int id )

inline

Definition at line 118 of file no_overlap_2d_helper.h.

◆ x_demands_helper()

SchedulingDemandHelper & operations_research::sat::NoOverlap2DConstraintHelper::x_demands_helper ( )

Definition at line 51 of file no_overlap_2d_helper.cc.

◆ x_helper()

SchedulingConstraintHelper & operations_research::sat::NoOverlap2DConstraintHelper::x_helper ( ) const

inline

Note: the helpers are only valid until the next call to Propagate().

Definition at line 221 of file no_overlap_2d_helper.h.

◆ y_demands_helper()

SchedulingDemandHelper & operations_research::sat::NoOverlap2DConstraintHelper::y_demands_helper ( )

Definition at line 59 of file no_overlap_2d_helper.cc.

◆ y_helper()

SchedulingConstraintHelper & operations_research::sat::NoOverlap2DConstraintHelper::y_helper ( ) const

inline

Definition at line 222 of file no_overlap_2d_helper.h.

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

ortools/sat/no_overlap_2d_helper.h
ortools/sat/no_overlap_2d_helper.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ NoOverlap2DConstraintHelper()

Member Function Documentation

◆ AddBottomMaxReason()

◆ AddBottomMinReason()

◆ AddLeftMaxReason()

◆ AddLeftMinReason()

◆ AddPresenceReason()

◆ AddSizeMinReason()

◆ AddXSizeMinReason()

◆ AddYSizeMinReason()

◆ ClearReason()

◆ connected_components()

◆ GetBoundingRectangle()

◆ GetBoxSizesMax()

◆ GetItemRangeForSizeMin()

◆ GetItemWithVariableSize()

◆ GetLevelZeroBoundingRectangle()

◆ GetLevelZeroBoxSizesMin()

◆ IncreaseLeftMin()

◆ InProcessingCount()

◆ IsAbsent()

◆ IsFixed()

◆ IsOptional()

◆ IsPresent()

◆ LastLevelZeroChangeIdx()

◆ NumBoxes()

◆ Propagate()

◆ PropagateRelativePosition()

◆ RegisterWith()

◆ ReportConflict()

◆ ReportConflictFromInfeasibleBoxRanges()

◆ ReportConflictFromTwoBoxes()

◆ SynchronizeAndSetDirection()

◆ WatchAllBoxes()

◆ x_demands_helper()

◆ x_helper()

◆ y_demands_helper()

◆ y_helper()