#include <constraint_solveri.h>

Classes
class	Chain
	A Chain is a range of committed nodes. More...

struct	ChainBounds

class	ChainRange
	A ChainRange is a range of Chains, committed or not. More...

class	NodeRange

Public Member Functions
int	CommittedIndex (int node) const

ChainBounds	CommittedPathRange (int path) const

	PathState (int num_nodes, std::vector< int > path_start, std::vector< int > path_end)

int	NumNodes () const
	Instance-constant accessors.

int	NumPaths () const
	Returns the number of paths (empty paths included).

int	Start (int path) const
	Returns the start of a path.

int	End (int path) const
	Returns the end of a path.

int	Path (int node) const
	State-dependent accessors.

const std::vector< int > &	ChangedPaths () const

const std::vector< int > &	ChangedLoops () const
	Returns the set of loops that were added by the change.

ChainRange	Chains (int path) const
	Returns the current range of chains of path.

NodeRange	Nodes (int path) const
	Returns the current range of nodes of path.

void	ChangePath (int path, const std::vector< ChainBounds > &chains)
	State modifiers.

void	ChangePath (int path, const std::initializer_list< ChainBounds > &chains)

void	ChangeLoops (const std::vector< int > &new_loops)
	Describes the nodes that are newly loops in this change.

void	Commit ()
	Set the current state G1 as committed. See class comment for details.

void	Revert ()
	Erase incremental changes. See class comment for details.

void	SetInvalid ()

bool	IsInvalid () const

Detailed Description

A PathState represents a set of paths and changes made on it.

More accurately, let us define P_{num_nodes, starts, ends}-graphs the set of directed graphs with nodes [0, num_nodes) whose connected components are paths from starts[i] to ends[i] (for the same i) and loops. Let us fix num_nodes, starts and ends, so we call these P-graphs.

A P-graph can be described by the sequence of nodes of each of its paths, and its set of loops. To describe a change made on a given P-graph G0 that yields another P-graph G1, we choose to describe G1 in terms of G0. When the difference between G0 and G1 is small, as is almost always the case in a local search setting, the description is compact, allowing for incremental filters to be efficient.

In order to describe G1 in terms of G0 succintly, we describe each path of G1 as a sequence of chains of G0. A chain of G0 is either a nonempty sequence of consecutive nodes of a path of G0, or a node that was a loop in G0. For instance, a path that was not modified from G0 to G1 has one chain, the sequence of all nodes in the path. Typically, local search operators modify one or two paths, and the resulting paths can described as sequences of two to four chains of G0. Paths that were modified are listed explicitly, allowing to iterate only on changed paths. The loops of G1 are described more implicitly: the loops of G1 not in G0 are listed explicitly, but those in both G1 and G0 are not listed.

A PathState object can be in two states: committed or changed. At construction, the object is committed, G0. To enter a changed state G1, one can pass modifications with ChangePath() and ChangeLoops(). For reasons of efficiency, a chain is described as a range of node indices in the representation of the committed graph G0. To that effect, the nodes of a path of G0 are guaranteed to have consecutive indices.

Filters can then browse the change efficiently using ChangedPaths(), Chains(), Nodes() and ChangedLoops().

Then Commit() or Revert() can be called: Commit() sets the changed state G1 as the new committed state, Revert() erases all changes.

Definition at line 3390 of file constraint_solveri.h.

Constructor & Destructor Documentation

◆ PathState()

operations_research::PathState::PathState	(	int	num_nodes,
		std::vector< int >	path_start,
		std::vector< int >	path_end )

Path constructor: path_start and path_end must be disjoint, their values in [0, num_nodes).

Initial state is all unperformed: paths go from start to end directly.

Nodes that are not starts or ends are loops.

Definition at line 2654 of file local_search.cc.

Member Function Documentation

◆ Chains()

PathState::ChainRange operations_research::PathState::Chains ( int path ) const

Returns the current range of chains of path.

Definition at line 2695 of file local_search.cc.

◆ ChangedLoops()

const std::vector< int > & operations_research::PathState::ChangedLoops ( ) const

inline

Returns the set of loops that were added by the change.

Definition at line 3438 of file constraint_solveri.h.

◆ ChangedPaths()

const std::vector< int > & operations_research::PathState::ChangedPaths ( ) const

inline

Returns the set of paths that actually changed, i.e. that have more than one chain.

Definition at line 3436 of file constraint_solveri.h.

◆ ChangeLoops()

void operations_research::PathState::ChangeLoops ( const std::vector< int > & new_loops )

Describes the nodes that are newly loops in this change.

Definition at line 2718 of file local_search.cc.

◆ ChangePath() [1/2]

void operations_research::PathState::ChangePath	(	int	path,
		const std::initializer_list< ChainBounds > &	chains )

inline

Same as above, but the initializer_list interface avoids the need to pass a vector.

Always add sentinel, in case this is the last path change.

Definition at line 3454 of file constraint_solveri.h.

◆ ChangePath() [2/2]

void operations_research::PathState::ChangePath	(	int	path,
		const std::vector< ChainBounds > &	chains )

State modifiers.

Changes the path to the given sequence of chains of the committed state. Chains are described by semi-open intervals. No optimization is made in case two consecutive chains are actually already consecutive in the committed state: they are not merged into one chain, and Chains(path) will report the two chains.

Definition at line 2709 of file local_search.cc.

◆ Commit()

void operations_research::PathState::Commit ( )

Set the current state G1 as committed. See class comment for details.

Definition at line 2725 of file local_search.cc.

◆ CommittedIndex()

int operations_research::PathState::CommittedIndex ( int node ) const

inline

Definition at line 3411 of file constraint_solveri.h.

◆ CommittedPathRange()

ChainBounds operations_research::PathState::CommittedPathRange ( int path ) const

inline

Definition at line 3412 of file constraint_solveri.h.

◆ End()

int operations_research::PathState::End ( int path ) const

inline

Returns the end of a path.

Definition at line 3428 of file constraint_solveri.h.

◆ IsInvalid()

bool operations_research::PathState::IsInvalid ( ) const

inline

Definition at line 3475 of file constraint_solveri.h.

◆ Nodes()

PathState::NodeRange operations_research::PathState::Nodes ( int path ) const

Returns the current range of nodes of path.

Definition at line 2702 of file local_search.cc.

◆ NumNodes()

int operations_research::PathState::NumNodes ( ) const

inline

Instance-constant accessors.

Returns the number of nodes in the underlying graph.

Definition at line 3422 of file constraint_solveri.h.

◆ NumPaths()

int operations_research::PathState::NumPaths ( ) const

inline

Returns the number of paths (empty paths included).

Definition at line 3424 of file constraint_solveri.h.

◆ Path()

int operations_research::PathState::Path ( int node ) const

inline

State-dependent accessors.

Returns the committed path of a given node, -1 if it is a loop.

Definition at line 3433 of file constraint_solveri.h.

◆ Revert()

void operations_research::PathState::Revert ( )

Erase incremental changes. See class comment for details.

Definition at line 2734 of file local_search.cc.

◆ SetInvalid()

void operations_research::PathState::SetInvalid ( )

inline

LNS Operators may not fix variables, in which case we mark the candidate invalid.

Definition at line 3474 of file constraint_solveri.h.

◆ Start()

int operations_research::PathState::Start ( int path ) const

inline

Returns the start of a path.

Definition at line 3426 of file constraint_solveri.h.

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

ortools/constraint_solver/constraint_solveri.h
ortools/constraint_solver/local_search.cc

Classes

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ PathState()

Member Function Documentation

◆ Chains()

◆ ChangedLoops()

◆ ChangedPaths()

◆ ChangeLoops()

◆ ChangePath() [1/2]

◆ ChangePath() [2/2]

◆ Commit()

◆ CommittedIndex()

◆ CommittedPathRange()

◆ End()

◆ IsInvalid()

◆ Nodes()

◆ NumNodes()

◆ NumPaths()

◆ Path()

◆ Revert()

◆ SetInvalid()

◆ Start()