Google OR-Tools: operations_research::PathOperator< ignore_path_vars > Class Template Reference
template<bool ignore_path_vars>
class operations_research::PathOperator< ignore_path_vars >
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(), Prev(), 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 1529 of file constraint_solveri.h.
#include <constraint_solveri.h>
Public Member Functions | |
| 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_incoming_neighbors, std::function< const std::vector< int > &(int, int)> get_outgoing_neighbors) | |
| ~PathOperator () override | |
| virtual bool | MakeNeighbor ()=0 |
| void | EnterSearch () 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 |
| 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 | |
| BaseObject & | operator= (const BaseObject &)=delete |
| virtual | ~BaseObject ()=default |
| virtual std::string | DebugString () const |
Protected Member Functions | |
| bool | MakeOneNeighbor () override |
| This method should not be overridden. Override MakeNeighbor() instead. | |
| virtual void | OnNodeInitialization () |
| virtual void | ResetIncrementalism () |
| int64_t | BaseNode (int i) const |
| Returns the ith base node of the operator. | |
| int64_t | BaseAlternativeNode (int i) const |
| Returns the alternative node for 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) |
| it's currently way more complicated to implement. | |
| virtual int64_t | GetBaseNodeRestartPosition (int base_index) |
| virtual void | SetNextBaseToIncrement (int64_t base_index) |
| virtual bool | ConsiderAlternatives (int64_t) 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 | SwapNodes (int64_t node1, int64_t node2) |
| Swaps the nodes node1 and node2. | |
| 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. | |
| bool | SwapActiveAndInactiveChains (absl::Span< const int64_t > active_chain, absl::Span< const int64_t > inactive_chain) |
| 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. | |
| int | GetAlternativeIndex (int node) const |
| Returns the index of the alternative set of the node. | |
| int64_t | GetActiveAlternativeSibling (int node) const |
| bool | CheckChainValidity (int64_t before_chain, int64_t chain_end, int64_t exclude) const |
| bool | HasNeighbors () const |
| Neighbor | 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 |
Protected Attributes | |
| const int | number_of_nexts_ |
template<bool ignore_path_vars>
◆ PathOperator() [2/2]
template<bool ignore_path_vars>
|
inline |
◆ ~PathOperator()
template<bool ignore_path_vars>
◆ AddAlternativeSet()
template<bool ignore_path_vars>
Handling node alternatives. Adds a set of node alternatives to the neighborhood. No node can be in two alternatives.
Definition at line 1909 of file constraint_solveri.h.
◆ AddPairAlternativeSets()
template<bool ignore_path_vars>
template<typename PairType>
Adds all sets of node alternatives of a vector of alternative pairs. No node can be in two alternatives.
Definition at line 1923 of file constraint_solveri.h.
◆ BaseAlternativeNode()
template<bool ignore_path_vars>
◆ BaseNode()
template<bool ignore_path_vars>
◆ BaseSiblingAlternativeNode()
template<bool ignore_path_vars>
Returns the alternative node for the sibling of the ith base node.
Definition at line 1689 of file constraint_solveri.h.
◆ CheckChainValidity()
template<bool ignore_path_vars>
Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not contain exclude. In particular, rejects a chain if chain_end is not strictly after before_chain on the path. Cycles are detected through chain length overflow.
Definition at line 1961 of file constraint_solveri.h.
◆ ConsiderAlternatives()
template<bool ignore_path_vars>
◆ CurrentNodePathEnd()
template<bool ignore_path_vars>
◆ CurrentNodePathStart()
template<bool ignore_path_vars>
◆ EndNode()
template<bool ignore_path_vars>
◆ EnterSearch()
template<bool ignore_path_vars>
◆ GetActiveAlternativeNode()
template<bool ignore_path_vars>
◆ GetActiveAlternativeSibling()
template<bool ignore_path_vars>
Returns the active node in the alternative set of the sibling of the given node.
Definition at line 1953 of file constraint_solveri.h.
◆ GetActiveInAlternativeSet()
template<bool ignore_path_vars>
◆ GetAlternativeIndex()
template<bool ignore_path_vars>
◆ GetBaseNodeRestartPosition()
template<bool ignore_path_vars>
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::ExchangePathStartEndsAndMakeActiveOperator< ignore_path_vars >, operations_research::MakeChainInactiveOperator< ignore_path_vars >, operations_research::MakePairActiveOperator< ignore_path_vars >, operations_research::PairExchangeRelocateOperator< ignore_path_vars >, operations_research::PairNodeSwapActiveOperator< swap_first, ignore_path_vars >, operations_research::PairRelocateOperator< ignore_path_vars >, operations_research::TwoOpt< ignore_path_vars >, and operations_research::TwoOptWithShortestPathOperator< ignore_path_vars >.
Definition at line 1727 of file constraint_solveri.h.
◆ GetNeighborForBaseNode()
template<bool ignore_path_vars>
◆ GetSiblingAlternativeIndex()
template<bool ignore_path_vars>
◆ HasNeighbors()
template<bool ignore_path_vars>
◆ InitPosition()
template<bool ignore_path_vars>
◆ IsInactive()
template<bool ignore_path_vars>
◆ IsPathEnd()
template<bool ignore_path_vars>
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 1888 of file constraint_solveri.h.
◆ IsPathStart()
template<bool ignore_path_vars>
◆ MakeActive()
template<bool ignore_path_vars>
◆ MakeChainInactive()
template<bool ignore_path_vars>
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
Definition at line 1836 of file constraint_solveri.h.
◆ MakeNeighbor()
template<bool ignore_path_vars>
Implemented in operations_research::Cross< ignore_path_vars >, operations_research::Exchange< ignore_path_vars >, operations_research::ExchangeAndMakeActiveOperator< ignore_path_vars >, operations_research::ExchangePathStartEndsAndMakeActiveOperator< ignore_path_vars >, operations_research::ExchangeSubtrip< ignore_path_vars >, operations_research::ExtendedSwapActiveOperator< ignore_path_vars >, operations_research::GroupPairAndRelocateOperator< ignore_path_vars >, operations_research::IndexPairSwapActiveOperator< ignore_path_vars >, operations_research::LightPairRelocateOperator< ignore_path_vars >, operations_research::LinKernighan< ignore_path_vars >, operations_research::MakeActiveAndRelocateOperator< ignore_path_vars >, operations_research::MakeActiveOperator< ignore_path_vars >, operations_research::MakeChainInactiveOperator< ignore_path_vars >, operations_research::MakeInactiveOperator< ignore_path_vars >, operations_research::MakePairActiveOperator< ignore_path_vars >, operations_research::MakePairInactiveOperator< ignore_path_vars >, operations_research::MakeRelocateNeighborsOperator< ignore_path_vars >, operations_research::PairExchangeOperator< ignore_path_vars >, operations_research::PairExchangeRelocateOperator< ignore_path_vars >, operations_research::PairNodeSwapActiveOperator< swap_first, ignore_path_vars >, operations_research::PairRelocateOperator< ignore_path_vars >, operations_research::PathLns< ignore_path_vars >, operations_research::Relocate< ignore_path_vars >, operations_research::RelocateAndMakeActiveOperator< ignore_path_vars >, operations_research::RelocateAndMakeInactiveOperator< ignore_path_vars >, operations_research::RelocateExpensiveChain< ignore_path_vars >, operations_research::RelocateSubtrip< ignore_path_vars >, operations_research::SwapActiveChainOperator< ignore_path_vars >, operations_research::SwapActiveOperator< ignore_path_vars >, operations_research::SwapActiveToShortestPathOperator< ignore_path_vars >, operations_research::TSPLns< ignore_path_vars >, operations_research::TSPOpt< ignore_path_vars >, operations_research::TwoOpt< ignore_path_vars >, and operations_research::TwoOptWithShortestPathOperator< ignore_path_vars >.
◆ MakeOneNeighbor()
template<bool ignore_path_vars>
◆ MoveChain()
template<bool ignore_path_vars>
Moves the chain starting after the node before_chain and ending at the node chain_end after the node destination
Definition at line 1767 of file constraint_solveri.h.
◆ Next()
template<bool ignore_path_vars>
◆ number_of_nexts()
template<bool ignore_path_vars>
◆ OldNext()
template<bool ignore_path_vars>
◆ OldPath()
template<bool ignore_path_vars>
◆ OldPrev()
template<bool ignore_path_vars>
◆ OnNodeInitialization()
template<bool ignore_path_vars>
◆ OnSamePathAsPreviousBase()
template<bool ignore_path_vars>
it's currently way more complicated to implement.
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.
Reimplemented in operations_research::ExchangeAndMakeActiveOperator< ignore_path_vars >, operations_research::MakeChainInactiveOperator< ignore_path_vars >, operations_research::MakePairActiveOperator< ignore_path_vars >, operations_research::PairExchangeRelocateOperator< ignore_path_vars >, operations_research::PairNodeSwapActiveOperator< swap_first, ignore_path_vars >, operations_research::PairRelocateOperator< ignore_path_vars >, operations_research::Relocate< ignore_path_vars >, operations_research::SwapActiveChainOperator< ignore_path_vars >, operations_research::TwoOpt< ignore_path_vars >, and operations_research::TwoOptWithShortestPathOperator< ignore_path_vars >.
Definition at line 1721 of file constraint_solveri.h.
◆ Path()
template<bool ignore_path_vars>
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 1649 of file constraint_solveri.h.
◆ path_starts()
template<bool ignore_path_vars>
◆ PathClass()
template<bool ignore_path_vars>
◆ PathClassFromStartNode()
template<bool ignore_path_vars>
◆ Prev()
template<bool ignore_path_vars>
◆ PrevNext()
template<bool ignore_path_vars>
◆ Reset()
template<bool ignore_path_vars>
◆ ResetIncrementalism()
template<bool ignore_path_vars>
◆ ResetPosition()
template<bool ignore_path_vars>
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 1904 of file constraint_solveri.h.
◆ RestartAtPathStartOnSynchronize()
template<bool ignore_path_vars>
◆ ReverseChain()
template<bool ignore_path_vars>
Reverses the chain starting after before_chain and ending before after_chain
Definition at line 1791 of file constraint_solveri.h.
◆ SetNext()
template<bool ignore_path_vars>
◆ SetNextBaseToIncrement()
template<bool ignore_path_vars>
Set the next base to increment on next iteration. All base > base_index will be reset to their start value.
Definition at line 1732 of file constraint_solveri.h.
◆ SkipUnchanged()
template<bool ignore_path_vars>
◆ StartNode()
template<bool ignore_path_vars>
◆ SwapActiveAndInactive()
template<bool ignore_path_vars>
Replaces active by inactive in the current path, making active inactive.
Definition at line 1854 of file constraint_solveri.h.
◆ SwapActiveAndInactiveChains()
template<bool ignore_path_vars>
|
inlineprotected |
Swaps both chains, making nodes on active_chain inactive and inserting active_chain at the position where inactive_chain was.
Definition at line 1861 of file constraint_solveri.h.
◆ SwapNodes()
template<bool ignore_path_vars>
◆ AlternativeNodeIterator
template<bool ignore_path_vars>
|
friend class AlternativeNodeIterator |
friend |
◆ BaseNodeIterators< PathOperator >
template<bool ignore_path_vars>
◆ NodeNeighborIterator
template<bool ignore_path_vars>
|
friend class NodeNeighborIterator |
friend |
◆ number_of_nexts_
template<bool ignore_path_vars>
The documentation for this class was generated from the following file:
- ortools/constraint_solver/constraint_solveri.h