operations_research::SymmetryManager Class Reference

Symmetry Breaking. More...

Inheritance diagram for operations_research::SymmetryManager:

List of all members.

Public Member Functions
	SymmetryManager (Solver *const s, SymmetryBreaker *const *visitors, int size)
virtual	~SymmetryManager ()
virtual void	EndNextDecision (DecisionBuilder *const db, Decision *const d)
	After calling DecisionBuilder::Next, along with the returned decision.
virtual void	RefuteDecision (Decision *d)
	Before refuting the Decision.
void	CheckSymmetries (int index)
void	AddTermToClause (SymmetryBreaker *const visitor, IntVar *const term)

---

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 ///< NOLINT

Definition at line 4462 of file search.cc.

---

Constructor & Destructor Documentation

operations_research::SymmetryManager::SymmetryManager	(	Solver *const	s,
		SymmetryBreaker *const *	visitors,
		int	size
	)			[inline]

Definition at line 4464 of file search.cc.

virtual operations_research::SymmetryManager::~SymmetryManager

(

)

[inline, virtual]

Definition at line 4480 of file search.cc.

---

Member Function Documentation

virtual void operations_research::SymmetryManager::EndNextDecision	(	DecisionBuilder *const	b,
		Decision *const	d
	)			[inline, virtual]

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

Reimplemented from operations_research::SearchMonitor.

Definition at line 4482 of file search.cc.

virtual void operations_research::SymmetryManager::RefuteDecision

(

Decision *

d

)

[inline, virtual]

Before refuting the Decision.

Reimplemented from operations_research::SearchMonitor.

Definition at line 4496 of file search.cc.

void operations_research::SymmetryManager::CheckSymmetries

(

int

index

)

[inline]

Todo:

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

Definition at line 4506 of file search.cc.

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

Definition at line 4543 of file search.cc.

---

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

• or-tools/src/constraint_solver/search.cc