OR-Tools  8.2
IndexPairSwapActiveOperator

Detailed Description

Operator which inserts inactive nodes into a path and makes a pair of active nodes inactive.

Definition at line 323 of file routing_neighborhoods.h.

Public Member Functions

 IndexPairSwapActiveOperator (const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
 
 ~IndexPairSwapActiveOperator () override
 
bool MakeNextNeighbor (Assignment *delta, Assignment *deltadelta) override
 Redefines MakeNextNeighbor to export a simpler interface. More...
 
bool MakeNeighbor () override
 
std::string DebugString () const override
 
void Reset () override
 
bool SkipUnchanged (int index) const override
 
int64 Next (int64 node) const
 Returns the node after node in the current delta. More...
 
int64 Prev (int64 node) const
 Returns the node before node in the current delta. More...
 
int64 Path (int64 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
 
const int64Value (int64 index) const
 Returns the value in the current assignment of the variable of given index. More...
 
IntVarVar (int64 index) const
 Returns the variable of given index. More...
 
const int64OldValue (int64 index) const
 
void SetValue (int64 index, const int64 &value)
 
bool Activated (int64 index) const
 
void Activate (int64 index)
 
void Deactivate (int64 index)
 
bool ApplyChanges (Assignment *delta, Assignment *deltadelta) const
 
void RevertChanges (bool incremental)
 
void AddVars (const std::vector< IntVar * > &vars)
 
virtual const LocalSearchOperatorSelf () const
 
virtual bool HasFragments () const
 

Protected Member Functions

bool MakeOneNeighbor () override
 This method should not be overridden. Override MakeNeighbor() instead. More...
 
int64 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 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 BaseSiblingAlternativeNode (int i) const
 Returns the alternative node for the sibling of the ith base node. More...
 
int64 StartNode (int i) const
 Returns the start node of the ith base node. More...
 
const std::vector< int64 > & 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 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. More...
 
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). More...
 
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. More...
 
virtual void SetNextBaseToIncrement (int64 base_index)
 Set the next base to increment on next iteration. More...
 
virtual bool ConsiderAlternatives (int64 base_index) const
 Indicates if alternatives should be considered when iterating over base nodes. More...
 
int64 OldNext (int64 node) const
 
int64 OldPrev (int64 node) const
 
int64 OldPath (int64 node) 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. More...
 
bool ReverseChain (int64 before_chain, int64 after_chain, int64 *chain_last)
 Reverses the chain starting after before_chain and ending before after_chain. More...
 
bool MakeActive (int64 node, int64 destination)
 Insert the inactive node after destination. More...
 
bool MakeChainInactive (int64 before_chain, int64 chain_end)
 Makes the nodes on the chain starting after before_chain and ending at chain_end inactive. More...
 
bool SwapActiveAndInactive (int64 active, int64 inactive)
 Replaces active by inactive in the current path, making active inactive. More...
 
void SetNext (int64 from, int64 to, int64 path)
 Sets 'to' to be the node after 'from' on the given path. More...
 
bool IsPathEnd (int64 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 node) const
 Returns true if node is the first node on the path. More...
 
bool IsInactive (int64 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 > &alternative_set)
 Handling node alternatives. More...
 
void AddPairAlternativeSets (const std::vector< std::pair< std::vector< int64 >, std::vector< int64 > > > &pair_alternative_sets)
 Adds all sets of node alternatives of a vector of alternative pairs. More...
 
int64 GetActiveInAlternativeSet (int alternative_index) const
 Returns the active node in the given alternative set. More...
 
int64 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 GetActiveAlternativeSibling (int node) const
 Returns the active node in the alternative set of the sibling of the given node. More...
 
bool CheckChainValidity (int64 before_chain, int64 chain_end, int64 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...
 
bool IsInverseValue (int64 index) const
 
int64 InverseValue (int64 index) const
 
int64 OldInverseValue (int64 index) const
 
void SetInverseValue (int64 index, int64 value)
 
void SetOldInverseValue (int64 index, int64 value)
 
void MarkChange (int64 index)
 OnStart() should really be protected, but then SWIG doesn't see it. More...
 

Protected Attributes

const int number_of_nexts_
 
const bool ignore_path_vars_
 
int next_base_to_increment_
 
int num_paths_ = 0
 
std::vector< int64start_to_path_
 
std::vector< IntVar * > vars_
 
std::vector< int64values_
 
std::vector< int64old_values_
 
std::vector< int64prev_values_
 
std::vector< int > assignment_indices_
 
Bitset64 activated_
 
Bitset64 was_activated_
 
SparseBitset changes_
 
SparseBitset delta_changes_
 
bool cleared_
 
IntVarLocalSearchHandler var_handler_
 

Constructor & Destructor Documentation

◆ IndexPairSwapActiveOperator()

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

Definition at line 608 of file routing_neighborhoods.cc.

◆ ~IndexPairSwapActiveOperator()

~IndexPairSwapActiveOperator ( )
inlineoverride

Definition at line 329 of file routing_neighborhoods.h.

Member Function Documentation

◆ Activate()

void Activate ( int64  index)
inlineinherited

Definition at line 856 of file constraint_solveri.h.

◆ Activated()

bool Activated ( int64  index) const
inlineinherited

Definition at line 855 of file constraint_solveri.h.

◆ AddAlternativeSet()

int AddAlternativeSet ( const std::vector< int64 > &  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 1507 of file constraint_solveri.h.

◆ AddPairAlternativeSets()

void AddPairAlternativeSets ( const std::vector< std::pair< std::vector< int64 >, std::vector< int64 > > > &  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 1520 of file constraint_solveri.h.

◆ AddVars()

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

Definition at line 901 of file constraint_solveri.h.

◆ ApplyChanges()

bool ApplyChanges ( Assignment delta,
Assignment deltadelta 
) const
inlineinherited

Definition at line 864 of file constraint_solveri.h.

◆ BaseAlternative()

int BaseAlternative ( int  i) const
inlineprotectedinherited

Returns the alternative for the ith base node.

Definition at line 1378 of file constraint_solveri.h.

◆ BaseAlternativeNode()

int64 BaseAlternativeNode ( int  i) const
inlineprotectedinherited

Returns the alternative node for the ith base node.

Definition at line 1380 of file constraint_solveri.h.

◆ BaseNode()

int64 BaseNode ( int  i) const
inlineprotectedinherited

Returns the ith base node of the operator.

Definition at line 1376 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 1388 of file constraint_solveri.h.

◆ BaseSiblingAlternativeNode()

int64 BaseSiblingAlternativeNode ( int  i) const
inlineprotectedinherited

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

Definition at line 1392 of file constraint_solveri.h.

◆ CheckChainValidity()

bool CheckChainValidity ( int64  before_chain,
int64  chain_end,
int64  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 833 of file local_search.cc.

◆ ConsiderAlternatives()

virtual bool ConsiderAlternatives ( int64  base_index) const
inlineprotectedvirtualinherited

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

Reimplemented in PairRelocateOperator.

Definition at line 1441 of file constraint_solveri.h.

◆ Deactivate()

void Deactivate ( int64  index)
inlineinherited

Definition at line 860 of file constraint_solveri.h.

◆ DebugString()

std::string DebugString ( ) const
inlineoverridevirtual

Reimplemented from BaseObject.

Definition at line 333 of file routing_neighborhoods.h.

◆ GetActiveAlternativeNode()

int64 GetActiveAlternativeNode ( int  node) const
inlineprotectedinherited

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

Definition at line 1537 of file constraint_solveri.h.

◆ GetActiveAlternativeSibling()

int64 GetActiveAlternativeSibling ( int  node) const
inlineprotectedinherited

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

Definition at line 1548 of file constraint_solveri.h.

◆ GetActiveInAlternativeSet()

int64 GetActiveInAlternativeSet ( int  alternative_index) const
inlineprotectedinherited

Returns the active node in the given alternative set.

Definition at line 1531 of file constraint_solveri.h.

◆ GetBaseNodeRestartPosition()

virtual int64 GetBaseNodeRestartPosition ( int  base_index)
inlineprotectedvirtualinherited

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 TwoOpt, MakeChainInactiveOperator, MakePairActiveOperator, PairRelocateOperator, PairExchangeRelocateOperator, and PairNodeSwapActiveOperator< swap_first >.

Definition at line 1431 of file constraint_solveri.h.

◆ GetSiblingAlternativeIndex()

int GetSiblingAlternativeIndex ( int  node) const
inlineprotectedinherited

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

Definition at line 1541 of file constraint_solveri.h.

◆ HasFragments()

virtual bool HasFragments ( ) const
inlinevirtualinherited

Reimplemented in BaseLns, and PathLns.

Definition at line 808 of file constraint_solveri.h.

◆ HoldsDelta()

bool HoldsDelta ( ) const
inlineoverridevirtualinherited

Reimplemented from LocalSearchOperator.

Definition at line 823 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 1498 of file constraint_solveri.h.

◆ InverseValue()

int64 InverseValue ( int64  index) const
inlineprotectedinherited

Definition at line 1072 of file constraint_solveri.h.

◆ IsInactive()

bool IsInactive ( int64  node) const
inlineprotectedinherited

Returns true if node is inactive.

Definition at line 1492 of file constraint_solveri.h.

◆ IsIncremental()

virtual bool IsIncremental ( ) const
inlinevirtualinherited

Reimplemented in TwoOpt.

Definition at line 839 of file constraint_solveri.h.

◆ IsInverseValue()

bool IsInverseValue ( int64  index) const
inlineprotectedinherited

Definition at line 1067 of file constraint_solveri.h.

◆ IsPathEnd()

bool IsPathEnd ( int64  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 1486 of file constraint_solveri.h.

◆ IsPathStart()

bool IsPathStart ( int64  node) const
inlineprotectedinherited

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

Definition at line 1489 of file constraint_solveri.h.

◆ MakeActive()

bool MakeActive ( int64  node,
int64  destination 
)
protectedinherited

Insert the inactive node after destination.

Definition at line 457 of file local_search.cc.

◆ MakeChainInactive()

bool MakeChainInactive ( int64  before_chain,
int64  chain_end 
)
protectedinherited

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

Definition at line 467 of file local_search.cc.

◆ MakeNeighbor()

bool MakeNeighbor ( )
overridevirtual

Implements PathOperator.

Definition at line 633 of file routing_neighborhoods.cc.

◆ MakeNextNeighbor()

bool MakeNextNeighbor ( Assignment delta,
Assignment deltadelta 
)
overridevirtual

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.

Reimplemented from IntVarLocalSearchOperator.

Definition at line 619 of file routing_neighborhoods.cc.

◆ MakeOneNeighbor()

bool MakeOneNeighbor ( )
overrideprotectedvirtualinherited

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

Reimplemented from IntVarLocalSearchOperator.

Reimplemented in BaseInactiveNodeToPathOperator, TSPLns, MakePairActiveOperator, and RelocateExpensiveChain.

Definition at line 387 of file local_search.cc.

◆ MarkChange()

void MarkChange ( int64  index)
inlineprotectedinherited

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

Definition at line 925 of file constraint_solveri.h.

◆ MoveChain()

bool MoveChain ( int64  before_chain,
int64  chain_end,
int64  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 411 of file local_search.cc.

◆ Next()

int64 Next ( int64  node) const
inlineinherited

Returns the node after node in the current delta.

Definition at line 1346 of file constraint_solveri.h.

◆ number_of_nexts()

int number_of_nexts ( ) const
inlineinherited

Number of next variables.

Definition at line 1365 of file constraint_solveri.h.

◆ OldInverseValue()

int64 OldInverseValue ( int64  index) const
inlineprotectedinherited

Definition at line 1074 of file constraint_solveri.h.

◆ OldNext()

int64 OldNext ( int64  node) const
inlineprotectedinherited

Definition at line 1443 of file constraint_solveri.h.

◆ OldPath()

int64 OldPath ( int64  node) const
inlineprotectedinherited

Definition at line 1453 of file constraint_solveri.h.

◆ OldPrev()

int64 OldPrev ( int64  node) const
inlineprotectedinherited

Definition at line 1448 of file constraint_solveri.h.

◆ OldValue()

const int64 & OldValue ( int64  index) const
inlineinherited

Definition at line 850 of file constraint_solveri.h.

◆ OnSamePathAsPreviousBase()

virtual bool OnSamePathAsPreviousBase ( int64  base_index)
inlineprotectedvirtualinherited

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.

Reimplemented in TwoOpt, Relocate, MakeChainInactiveOperator, MakePairActiveOperator, PairRelocateOperator, PairExchangeRelocateOperator, and PairNodeSwapActiveOperator< swap_first >.

Definition at line 1425 of file constraint_solveri.h.

◆ Path()

int64 Path ( int64  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 1360 of file constraint_solveri.h.

◆ path_starts()

const std::vector< int64 > & path_starts ( ) const
inlineprotectedinherited

Returns the vector of path start nodes.

Definition at line 1404 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 1406 of file constraint_solveri.h.

◆ Prev()

int64 Prev ( int64  node) const
inlineinherited

Returns the node before node in the current delta.

Definition at line 1352 of file constraint_solveri.h.

◆ Reset()

void Reset ( )
overridevirtualinherited

Reimplemented from LocalSearchOperator.

Definition at line 378 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 1502 of file constraint_solveri.h.

◆ RestartAtPathStartOnSynchronize()

virtual bool RestartAtPathStartOnSynchronize ( )
inlineprotectedvirtualinherited

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.

Reimplemented in MakePairActiveOperator, and PairNodeSwapActiveOperator< swap_first >.

Definition at line 1419 of file constraint_solveri.h.

◆ ReverseChain()

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

Reverses the chain starting after before_chain and ending before after_chain.

Definition at line 434 of file local_search.cc.

◆ RevertChanges()

void RevertChanges ( bool  incremental)
inlineinherited

Definition at line 888 of file constraint_solveri.h.

◆ Self()

virtual const LocalSearchOperator * Self ( ) const
inlinevirtualinherited

Definition at line 806 of file constraint_solveri.h.

◆ SetInverseValue()

void SetInverseValue ( int64  index,
int64  value 
)
inlineprotectedinherited

Definition at line 1078 of file constraint_solveri.h.

◆ SetNext()

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

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

Definition at line 1474 of file constraint_solveri.h.

◆ SetNextBaseToIncrement()

virtual void SetNextBaseToIncrement ( int64  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.

◆ SetOldInverseValue()

void SetOldInverseValue ( int64  index,
int64  value 
)
inlineprotectedinherited

Definition at line 1082 of file constraint_solveri.h.

◆ SetValue()

void SetValue ( int64  index,
const int64 value 
)
inlineinherited

Definition at line 851 of file constraint_solveri.h.

◆ Size()

int Size ( ) const
inlineinherited

Definition at line 840 of file constraint_solveri.h.

◆ SkipUnchanged()

bool SkipUnchanged ( int  index) const
overridevirtualinherited

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

◆ StartNode()

int64 StartNode ( int  i) const
inlineprotectedinherited

Returns the start node of the ith base node.

Definition at line 1402 of file constraint_solveri.h.

◆ SwapActiveAndInactive()

bool SwapActiveAndInactive ( int64  active,
int64  inactive 
)
protectedinherited

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

Definition at line 484 of file local_search.cc.

◆ Value()

const int64 & Value ( int64  index) const
inlineinherited

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

Definition at line 843 of file constraint_solveri.h.

◆ Var()

IntVar * Var ( int64  index) const
inlineinherited

Returns the variable of given index.

Definition at line 848 of file constraint_solveri.h.

Member Data Documentation

◆ activated_

Bitset64 activated_
protectedinherited

Definition at line 935 of file constraint_solveri.h.

◆ assignment_indices_

std::vector<int> assignment_indices_
mutableprotectedinherited

Definition at line 934 of file constraint_solveri.h.

◆ changes_

SparseBitset changes_
protectedinherited

Definition at line 937 of file constraint_solveri.h.

◆ cleared_

bool cleared_
protectedinherited

Definition at line 939 of file constraint_solveri.h.

◆ delta_changes_

SparseBitset delta_changes_
protectedinherited

Definition at line 938 of file constraint_solveri.h.

◆ ignore_path_vars_

const bool ignore_path_vars_
protectedinherited

Definition at line 1561 of file constraint_solveri.h.

◆ next_base_to_increment_

int next_base_to_increment_
protectedinherited

Definition at line 1562 of file constraint_solveri.h.

◆ num_paths_

int num_paths_ = 0
protectedinherited

Definition at line 1563 of file constraint_solveri.h.

◆ number_of_nexts_

const int number_of_nexts_
protectedinherited

Definition at line 1560 of file constraint_solveri.h.

◆ old_values_

std::vector<int64 > old_values_
protectedinherited

Definition at line 932 of file constraint_solveri.h.

◆ prev_values_

std::vector<int64 > prev_values_
protectedinherited

Definition at line 933 of file constraint_solveri.h.

◆ start_to_path_

std::vector<int64> start_to_path_
protectedinherited

Definition at line 1564 of file constraint_solveri.h.

◆ values_

std::vector<int64 > values_
protectedinherited

Definition at line 931 of file constraint_solveri.h.

◆ var_handler_

IntVarLocalSearchHandler var_handler_
protectedinherited

Definition at line 940 of file constraint_solveri.h.

◆ vars_

std::vector<IntVar *> vars_
protectedinherited

Definition at line 930 of file constraint_solveri.h.

◆ was_activated_

Bitset64 was_activated_
protectedinherited

Definition at line 936 of file constraint_solveri.h.


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