operations_research::SymmetryManager Class Reference

-------— Symmetry Breaking -------— More...

Inheritance diagram for operations_research::SymmetryManager:

Public Member Functions
	SymmetryManager (Solver *const s, const std::vector< SymmetryBreaker * > &visitors)
	~SymmetryManager () override
void	EndNextDecision (DecisionBuilder *const, Decision *const d) override
	After calling DecisionBuilder::Next, along with the returned decision.
void	RefuteDecision (Decision *d) override
	Before refuting the decision.
void	CheckSymmetries (int index)
void	AddTermToClause (SymmetryBreaker *const visitor, IntVar *const term)
std::string	DebugString () const override
Public Member Functions inherited from operations_research::SearchMonitor
	SearchMonitor (Solver *const s)
	SearchMonitor (const SearchMonitor &)=delete
	This type is neither copyable nor movable.
SearchMonitor &	operator= (const SearchMonitor &)=delete
	~SearchMonitor () override
virtual void	EnterSearch ()
	Beginning of the search.
virtual void	RestartSearch ()
	Restart the search.
virtual void	ExitSearch ()
	End of the search.
virtual void	BeginNextDecision (DecisionBuilder *b)
	Before calling DecisionBuilder::Next.
virtual void	ApplyDecision (Decision *d)
	Before applying the decision.
virtual void	AfterDecision (Decision *d, bool apply)
virtual void	BeginFail ()
	Just when the failure occurs.
virtual void	EndFail ()
	After completing the backtrack.
virtual void	BeginInitialPropagation ()
	Before the initial propagation.
virtual void	EndInitialPropagation ()
	After the initial propagation.
virtual bool	AcceptSolution ()
virtual bool	AtSolution ()
virtual void	NoMoreSolutions ()
	When the search tree is finished.
virtual bool	LocalOptimum ()
virtual bool	AcceptDelta (Assignment *delta, Assignment *deltadelta)
virtual void	AcceptNeighbor ()
	After accepting a neighbor during local search.
virtual void	AcceptUncheckedNeighbor ()
	After accepting an unchecked neighbor during local search.
virtual bool	IsUncheckedSolutionLimitReached ()
virtual void	PeriodicCheck ()
	Periodic call to check limits in long running methods.
virtual int	ProgressPercent ()
virtual void	Accept (ModelVisitor *visitor) const
	Accepts the given model visitor.
virtual void	Install ()
	A search monitors adds itself on the active search.
Solver *	solver () const
Public Member Functions inherited from operations_research::BaseObject
	BaseObject ()
	BaseObject (const BaseObject &)=delete
	This type is neither copyable nor movable.
BaseObject &	operator= (const BaseObject &)=delete
virtual	~BaseObject ()

Additional Inherited Members
Static Public Attributes inherited from operations_research::SearchMonitor
static constexpr int	kNoProgress = -1
Protected Member Functions inherited from operations_research::SearchMonitor
void	ListenToEvent (Solver::MonitorEvent event)

Detailed Description

-------— Symmetry Breaking -------—

The symmetry manager maintains a list of problem symmetries. Each symmetry is called on each decision and should return a term representing the boolean status of the symmetrical decision. e.g. : the decision is x == 3, the symmetrical decision is y == 5 then the symmetry breaker should use AddIntegerVariableEqualValueClause(y, 5). Once this is done, upon refutation, for each symmetry breaker, the system adds a constraint that will forbid the symmetrical variation of the current explored search tree. This constraint can be expressed very simply just by keeping the list of current symmetrical decisions.

This is called Symmetry Breaking During Search (Ian Gent, Barbara Smith, ECAI 2000). http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3788&rep=rep1&type=pdf

Definition at line 5175 of file search.cc.

Constructor & Destructor Documentation

SymmetryManager()

operations_research::SymmetryManager::SymmetryManager ( Solver *const s, const std::vector< SymmetryBreaker * > & visitors )

inline

Definition at line 5177 of file search.cc.

~SymmetryManager()

operations_research::SymmetryManager::~SymmetryManager ( )

inlineoverride

Definition at line 5189 of file search.cc.

Member Function Documentation

AddTermToClause()

void operations_research::SymmetryManager::AddTermToClause ( SymmetryBreaker *const visitor, IntVar *const term )

inline

Definition at line 5252 of file search.cc.

CheckSymmetries()

void operations_research::SymmetryManager::CheckSymmetries ( int index )

inline

Todo

(user) : Improve speed, cache previous min and build them incrementally.

keep the last entry for later, if loop doesn't exit.

Premise is wrong. The clause will never apply.

Premise may be true. Adding to guard vector.

Given premises: xi = ai and a term y != b The following is equivalent to And(xi == a1) => y != b.

Definition at line 5215 of file search.cc.

DebugString()

std::string operations_research::SymmetryManager::DebugString ( ) const

inlineoverridevirtual

Reimplemented from operations_research::BaseObject.

Definition at line 5256 of file search.cc.

EndNextDecision()

void operations_research::SymmetryManager::EndNextDecision ( DecisionBuilder * const b, Decision *const d )

inlineoverridevirtual

After calling DecisionBuilder::Next, along with the returned decision.

Synchroneous push of decision as marker.

Reimplemented from operations_research::SearchMonitor.

Definition at line 5191 of file search.cc.

RefuteDecision()

void operations_research::SymmetryManager::RefuteDecision ( Decision * d )

inlineoverridevirtual

Before refuting the decision.

Reimplemented from operations_research::SearchMonitor.

Definition at line 5205 of file search.cc.

---

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

• ortools/constraint_solver/search.cc