operations_research::sat::ProbingRectangle Class Reference

#include <diffn_util.h>

Public Types
enum	Edge { TOP = 0 , LEFT = 1 , BOTTOM = 2 , RIGHT = 3 }
enum	Direction { LEFT_AND_RIGHT = 0 , TOP_AND_BOTTOM = 1 }

Public Member Functions
	ProbingRectangle (const std::vector< RectangleInRange > &intervals)
	It will initialize with the bounding box of the whole set.
void	Reset ()
	Reset to the bounding box of the whole set.
void	Shrink (Edge edge)
bool	CanShrink (Edge edge) const
bool	IsMinimal () const
void	ValidateInvariants () const
IntegerValue	GetShrinkDeltaEnergy (Edge edge) const
	How much of GetMinimumEnergy() will change if Shrink() is called.
IntegerValue	GetShrinkDeltaArea (Edge edge) const
	How much of GetCurrentRectangleArea() will change if Shrink() is called.
Rectangle	GetCurrentRectangle () const
IntegerValue	GetCurrentRectangleArea () const
IntegerValue	GetMinimumEnergy () const
const std::vector< RectangleInRange > &	Intervals () const

Detailed Description

Cheaply test several increasingly smaller rectangles for energy conflict. More precisely, each call to Shrink() cost O(k + n) operations, where k is the number of points that shrinking the probing rectangle will cross and n is the number of items which are in a range that overlaps the probing rectangle in both sides in the dimension that is getting shrinked. When calling repeatedely Shrink() until the probing rectangle collapse into a single point, the O(k) component adds up to a O(M) cost, where M is the number of items. This means this procedure is linear in time if the ranges of the items are small.

The energy is defined as the minimum occupied area inside the probing rectangle. For more details, see Clautiaux, François, et al. "A new constraint programming approach for the orthogonal packing problem." Computers & Operations Research 35.3 (2008): 944-959.

This is used by FindRectanglesWithEnergyConflictMC() below.

Definition at line 489 of file diffn_util.h.

Member Enumeration Documentation

Direction

enum operations_research::sat::ProbingRectangle::Direction

Enumerator
LEFT_AND_RIGHT
TOP_AND_BOTTOM

Definition at line 535 of file diffn_util.h.

Edge

enum operations_research::sat::ProbingRectangle::Edge

Enumerator
TOP
LEFT
BOTTOM
RIGHT

Definition at line 494 of file diffn_util.h.

Constructor & Destructor Documentation

ProbingRectangle()

operations_research::sat::ProbingRectangle::ProbingRectangle ( const std::vector< RectangleInRange > & intervals )

explicit

It will initialize with the bounding box of the whole set.

Add four bogus points in the extremities so we can delegate setting up all internal state to Shrink().

Definition at line 778 of file diffn_util.cc.

Member Function Documentation

CanShrink()

bool operations_research::sat::ProbingRectangle::CanShrink

(

Edge

edge

)

const

Definition at line 1461 of file diffn_util.cc.

GetCurrentRectangle()

Rectangle operations_research::sat::ProbingRectangle::GetCurrentRectangle

(

)

const

Definition at line 896 of file diffn_util.cc.

GetCurrentRectangleArea()

IntegerValue operations_research::sat::ProbingRectangle::GetCurrentRectangleArea ( ) const

inline

Definition at line 526 of file diffn_util.h.

GetMinimumEnergy()

IntegerValue operations_research::sat::ProbingRectangle::GetMinimumEnergy ( ) const

inline

This is equivalent of, for every item:

• Call GetMinimumIntersectionArea() with GetCurrentRectangle().
• Return the total sum of the areas.

Definition at line 531 of file diffn_util.h.

GetShrinkDeltaArea()

IntegerValue operations_research::sat::ProbingRectangle::GetShrinkDeltaArea

(

Edge

edge

)

const

How much of GetCurrentRectangleArea() will change if Shrink() is called.

Definition at line 1350 of file diffn_util.cc.

GetShrinkDeltaEnergy()

IntegerValue operations_research::sat::ProbingRectangle::GetShrinkDeltaEnergy ( Edge edge ) const

inline

How much of GetMinimumEnergy() will change if Shrink() is called.

Definition at line 518 of file diffn_util.h.

Intervals()

const std::vector< RectangleInRange > & operations_research::sat::ProbingRectangle::Intervals ( ) const

inline

Definition at line 533 of file diffn_util.h.

IsMinimal()

bool operations_research::sat::ProbingRectangle::IsMinimal ( ) const

inline

We only need to know if there is slack on both dimensions. Actually CanShrink(BOTTOM) == CanShrink(TOP) and conversely.

Definition at line 507 of file diffn_util.h.

Reset()

void operations_research::sat::ProbingRectangle::Reset

(

)

Reset to the bounding box of the whole set.

Remove the four bogus points we added.

Definition at line 868 of file diffn_util.cc.

Shrink()

void operations_research::sat::ProbingRectangle::Shrink

(

Edge

edge

)

Shrink the rectangle by moving one of its four edges to the next "interesting" value. The interesting values for x or y are the ones that correspond to a boundary, ie., a value that corresponds to one of {min, min + size, max - size, max} of a rectangle.

Definition at line 1333 of file diffn_util.cc.

ValidateInvariants()

void operations_research::sat::ProbingRectangle::ValidateInvariants

(

)

const

Test-only method that check that all internal incremental counts are correct by comparing with recalculating them from scratch.

NOMUTANTS – This is a sanity check, it is hard to corrupt the data in an unit test to check it will fail.

We account separately for the problematic items that touches both sides.

Definition at line 935 of file diffn_util.cc.

---

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

• ortools/sat/diffn_util.h
• ortools/sat/diffn_util.cc