Inheritance diagram for operations_research::TSPLns:

Public Member Functions
	TSPLns (const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, Solver::IndexEvaluator3 evaluator, int tsp_size)

	~TSPLns () override

bool	MakeNeighbor () override

std::string	DebugString () const override

Public Member Functions inherited from operations_research::PathOperator
	PathOperator (const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, IterationParameters iteration_parameters)
	Builds an instance of PathOperator from next and path variables.

	PathOperator (const std::vector< IntVar * > &next_vars, const std::vector< IntVar * > &path_vars, int number_of_base_nodes, bool skip_locally_optimal_paths, bool accept_path_end_base, std::function< int(int64_t)> start_empty_path_class, std::function< const std::vector< int > &(int, int)> get_neighbors)

	~PathOperator () 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.

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

int64_t	Path (int64_t node) const

int	number_of_nexts () const
	Number of next variables.

Public Member Functions inherited from operations_research::IntVarLocalSearchOperator
	IntVarLocalSearchOperator (const std::vector< IntVar * > &vars, bool keep_inverse_values=false)

	~IntVarLocalSearchOperator () override

bool	HoldsDelta () const override

void	Start (const Assignment *assignment) override

virtual bool	IsIncremental () const

int	Size () const

int64_t	Value (int64_t index) const

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

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
	--— Base operator class for operators manipulating IntVars --—

Public Member Functions inherited from operations_research::LocalSearchOperator
	LocalSearchOperator ()

	~LocalSearchOperator () override

virtual const LocalSearchOperator *	Self () const

virtual bool	HasFragments () 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 ()

Protected Member Functions
bool	MakeOneNeighbor () override
	This method should not be overridden. Override MakeNeighbor() instead.

Protected Member Functions inherited from operations_research::PathOperator
int64_t	BaseNode (int i) const
	Returns the ith base node of the operator.

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

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

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

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

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

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

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

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

int	PathClassFromStartNode (int64_t start_node) const

virtual bool	RestartAtPathStartOnSynchronize ()

virtual bool	OnSamePathAsPreviousBase (int64_t base_index)

virtual int64_t	GetBaseNodeRestartPosition (int base_index)

virtual void	SetNextBaseToIncrement (int64_t base_index)

virtual bool	ConsiderAlternatives (int64_t base_index) const

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

int	CurrentNodePathStart (int64_t node) const

int	CurrentNodePathEnd (int64_t node) const

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

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

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

bool	MakeChainInactive (int64_t before_chain, int64_t chain_end)

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

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

bool	IsPathEnd (int64_t node) const

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

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

virtual bool	InitPosition () const

void	ResetPosition ()

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

template<typename PairType >
void	AddPairAlternativeSets (const std::vector< PairType > &pair_alternative_sets)

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

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

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

int64_t	GetActiveAlternativeSibling (int node) const

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

bool	HasNeighbors () const

int	GetNeighborForBaseNode (int64_t base_index) const

Protected Member Functions inherited from operations_research::IntVarLocalSearchOperator
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

Additional Inherited Members
Protected Attributes inherited from operations_research::PathOperator
const int	number_of_nexts_

const bool	ignore_path_vars_

Detailed Description

TSP-base lns Randomly merge consecutive nodes until n "meta"-nodes remain and solve the corresponding TSP. This can be seen as a large neighborhood search operator although decisions are taken with the operator. This is an "unlimited" neighborhood which must be stopped by search limits. To force diversification, the operator iteratively forces each node to serve as base of a meta-node.

Definition at line 1587 of file local_search.cc.

Constructor & Destructor Documentation

◆ TSPLns()

operations_research::TSPLns::TSPLns	(	const std::vector< IntVar * > &	vars,
		const std::vector< IntVar * > &	secondary_vars,
		Solver::IndexEvaluator3	evaluator,
		int	tsp_size )

Definition at line 1615 of file local_search.cc.

◆ ~TSPLns()

operations_research::TSPLns::~TSPLns ( )

inlineoverride

Definition at line 1592 of file local_search.cc.

Member Function Documentation

◆ DebugString()

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

inlineoverridevirtual

Reimplemented from operations_research::BaseObject.

Definition at line 1595 of file local_search.cc.

◆ MakeNeighbor()

bool operations_research::TSPLns::MakeNeighbor ( )

overridevirtual

Randomly select break nodes (final nodes of a meta-node, after which an arc is relaxed.

Always add base node to break nodes (diversification)

Setup break node indexing and internal meta-node cost (cost of partial route starting at first node of the meta-node and ending at its last node); this cost has to be added to the TSP matrix cost in order to respect the triangle inequality.

Setup TSP cost matrix

Solve TSP and inject solution in delta (only if it leads to a new solution)

Implements operations_research::PathOperator.

Definition at line 1642 of file local_search.cc.

◆ MakeOneNeighbor()

bool operations_research::TSPLns::MakeOneNeighbor ( )

overrideprotectedvirtual

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

Need to revert changes here since MakeNeighbor might have returned false and have done changes in the previous iteration.

Reimplemented from operations_research::PathOperator.

Definition at line 1631 of file local_search.cc.

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

ortools/constraint_solver/local_search.cc

Public Member Functions

Protected Member Functions

Additional Inherited Members