operations_research::sat::TryEdgeRectanglePropagator Class Reference

Exposed for testing. More...

#include <2d_try_edge_propagator.h>

Inheritance diagram for operations_research::sat::TryEdgeRectanglePropagator:

Public Member Functions
	TryEdgeRectanglePropagator (bool x_is_forward_after_swap, bool y_is_forward_after_swap, bool swap_x_and_y, NoOverlap2DConstraintHelper *helper, Model *model)
	~TryEdgeRectanglePropagator () override
bool	Propagate () final
int	RegisterWith (GenericLiteralWatcher *watcher)
Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default
virtual	~PropagatorInterface ()=default
virtual bool	IncrementalPropagate (const std::vector< int > &)

Protected Member Functions
virtual bool	ExplainAndPropagate (const std::vector< std::pair< int, std::optional< IntegerValue > > > &found_propagations)
std::vector< int >	GetMinimumProblemWithPropagation (int box_index, IntegerValue new_x_min)

Protected Attributes
std::vector< Rectangle >	placed_boxes_
std::vector< bool >	is_in_cache_
std::vector< Rectangle >	mandatory_regions_
std::vector< RectangleInRange >	active_box_ranges_
std::vector< bool >	is_active_
Bitset64< int >	has_mandatory_region_
std::vector< int >	changed_item_
std::vector< int >	changed_mandatory_

Detailed Description

Exposed for testing.

Definition at line 44 of file 2d_try_edge_propagator.h.

Constructor & Destructor Documentation

TryEdgeRectanglePropagator()

operations_research::sat::TryEdgeRectanglePropagator::TryEdgeRectanglePropagator ( bool x_is_forward_after_swap, bool y_is_forward_after_swap, bool swap_x_and_y, NoOverlap2DConstraintHelper * helper, Model * model )

inline

Definition at line 46 of file 2d_try_edge_propagator.h.

~TryEdgeRectanglePropagator()

operations_research::sat::TryEdgeRectanglePropagator::~TryEdgeRectanglePropagator ( )

override

Definition at line 47 of file 2d_try_edge_propagator.cc.

Member Function Documentation

ExplainAndPropagate()

bool operations_research::sat::TryEdgeRectanglePropagator::ExplainAndPropagate ( const std::vector< std::pair< int, std::optional< IntegerValue > > > & found_propagations )

protectedvirtual

Important: we also add to the reason the actual box we are changing the x_min. This is important, since we don't check if there are any feasible placement before its current x_min, so it needs to be part of the reason.

We don't need to add to the reason the x_max for the box we are pushing the x_min, except if we found a conflict.

Definition at line 358 of file 2d_try_edge_propagator.cc.

GetMinimumProblemWithPropagation()

std::vector< int > operations_research::sat::TryEdgeRectanglePropagator::GetMinimumProblemWithPropagation ( int box_index, IntegerValue new_x_min )

protected

This function assumes that a propagation is found and the box with index box_index cannot be placed to the left of new_x_min. It returns a list of indices of boxes that defines a subproblem where the propagation is still valid, including box_index itself.

We know that we can't place the box at x < new_x_min (which can be start_max for a conflict). The explanation for the propagation is complex: we tried a lot of positions, and each one overlaps with the mandatory part of at least one box. We want to find the smallest set of "conflicting boxes" that would still forbid every possible placement. To do that, we build a vector with, for each placement position, the list boxes that conflict when placing the box at that position. Then we solve (approximately) a set cover problem to find the smallest set of boxes that will still makes all positions conflicting.

We need to rerun the main propagator loop logic, but this time keeping track of which boxes conflicted for each position.

potential_y_positions is sorted, so we can stop here.

Now gather the data per box to make easier to use the set cover solver API.

Todo

(user): skip the boxes that are fixed at level zero. They do not contribute to the size of the explanation (so we shouldn't minimize their number) and make the SetCover problem harder to solve.

Todo

(user): We now know for each box the list of placements that it contributes to the conflict. We could use this information to relax the bounds of this box on the explanation of the propagation. For example, for a box that always overlaps at least five units to the right when it does, we could call AddStartMinReason(x_min - 4) instead of AddStartMinReason(x_min).

Definition at line 252 of file 2d_try_edge_propagator.cc.

Propagate()

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

Our algo is quadratic, so we don't want to run it on really large problems.

If a mandatory region is changed, we need to replace any cached box that now became overlapping with it.

potential_y_positions is sorted, so we can stop here.

We could not find any placement of the box at its current lower bound! Thus, we are sure we have something to propagate. Let's find the new lower bound (or a conflict). Note that the code below is much less performance critical than the code above, since it only triggers on propagations.

potential_x_positions is sorted, so the first we found is the lowest one.

Implements operations_research::sat::PropagatorInterface.

Definition at line 134 of file 2d_try_edge_propagator.cc.

RegisterWith()

int operations_research::sat::TryEdgeRectanglePropagator::RegisterWith

(

GenericLiteralWatcher *

watcher

)

Definition at line 40 of file 2d_try_edge_propagator.cc.

Member Data Documentation

active_box_ranges_

std::vector<RectangleInRange> operations_research::sat::TryEdgeRectanglePropagator::active_box_ranges_

protected

Definition at line 72 of file 2d_try_edge_propagator.h.

changed_item_

std::vector<int> operations_research::sat::TryEdgeRectanglePropagator::changed_item_

protected

Definition at line 76 of file 2d_try_edge_propagator.h.

changed_mandatory_

std::vector<int> operations_research::sat::TryEdgeRectanglePropagator::changed_mandatory_

protected

Definition at line 77 of file 2d_try_edge_propagator.h.

has_mandatory_region_

Bitset64<int> operations_research::sat::TryEdgeRectanglePropagator::has_mandatory_region_

protected

Definition at line 74 of file 2d_try_edge_propagator.h.

is_active_

std::vector<bool> operations_research::sat::TryEdgeRectanglePropagator::is_active_

protected

Definition at line 73 of file 2d_try_edge_propagator.h.

is_in_cache_

std::vector<bool> operations_research::sat::TryEdgeRectanglePropagator::is_in_cache_

protected

Definition at line 69 of file 2d_try_edge_propagator.h.

mandatory_regions_

std::vector<Rectangle> operations_research::sat::TryEdgeRectanglePropagator::mandatory_regions_

protected

Definition at line 71 of file 2d_try_edge_propagator.h.

placed_boxes_

std::vector<Rectangle> operations_research::sat::TryEdgeRectanglePropagator::placed_boxes_

protected

placed_boxes_ is a list that is only meaningful for indices for which is_in_cache_[box_index] is true. After applying this condition, placed_boxes_ contains a list of boxes placed at their current x_min and that does not overlap with the mandatory region of any other box in placed_boxes_. In other words, there is no point on looking for any propagation for this heuristic between boxes that are already in placed_boxes_.

Definition at line 68 of file 2d_try_edge_propagator.h.

---

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

• ortools/sat/2d_try_edge_propagator.h
• ortools/sat/2d_try_edge_propagator.cc