operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator Class Reference

#include <diffn.h>

Inheritance diagram for operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator:

Public Member Functions
	NonOverlappingRectanglesDisjunctivePropagator (NoOverlap2DConstraintHelper *helper, Model *model)
	The slow_propagators select which disjunctive algorithms to propagate.
	~NonOverlappingRectanglesDisjunctivePropagator () override
bool	Propagate () final
void	Register (int fast_priority, int slow_priority)
Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default
virtual	~PropagatorInterface ()=default
virtual bool	IncrementalPropagate (const std::vector< int > &)

Detailed Description

Non overlapping rectangles. This includes box with zero-areas. The following is forbidden:

• a point box inside a box with a non zero area
• a line box overlapping a box with a non zero area
• one vertical line box crossing an horizontal line box.

Definition at line 97 of file diffn.h.

Constructor & Destructor Documentation

NonOverlappingRectanglesDisjunctivePropagator()

operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator::NonOverlappingRectanglesDisjunctivePropagator	(	NoOverlap2DConstraintHelper *	helper,
		Model *	model )

The slow_propagators select which disjunctive algorithms to propagate.

Note

x_ and y_ must be initialized with enough intervals when passed to the disjunctive propagators.

Definition at line 560 of file diffn.cc.

~NonOverlappingRectanglesDisjunctivePropagator()

operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator::~NonOverlappingRectanglesDisjunctivePropagator ( )

overridedefault

Member Function Documentation

Propagate()

bool operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator::Propagate ( )

finalvirtual

Note

we optimized this function for two main use cases:

• smallish problem where we don't have more than 100 boxes.
• large problem with many 1000s boxes, but with only a small subset that is not fixed (mainly coming from LNS).

If we are "diving" we maintain the set of fixed boxes for which we know that they are not overlapping.

Note

the code assumes that this was registered twice in fast and slow mode. So we will not redo some propagation in slow mode that was already done by the fast mode.

We can actually swap dimensions to propagate vertically.

Implements operations_research::sat::PropagatorInterface.

Definition at line 818 of file diffn.cc.

Register()

void operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator::Register	(	int	fast_priority,
		int	slow_priority )

This propagator is the one making sure our propagation is complete, so we do need to make sure it is called again if it modified some bounds.

Definition at line 579 of file diffn.cc.

---

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

• ortools/sat/diffn.h
• ortools/sat/diffn.cc