Detailed Description

Operator which moves a pair of nodes to another position where the first node of the pair must be before the second node on the same path.

Possible neighbors for the path 1 -> A -> B -> 2 -> 3 (where (1, 3) are first and last nodes of the path and can therefore not be moved, and (A, B) is a pair of nodes): 1 -> [A] -> 2 -> [B] -> 3 1 -> 2 -> [A] -> [B] -> 3 The pair can be moved to another path.

Definition at line 212 of file routing_neighborhoods.h.

Public Member Functions
	PairRelocateOperator (const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64_t)> start_empty_path_class, const RoutingIndexPairs &index_pairs)

	~PairRelocateOperator () override

bool	MakeNeighbor () override

std::string	DebugString () const override

void	Reset () override

bool	SkipUnchanged (int index) const override

int64_t	Next (int64_t node) const
	Returns the node after node in the current delta. More...

int64_t	Prev (int64_t node) const
	Returns the node before node in the current delta. More...

int64_t	Path (int64_t node) const
	Returns the index of the path to which node belongs in the current delta. More...

int	number_of_nexts () const
	Number of next variables. More...

bool	HoldsDelta () const override

void	Start (const Assignment *assignment) override
	This method should not be overridden. More...

virtual bool	IsIncremental () const

int	Size () const

int64_t	Value (int64_t index) const
	Returns the value in the current assignment of the variable of given index. More...

IntVar *	Var (int64_t index) const
	Returns the variable of given index. More...

int64_t	OldValue (int64_t index) const

int64_t	PrevValue (int64_t index) const

void	SetValue (int64_t index, int64_t value)

bool	Activated (int64_t index) const

void	Activate (int64_t index)

void	Deactivate (int64_t index)

bool	ApplyChanges (Assignment delta, Assignment deltadelta) const

void	RevertChanges (bool change_was_incremental)

void	AddVars (const std::vector< IntVar * > &vars)

bool	MakeNextNeighbor (Assignment delta, Assignment deltadelta) override
	OnStart() should really be protected, but then SWIG doesn't see it. More...

virtual const LocalSearchOperator *	Self () const

virtual bool	HasFragments () const

Protected Member Functions
bool	OnSamePathAsPreviousBase (int64_t base_index) override
	Returns true if a base node has to be on the same path as the "previous" base node (base node of index base_index - 1). More...

int64_t	GetBaseNodeRestartPosition (int base_index) override
	Returns the index of the node to which the base node of index base_index must be set to when it reaches the end of a path. More...

bool	ConsiderAlternatives (int64_t base_index) const override
	Indicates if alternatives should be considered when iterating over base nodes. More...

bool	MakeOneNeighbor () override
	This method should not be overridden. Override MakeNeighbor() instead. More...

virtual void	OnNodeInitialization ()
	Called by OnStart() after initializing node information. More...

int64_t	BaseNode (int i) const
	Returns the ith base node of the operator. More...

int	BaseAlternative (int i) const
	Returns the alternative for the ith base node. More...

int64_t	BaseAlternativeNode (int i) const
	Returns the alternative node for the ith base node. More...

int	BaseSiblingAlternative (int i) const
	Returns the alternative for the sibling of the ith base node. More...

int64_t	BaseSiblingAlternativeNode (int i) const
	Returns the alternative node for the sibling of the ith base node. More...

int64_t	StartNode (int i) const
	Returns the start node of the ith base node. More...

int64_t	EndNode (int i) const
	Returns the end node of the ith base node. More...

const std::vector< int64_t > &	path_starts () const
	Returns the vector of path start nodes. More...

int	PathClass (int i) const
	Returns the class of the path of the ith base node. More...

virtual void	SetNextBaseToIncrement (int64_t base_index)
	Set the next base to increment on next iteration. More...

int64_t	OldNext (int64_t node) const

int64_t	PrevNext (int64_t node) const

int64_t	OldPrev (int64_t node) const

int64_t	OldPath (int64_t node) const

bool	MoveChain (int64_t before_chain, int64_t chain_end, int64_t destination)
	Moves the chain starting after the node before_chain and ending at the node chain_end after the node destination. More...

bool	ReverseChain (int64_t before_chain, int64_t after_chain, int64_t *chain_last)
	Reverses the chain starting after before_chain and ending before after_chain. More...

bool	MakeActive (int64_t node, int64_t destination)
	Insert the inactive node after destination. More...

bool	MakeChainInactive (int64_t before_chain, int64_t chain_end)
	Makes the nodes on the chain starting after before_chain and ending at chain_end inactive. More...

bool	SwapActiveAndInactive (int64_t active, int64_t inactive)
	Replaces active by inactive in the current path, making active inactive. More...

void	SetNext (int64_t from, int64_t to, int64_t path)
	Sets 'to' to be the node after 'from' on the given path. More...

bool	IsPathEnd (int64_t node) const
	Returns true if node is the last node on the path; defined by the fact that node is outside the range of the variable array. More...

bool	IsPathStart (int64_t node) const
	Returns true if node is the first node on the path. More...

bool	IsInactive (int64_t node) const
	Returns true if node is inactive. More...

virtual bool	InitPosition () const
	Returns true if the operator needs to restart its initial position at each call to Start() More...

void	ResetPosition ()
	Reset the position of the operator to its position when Start() was last called; this can be used to let an operator iterate more than once over the paths. More...

int	AddAlternativeSet (const std::vector< int64_t > &alternative_set)
	Handling node alternatives. More...

void	AddPairAlternativeSets (const std::vector< std::pair< std::vector< int64_t >, std::vector< int64_t >>> &pair_alternative_sets)
	Adds all sets of node alternatives of a vector of alternative pairs. More...

int64_t	GetActiveInAlternativeSet (int alternative_index) const
	Returns the active node in the given alternative set. More...

int64_t	GetActiveAlternativeNode (int node) const
	Returns the active node in the alternative set of the given node. More...

int	GetSiblingAlternativeIndex (int node) const
	Returns the index of the alternative set of the sibling of node. More...

int64_t	GetActiveAlternativeSibling (int node) const
	Returns the active node in the alternative set of the sibling of the given node. More...

bool	CheckChainValidity (int64_t before_chain, int64_t chain_end, int64_t exclude) const
	Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not contain exclude. More...

int64_t	InverseValue (int64_t index) const

int64_t	OldInverseValue (int64_t index) const

void	AddToAssignment (IntVar var, int64_t value, bool active, std::vector< int > assignment_indices, int64_t index, Assignment *assignment) const

Protected Attributes
const int	number_of_nexts_

const bool	ignore_path_vars_

int	next_base_to_increment_

int	num_paths_ = 0

std::vector< int64_t >	start_to_path_

Constructor & Destructor Documentation

◆ PairRelocateOperator()

PairRelocateOperator	(	const std::vector< IntVar * > &	vars,
		const std::vector< IntVar * > &	secondary_vars,
		std::function< int(int64_t)>	start_empty_path_class,
		const RoutingIndexPairs &	index_pairs
	)

Definition at line 314 of file routing_neighborhoods.cc.

◆ ~PairRelocateOperator()

~PairRelocateOperator ( )

inlineoverride

Definition at line 218 of file routing_neighborhoods.h.

Member Function Documentation

◆ Activate()

void Activate ( int64_t index )

inlineinherited

Definition at line 1111 of file constraint_solveri.h.

◆ Activated()

bool Activated ( int64_t index ) const

inlineinherited

Definition at line 1108 of file constraint_solveri.h.

◆ AddAlternativeSet()

int AddAlternativeSet ( const std::vector< int64_t > & alternative_set )

inlineprotectedinherited

Handling node alternatives.

Adds a set of node alternatives to the neighborhood. No node can be in two altrnatives.

Definition at line 1512 of file constraint_solveri.h.

◆ AddPairAlternativeSets()

void AddPairAlternativeSets ( const std::vector< std::pair< std::vector< int64_t >, std::vector< int64_t >>> & pair_alternative_sets )

inlineprotectedinherited

Adds all sets of node alternatives of a vector of alternative pairs.

No node can be in two altrnatives.

Definition at line 1525 of file constraint_solveri.h.

◆ AddToAssignment()

void AddToAssignment	(	IntVar *	var,
		int64_t	value,
		bool	active,
		std::vector< int > *	assignment_indices,
		int64_t	index,
		Assignment *	assignment
	)		const

inlineprotectedinherited

Definition at line 1188 of file constraint_solveri.h.

◆ AddVars()

void AddVars ( const std::vector< IntVar * > & vars )

inlineinherited

Definition at line 1149 of file constraint_solveri.h.

◆ ApplyChanges()

bool ApplyChanges	(	Assignment *	delta,
		Assignment *	deltadelta
	)		const

inlineinherited

Definition at line 1114 of file constraint_solveri.h.

◆ BaseAlternative()

int BaseAlternative ( int i ) const

inlineprotectedinherited

Returns the alternative for the ith base node.

Definition at line 1375 of file constraint_solveri.h.

◆ BaseAlternativeNode()

int64_t BaseAlternativeNode ( int i ) const

inlineprotectedinherited

Returns the alternative node for the ith base node.

Definition at line 1377 of file constraint_solveri.h.

◆ BaseNode()

int64_t BaseNode ( int i ) const

inlineprotectedinherited

Returns the ith base node of the operator.

Definition at line 1373 of file constraint_solveri.h.

◆ BaseSiblingAlternative()

int BaseSiblingAlternative ( int i ) const

inlineprotectedinherited

Returns the alternative for the sibling of the ith base node.

Definition at line 1385 of file constraint_solveri.h.

◆ BaseSiblingAlternativeNode()

int64_t BaseSiblingAlternativeNode ( int i ) const

inlineprotectedinherited

Returns the alternative node for the sibling of the ith base node.

Definition at line 1389 of file constraint_solveri.h.

◆ CheckChainValidity()

bool CheckChainValidity	(	int64_t	before_chain,
		int64_t	chain_end,
		int64_t	exclude
	)		const

protectedinherited

Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not contain exclude.

Definition at line 851 of file local_search.cc.

◆ ConsiderAlternatives()

bool ConsiderAlternatives ( int64_t base_index ) const

inlineoverrideprotectedvirtual

Indicates if alternatives should be considered when iterating over base nodes.

Reimplemented from PathOperator.

Definition at line 230 of file routing_neighborhoods.h.

◆ Deactivate()

void Deactivate ( int64_t index )

inlineinherited

Definition at line 1112 of file constraint_solveri.h.

◆ DebugString()

std::string DebugString ( ) const

inlineoverridevirtual

Reimplemented from BaseObject.

Definition at line 221 of file routing_neighborhoods.h.

◆ EndNode()

int64_t EndNode ( int i ) const

inlineprotectedinherited

Returns the end node of the ith base node.

Definition at line 1401 of file constraint_solveri.h.

◆ GetActiveAlternativeNode()

int64_t GetActiveAlternativeNode ( int node ) const

inlineprotectedinherited

Returns the active node in the alternative set of the given node.

Definition at line 1542 of file constraint_solveri.h.

◆ GetActiveAlternativeSibling()

int64_t GetActiveAlternativeSibling ( int node ) const

inlineprotectedinherited

Returns the active node in the alternative set of the sibling of the given node.

Definition at line 1553 of file constraint_solveri.h.

◆ GetActiveInAlternativeSet()

int64_t GetActiveInAlternativeSet ( int alternative_index ) const

inlineprotectedinherited

Returns the active node in the given alternative set.

Definition at line 1536 of file constraint_solveri.h.

◆ GetBaseNodeRestartPosition()

int64_t GetBaseNodeRestartPosition ( int base_index )

overrideprotectedvirtual

Returns the index of the node to which the base node of index base_index must be set to when it reaches the end of a path.

By default, it is set to the start of the current path. When this method is called, one can only assume that base nodes with indices < base_index have their final position.

Reimplemented from PathOperator.

Definition at line 373 of file routing_neighborhoods.cc.

◆ GetSiblingAlternativeIndex()

int GetSiblingAlternativeIndex ( int node ) const

inlineprotectedinherited

Returns the index of the alternative set of the sibling of node.

Definition at line 1546 of file constraint_solveri.h.

◆ HasFragments()

virtual bool HasFragments ( ) const

inlinevirtualinherited

Reimplemented in PathLns, and BaseLns.

Definition at line 922 of file constraint_solveri.h.

◆ HoldsDelta()

bool HoldsDelta ( ) const

inlineoverridevirtualinherited

Reimplemented from LocalSearchOperator.

Definition at line 1066 of file constraint_solveri.h.

◆ InitPosition()

virtual bool InitPosition ( ) const

inlineprotectedvirtualinherited

Returns true if the operator needs to restart its initial position at each call to Start()

Definition at line 1503 of file constraint_solveri.h.

◆ InverseValue()

int64_t InverseValue ( int64_t index ) const

inlineprotectedinherited

Definition at line 1181 of file constraint_solveri.h.

◆ IsInactive()

bool IsInactive ( int64_t node ) const

inlineprotectedinherited

Returns true if node is inactive.

Definition at line 1497 of file constraint_solveri.h.

◆ IsIncremental()

virtual bool IsIncremental ( ) const

inlinevirtualinherited

Reimplemented in TwoOpt.

Definition at line 1089 of file constraint_solveri.h.

◆ IsPathEnd()

bool IsPathEnd ( int64_t node ) const

inlineprotectedinherited

Returns true if node is the last node on the path; defined by the fact that node is outside the range of the variable array.

Definition at line 1491 of file constraint_solveri.h.

◆ IsPathStart()

bool IsPathStart ( int64_t node ) const

inlineprotectedinherited

Returns true if node is the first node on the path.

Definition at line 1494 of file constraint_solveri.h.

◆ MakeActive()

bool MakeActive	(	int64_t	node,
		int64_t	destination
	)

protectedinherited

Insert the inactive node after destination.

Definition at line 461 of file local_search.cc.

◆ MakeChainInactive()

bool MakeChainInactive	(	int64_t	before_chain,
		int64_t	chain_end
	)

protectedinherited

Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.

Definition at line 471 of file local_search.cc.

◆ MakeNeighbor()

bool MakeNeighbor ( )

overridevirtual

Implements PathOperator.

Definition at line 324 of file routing_neighborhoods.cc.

◆ MakeNextNeighbor()

bool MakeNextNeighbor	(	Assignment *	delta,
		Assignment *	deltadelta
	)

overridevirtualinherited

OnStart() should really be protected, but then SWIG doesn't see it.

So we make it public, but only subclasses should access to it (to override it). Redefines MakeNextNeighbor to export a simpler interface. The calls to ApplyChanges() and RevertChanges() are factored in this method, hiding both delta and deltadelta from subclasses which only need to override MakeOneNeighbor(). Therefore this method should not be overridden. Override MakeOneNeighbor() instead.

Implements LocalSearchOperator.

Reimplemented in PairNodeSwapActiveOperator< swap_first >, IndexPairSwapActiveOperator, and SwapIndexPairOperator.

Definition at line 79 of file local_search.cc.

◆ MakeOneNeighbor()

bool MakeOneNeighbor ( )

overrideprotectedvirtualinherited

This method should not be overridden. Override MakeNeighbor() instead.

Reimplemented from IntVarLocalSearchOperator.

Reimplemented in RelocateExpensiveChain, MakePairActiveOperator, TSPLns, and BaseInactiveNodeToPathOperator.

Definition at line 391 of file local_search.cc.

◆ MoveChain()

bool MoveChain	(	int64_t	before_chain,
		int64_t	chain_end,
		int64_t	destination
	)

protectedinherited

Moves the chain starting after the node before_chain and ending at the node chain_end after the node destination.

Definition at line 415 of file local_search.cc.

◆ Next()

int64_t Next ( int64_t node ) const

inlineinherited

Returns the node after node in the current delta.

Definition at line 1343 of file constraint_solveri.h.

◆ number_of_nexts()

int number_of_nexts ( ) const

inlineinherited

Number of next variables.

Definition at line 1362 of file constraint_solveri.h.

◆ OldInverseValue()

int64_t OldInverseValue ( int64_t index ) const

inlineprotectedinherited

Definition at line 1184 of file constraint_solveri.h.

◆ OldNext()

int64_t OldNext ( int64_t node ) const

inlineprotectedinherited

Definition at line 1443 of file constraint_solveri.h.

◆ OldPath()

int64_t OldPath ( int64_t node ) const

inlineprotectedinherited

Definition at line 1458 of file constraint_solveri.h.

◆ OldPrev()

int64_t OldPrev ( int64_t node ) const

inlineprotectedinherited

Definition at line 1453 of file constraint_solveri.h.

◆ OldValue()

int64_t OldValue ( int64_t index ) const

inlineinherited

Definition at line 1101 of file constraint_solveri.h.

◆ OnNodeInitialization()

virtual void OnNodeInitialization ( )

inlineprotectedvirtualinherited

Called by OnStart() after initializing node information.

Should be overridden instead of OnStart() to avoid calling PathOperator::OnStart explicitly.

Definition at line 1370 of file constraint_solveri.h.

◆ OnSamePathAsPreviousBase()

bool OnSamePathAsPreviousBase ( int64_t base_index )

inlineoverrideprotectedvirtual

Returns true if a base node has to be on the same path as the "previous" base node (base node of index base_index - 1).

Useful to limit neighborhood exploration to nodes on the same path. it's currently way more complicated to implement.

Both destination nodes must be on the same path.

Reimplemented from PathOperator.

Definition at line 224 of file routing_neighborhoods.h.

◆ Path()

int64_t Path ( int64_t node ) const

inlineinherited

Returns the index of the path to which node belongs in the current delta.

Only returns a valid value if path variables are taken into account.

Definition at line 1357 of file constraint_solveri.h.

◆ path_starts()

const std::vector<int64_t>& path_starts ( ) const

inlineprotectedinherited

Returns the vector of path start nodes.

Definition at line 1403 of file constraint_solveri.h.

◆ PathClass()

int PathClass ( int i ) const

inlineprotectedinherited

Returns the class of the path of the ith base node.

Definition at line 1405 of file constraint_solveri.h.

◆ Prev()

int64_t Prev ( int64_t node ) const

inlineinherited

Returns the node before node in the current delta.

Definition at line 1349 of file constraint_solveri.h.

◆ PrevNext()

int64_t PrevNext ( int64_t node ) const

inlineprotectedinherited

Definition at line 1448 of file constraint_solveri.h.

◆ PrevValue()

int64_t PrevValue ( int64_t index ) const

inlineinherited

Definition at line 1102 of file constraint_solveri.h.

◆ Reset()

void Reset ( )

overridevirtualinherited

Reimplemented from LocalSearchOperator.

Definition at line 382 of file local_search.cc.

◆ ResetPosition()

void ResetPosition ( )

inlineprotectedinherited

Reset the position of the operator to its position when Start() was last called; this can be used to let an operator iterate more than once over the paths.

Definition at line 1507 of file constraint_solveri.h.

◆ ReverseChain()

bool ReverseChain	(	int64_t	before_chain,
		int64_t	after_chain,
		int64_t *	chain_last
	)

protectedinherited

Reverses the chain starting after before_chain and ending before after_chain.

Definition at line 438 of file local_search.cc.

◆ RevertChanges()

void RevertChanges ( bool change_was_incremental )

inlineinherited

Definition at line 1138 of file constraint_solveri.h.

◆ Self()

virtual const LocalSearchOperator* Self ( ) const

inlinevirtualinherited

Definition at line 920 of file constraint_solveri.h.

◆ SetNext()

void SetNext	(	int64_t	from,
		int64_t	to,
		int64_t	path
	)

inlineprotectedinherited

Sets 'to' to be the node after 'from' on the given path.

Definition at line 1480 of file constraint_solveri.h.

◆ SetNextBaseToIncrement()

virtual void SetNextBaseToIncrement ( int64_t base_index )

inlineprotectedvirtualinherited

Set the next base to increment on next iteration.

All base > base_index will be reset to their start value.

Definition at line 1436 of file constraint_solveri.h.

◆ SetValue()

void SetValue	(	int64_t	index,
		int64_t	value
	)

inlineinherited

Definition at line 1105 of file constraint_solveri.h.

◆ Size()

int Size ( ) const

inlineinherited

Definition at line 1091 of file constraint_solveri.h.

◆ SkipUnchanged()

bool SkipUnchanged ( int index ) const

overridevirtualinherited

Reimplemented from IntVarLocalSearchOperator.

Definition at line 403 of file local_search.cc.

◆ Start()

void Start ( const Assignment * assignment )

inlineoverridevirtualinherited

This method should not be overridden.

Override OnStart() instead which is called before exiting this method.

Implements LocalSearchOperator.

Definition at line 1069 of file constraint_solveri.h.

◆ StartNode()

int64_t StartNode ( int i ) const

inlineprotectedinherited

Returns the start node of the ith base node.

Definition at line 1399 of file constraint_solveri.h.

◆ SwapActiveAndInactive()

bool SwapActiveAndInactive	(	int64_t	active,
		int64_t	inactive
	)

protectedinherited

Replaces active by inactive in the current path, making active inactive.

Definition at line 488 of file local_search.cc.

◆ Value()

int64_t Value ( int64_t index ) const

inlineinherited

Returns the value in the current assignment of the variable of given index.

Definition at line 1094 of file constraint_solveri.h.

◆ Var()

IntVar* Var ( int64_t index ) const

inlineinherited

Returns the variable of given index.

Definition at line 1099 of file constraint_solveri.h.

Member Data Documentation

◆ ignore_path_vars_

const bool ignore_path_vars_

protectedinherited

Definition at line 1566 of file constraint_solveri.h.

◆ next_base_to_increment_

int next_base_to_increment_

protectedinherited

Definition at line 1567 of file constraint_solveri.h.

◆ num_paths_

int num_paths_ = 0

protectedinherited

Definition at line 1568 of file constraint_solveri.h.

◆ number_of_nexts_

const int number_of_nexts_

protectedinherited

Definition at line 1565 of file constraint_solveri.h.

◆ start_to_path_

std::vector<int64_t> start_to_path_

protectedinherited

Definition at line 1569 of file constraint_solveri.h.

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

Detailed Description

Public Member Functions

Protected Member Functions

Protected Attributes

Constructor & Destructor Documentation

◆ PairRelocateOperator()

◆ ~PairRelocateOperator()

Member Function Documentation

◆ Activate()

◆ Activated()

◆ AddAlternativeSet()

◆ AddPairAlternativeSets()

◆ AddToAssignment()

◆ AddVars()

◆ ApplyChanges()

◆ BaseAlternative()

◆ BaseAlternativeNode()

◆ BaseNode()

◆ BaseSiblingAlternative()

◆ BaseSiblingAlternativeNode()

◆ CheckChainValidity()

◆ ConsiderAlternatives()

◆ Deactivate()

◆ DebugString()

◆ EndNode()

◆ GetActiveAlternativeNode()

◆ GetActiveAlternativeSibling()

◆ GetActiveInAlternativeSet()

◆ GetBaseNodeRestartPosition()

◆ GetSiblingAlternativeIndex()

◆ HasFragments()

◆ HoldsDelta()

◆ InitPosition()

◆ InverseValue()

◆ IsInactive()

◆ IsIncremental()

◆ IsPathEnd()

◆ IsPathStart()

◆ MakeActive()

◆ MakeChainInactive()

◆ MakeNeighbor()

◆ MakeNextNeighbor()

◆ MakeOneNeighbor()

◆ MoveChain()

◆ Next()

◆ number_of_nexts()

◆ OldInverseValue()

◆ OldNext()

◆ OldPath()

◆ OldPrev()

◆ OldValue()

◆ OnNodeInitialization()

◆ OnSamePathAsPreviousBase()

◆ Path()

◆ path_starts()

◆ PathClass()

◆ Prev()

◆ PrevNext()

◆ PrevValue()

◆ Reset()

◆ ResetPosition()

◆ ReverseChain()

◆ RevertChanges()

◆ Self()

◆ SetNext()

◆ SetNextBaseToIncrement()

◆ SetValue()

◆ Size()

◆ SkipUnchanged()

◆ Start()

◆ StartNode()

◆ SwapActiveAndInactive()

◆ Value()

◆ Var()

Member Data Documentation

◆ ignore_path_vars_

◆ next_base_to_increment_

◆ num_paths_

◆ number_of_nexts_

◆ start_to_path_