operations_research::sat::AllDifferentBoundsPropagator Class Reference

#include <all_different.h>

Inheritance diagram for operations_research::sat::AllDifferentBoundsPropagator:

Public Member Functions
	AllDifferentBoundsPropagator (absl::Span< const AffineExpression > expressions, IntegerTrail *integer_trail)
	AllDifferentBoundsPropagator (const AllDifferentBoundsPropagator &)=delete
	This type is neither copyable nor movable.
AllDifferentBoundsPropagator &	operator= (const AllDifferentBoundsPropagator &)=delete
bool	Propagate () final
void	RegisterWith (GenericLiteralWatcher *watcher)
Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default
virtual	~PropagatorInterface ()=default
virtual bool	IncrementalPropagate (const std::vector< int > &)

Detailed Description

Implements the all different bound consistent propagator with explanation. That is, given n affine expressions that must take different values, this propagates the bounds of each expression as much as possible. The key is to detect the so called Hall interval which are interval of size k that contains the domain of k expressinos. Because all the variables must take different values, we can deduce that the domain of the other variables cannot contains such Hall interval.

We use a "fast" O(n log n) algorithm.

Todo

(user): It might be difficult to find something faster than what is implemented here. Some related reference: https://cs.uwaterloo.ca/~vanbeek/Publications/ijcai03_TR.pdf

Definition at line 152 of file all_different.h.

Constructor & Destructor Documentation

AllDifferentBoundsPropagator() [1/2]

operations_research::sat::AllDifferentBoundsPropagator::AllDifferentBoundsPropagator	(	absl::Span< const AffineExpression >	expressions,
		IntegerTrail *	integer_trail )

We need +2 for sentinels.

Definition at line 418 of file all_different.cc.

AllDifferentBoundsPropagator() [2/2]

operations_research::sat::AllDifferentBoundsPropagator::AllDifferentBoundsPropagator ( const AllDifferentBoundsPropagator & )

delete

This type is neither copyable nor movable.

Member Function Documentation

operator=()

AllDifferentBoundsPropagator & operations_research::sat::AllDifferentBoundsPropagator::operator= ( const AllDifferentBoundsPropagator & )

delete

Propagate()

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

Note

it is not required to swap back bounds_ and negated_bounds_.

Todo

(user): investigate the impact.

Implements operations_research::sat::PropagatorInterface.

Definition at line 436 of file all_different.cc.

RegisterWith()

void operations_research::sat::AllDifferentBoundsPropagator::RegisterWith

(

GenericLiteralWatcher *

watcher

)

Definition at line 637 of file all_different.cc.

---

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

• ortools/sat/all_different.h
• ortools/sat/all_different.cc