operations_research::PathOperator Class Reference

Path-based Operators. More...

#include <constraint_solveri.h>

Inheritance diagram for operations_research::PathOperator:

List of all members.

Public Member Functions

PathOperator (const IntVar *const *next_vars, const IntVar *const *path_vars, int size, int number_of_base_nodes)

namespace

virtual ~PathOperator ()

virtual bool MakeNeighbor ()=0

virtual bool SkipUnchanged (int index) const

int64 Next (int64 node_index) const

Returns the index of the node after the node of index node_index in the current assignment.

int64 Path (int64 node_index) const

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

int number_of_nexts () const

Number of next variables.

Protected Member Functions

virtual bool MakeOneNeighbor ()

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

int64 BaseNode (int i) const

Returns the index of the variable corresponding to the ith base node.

int64 StartNode (int i) const

Returns the index of the variable corresponding to the current path of the ith base node.

virtual bool RestartAtPathStartOnSynchronize ()

When the operator is being synchronized with a new solution (when Start() is called), returns true to restart the exploration of the neighborhood from the start of the last paths explored; returns false to restart the exploration at the last nodes visited.

virtual bool OnSamePathAsPreviousBase (int64 base_index)

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).

virtual int64 GetBaseNodeRestartPosition (int base_index)

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.

int64 OldNext (int64 node_index) const

int64 OldPath (int64 node_index) const

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

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

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

Reverses the chain starting after before_chain and ending before after_chain.

bool MakeActive (int64 node, int64 destination)

bool MakeChainInactive (int64 before_chain, int64 chain_end)

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

Sets the to to be the node after from.

bool IsPathEnd (int64 i) const

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

bool IsInactive (int64 i) const

Returns true if node is inactive.

virtual bool InitPosition () const

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

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.

Protected Attributes

const int number_of_nexts_

const bool ignore_path_vars_

Detailed Description

Path-based Operators.

Base class of the local search operators dedicated to path modifications (a path is a set of nodes linked together by arcs). This family of neighborhoods supposes they are handling next variables representing the arcs (var[i] represents the node immediately after i on a path). Several services are provided:

arc manipulators (SetNext(), ReverseChain(), MoveChain())
path inspectors (Next(), IsPathEnd())
path iterators: operators need a given number of nodes to define a neighbor; this class provides the iteration on a given number of (base) nodes which can be used to define a neighbor (through the BaseNode method) Subclasses only need to override MakeNeighbor to create neighbors using the services above (no direct manipulation of assignments).

Definition at line 1013 of file constraint_solveri.h.

Constructor & Destructor Documentation

operations_research::PathOperator::PathOperator	(	const IntVar const	next_vars,
		const IntVar const	path_vars,
		int	size,
		int	number_of_base_nodes
	)

namespace

Path-based Operators

Definition at line 636 of file local_search.cc.

virtual operations_research::PathOperator::~PathOperator ( ) [inline, virtual]

Definition at line 1019 of file constraint_solveri.h.

Member Function Documentation

virtual bool operations_research::PathOperator::MakeNeighbor ( ) [pure virtual]

Implemented in operations_research::MakePairActiveOperator, and operations_research::PairRelocateOperator.

bool operations_research::PathOperator::SkipUnchanged ( int index ) const [virtual]

Todo:: TODO(user): Make the following methods protected.

Reimplemented from operations_research::IntVarLocalSearchOperator.

Definition at line 670 of file local_search.cc.

int64 operations_research::PathOperator::Next ( int64 node_index ) const [inline]

Returns the index of the node after the node of index node_index in the current assignment.

Definition at line 1027 of file constraint_solveri.h.

int64 operations_research::PathOperator::Path ( int64 node_index ) const [inline]

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

Definition at line 1034 of file constraint_solveri.h.

int operations_research::PathOperator::number_of_nexts ( ) const [inline]

Number of next variables.

Definition at line 1039 of file constraint_solveri.h.

bool operations_research::PathOperator::MakeOneNeighbor ( ) [protected, virtual]

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

Reimplemented from operations_research::IntVarLocalSearchOperator.

Definition at line 658 of file local_search.cc.

int64 operations_research::PathOperator::BaseNode ( int i ) const [inline, protected]

Returns the index of the variable corresponding to the ith base node.

Definition at line 1046 of file constraint_solveri.h.

int64 operations_research::PathOperator::StartNode ( int i ) const [inline, protected]

Returns the index of the variable corresponding to the current path of the ith base node.

Definition at line 1049 of file constraint_solveri.h.

virtual bool operations_research::PathOperator::RestartAtPathStartOnSynchronize ( ) [inline, protected, virtual]

When the operator is being synchronized with a new solution (when Start() is called), returns true to restart the exploration of the neighborhood from the start of the last paths explored; returns false to restart the exploration at the last nodes visited.

This is used to avoid restarting on base nodes which have changed paths, leading to potentially skipping neighbors.

Todo:: TODO(user): remove this when automatic detection of such cases in done.

Definition at line 1058 of file constraint_solveri.h.

virtual bool operations_research::PathOperator::OnSamePathAsPreviousBase ( int64 base_index ) [inline, protected, virtual]

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.

Todo:: TODO(user): ideally this should be OnSamePath(int64 node1, int64 node2); it's currently way more complicated to implement.

Reimplemented in operations_research::MakePairActiveOperator, and operations_research::PairRelocateOperator.

Definition at line 1066 of file constraint_solveri.h.

virtual int64 operations_research::PathOperator::GetBaseNodeRestartPosition ( int base_index ) [inline, protected, virtual]

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 in operations_research::MakePairActiveOperator, and operations_research::PairRelocateOperator.

Definition at line 1074 of file constraint_solveri.h.

int64 operations_research::PathOperator::OldNext ( int64 node_index ) const [inline, protected]

Definition at line 1078 of file constraint_solveri.h.

int64 operations_research::PathOperator::OldPath ( int64 node_index ) const [inline, protected]

Definition at line 1083 of file constraint_solveri.h.

bool operations_research::PathOperator::MoveChain	(	int64	before_chain,
		int64	chain_end,
		int64	destination
	)			`[protected]`

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

Definition at line 683 of file local_search.cc.

bool operations_research::PathOperator::ReverseChain	(	int64	before_chain,
		int64	after_chain,
		int64 *	chain_last
	)			`[protected]`

Reverses the chain starting after before_chain and ending before after_chain.

Definition at line 709 of file local_search.cc.

bool operations_research::PathOperator::MakeActive	(	int64	node,
		int64	destination
	)			`[protected]`

Definition at line 733 of file local_search.cc.

bool operations_research::PathOperator::MakeChainInactive	(	int64	before_chain,
		int64	chain_end
	)			`[protected]`

Definition at line 744 of file local_search.cc.

void operations_research::PathOperator::SetNext	(	int64	from,
		int64	to,
		int64	path
	)			`[inline, protected]`

Sets the to to be the node after from.

Definition at line 1099 of file constraint_solveri.h.

bool operations_research::PathOperator::IsPathEnd ( int64 i ) const [inline, protected]

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

Definition at line 1110 of file constraint_solveri.h.

bool operations_research::PathOperator::IsInactive ( int64 i ) const [inline, protected]

Returns true if node is inactive.

Definition at line 1113 of file constraint_solveri.h.

virtual bool operations_research::PathOperator::InitPosition ( ) const [inline, protected, virtual]

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

Definition at line 1117 of file constraint_solveri.h.

void operations_research::PathOperator::ResetPosition ( ) [inline, protected]

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 1121 of file constraint_solveri.h.

Member Data Documentation

const int operations_research::PathOperator::number_of_nexts_ [protected]

Definition at line 1125 of file constraint_solveri.h.

const bool operations_research::PathOperator::ignore_path_vars_ [protected]

Definition at line 1126 of file constraint_solveri.h.

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

or-tools/src/constraint_solver/constraint_solveri.h
or-tools/src/constraint_solver/local_search.cc


Public Member Functions
	PathOperator (const IntVar const next_vars, const IntVar const path_vars, int size, int number_of_base_nodes)
	namespace
virtual	~PathOperator ()
virtual bool	MakeNeighbor ()=0
virtual bool	SkipUnchanged (int index) const
int64	Next (int64 node_index) const
	Returns the index of the node after the node of index node_index in the current assignment.
int64	Path (int64 node_index) const
	Returns the index of the path to which the node of index node_index belongs in the current assignment.
int	number_of_nexts () const
	Number of next variables.
Protected Member Functions
virtual bool	MakeOneNeighbor ()
	This method should not be overridden. Override MakeNeighbor() instead.
int64	BaseNode (int i) const
	Returns the index of the variable corresponding to the ith base node.
int64	StartNode (int i) const
	Returns the index of the variable corresponding to the current path of the ith base node.
virtual bool	RestartAtPathStartOnSynchronize ()
	When the operator is being synchronized with a new solution (when Start() is called), returns true to restart the exploration of the neighborhood from the start of the last paths explored; returns false to restart the exploration at the last nodes visited.
virtual bool	OnSamePathAsPreviousBase (int64 base_index)
	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).
virtual int64	GetBaseNodeRestartPosition (int base_index)
	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.
int64	OldNext (int64 node_index) const
int64	OldPath (int64 node_index) const
bool	MoveChain (int64 before_chain, int64 chain_end, int64 destination)
	Moves the chain starting after the node before_chain and ending at the node chain_end after the node destination.
bool	ReverseChain (int64 before_chain, int64 after_chain, int64 *chain_last)
	Reverses the chain starting after before_chain and ending before after_chain.
bool	MakeActive (int64 node, int64 destination)
bool	MakeChainInactive (int64 before_chain, int64 chain_end)
void	SetNext (int64 from, int64 to, int64 path)
	Sets the to to be the node after from.
bool	IsPathEnd (int64 i) const
	Returns true if i is the last node on the path; defined by the fact that i outside the range of the variable array.
bool	IsInactive (int64 i) const
	Returns true if node is inactive.
virtual bool	InitPosition () const
	Returns true if operator needs to restart its initial position at each call to Start().
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.
Protected Attributes
const int	number_of_nexts_
const bool	ignore_path_vars_