Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator Class Reference

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.

#include <diffn.h>

Inheritance diagram for operations_research::sat::NonOverlappingRectanglesDisjunctivePropagator:
operations_research::sat::PropagatorInterface

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 > &)

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 668 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 924 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 687 of file diffn.cc.

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