![]() |
OR-Tools
8.2
|
Definition at line 1781 of file local_search.cc.
Public Member Functions | |
PathLns (const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, int number_of_chunks, int chunk_size, bool unactive_fragments) | |
~PathLns () override | |
bool | MakeNeighbor () override |
std::string | DebugString () const override |
bool | HasFragments () 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 | MakeNextNeighbor (Assignment *delta, Assignment *deltadelta) override |
Redefines MakeNextNeighbor to export a simpler interface. 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 int64 & | Value (int64 index) const |
Returns the value in the current assignment of the variable of given index. More... | |
IntVar * | Var (int64 index) const |
Returns the variable of given index. More... | |
const int64 & | OldValue (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 LocalSearchOperator * | Self () const |
Protected Member Functions | |
bool | MakeOneNeighbor () override |
This method should not be overridden. Override MakeNeighbor() instead. More... | |
virtual void | OnNodeInitialization () |
Called by OnStart() after initializing node information. 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< int64 > | start_to_path_ |
std::vector< IntVar * > | vars_ |
std::vector< int64 > | values_ |
std::vector< int64 > | old_values_ |
std::vector< int64 > | prev_values_ |
std::vector< int > | assignment_indices_ |
Bitset64 | activated_ |
Bitset64 | was_activated_ |
SparseBitset | changes_ |
SparseBitset | delta_changes_ |
bool | cleared_ |
IntVarLocalSearchHandler | var_handler_ |
|
inline |
Definition at line 1783 of file local_search.cc.
|
inlineoverride |
Definition at line 1793 of file local_search.cc.
|
inlineinherited |
Definition at line 856 of file constraint_solveri.h.
|
inlineinherited |
Definition at line 855 of file constraint_solveri.h.
|
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.
|
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.
|
inlineinherited |
Definition at line 901 of file constraint_solveri.h.
|
inlineinherited |
Definition at line 864 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns the alternative for the ith base node.
Definition at line 1378 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns the alternative node for the ith base node.
Definition at line 1380 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns the ith base node of the operator.
Definition at line 1376 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns the alternative for the sibling of the ith base node.
Definition at line 1388 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns the alternative node for the sibling of the ith base node.
Definition at line 1392 of file constraint_solveri.h.
|
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.
|
inlineprotectedvirtualinherited |
Indicates if alternatives should be considered when iterating over base nodes.
Reimplemented in PairRelocateOperator.
Definition at line 1441 of file constraint_solveri.h.
|
inlineinherited |
Definition at line 860 of file constraint_solveri.h.
|
inlineoverridevirtual |
Reimplemented from BaseObject.
Definition at line 1796 of file local_search.cc.
|
inlineprotectedinherited |
Returns the active node in the alternative set of the given node.
Definition at line 1537 of file constraint_solveri.h.
|
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.
|
inlineprotectedinherited |
Returns the active node in the given alternative set.
Definition at line 1531 of file constraint_solveri.h.
|
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.
|
inlineprotectedinherited |
Returns the index of the alternative set of the sibling of node.
Definition at line 1541 of file constraint_solveri.h.
|
inlineoverridevirtual |
Reimplemented from LocalSearchOperator.
Definition at line 1797 of file local_search.cc.
|
inlineoverridevirtualinherited |
Reimplemented from LocalSearchOperator.
Definition at line 823 of file constraint_solveri.h.
|
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.
Definition at line 1072 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns true if node is inactive.
Definition at line 1492 of file constraint_solveri.h.
|
inlinevirtualinherited |
Reimplemented in TwoOpt.
Definition at line 839 of file constraint_solveri.h.
|
inlineprotectedinherited |
Definition at line 1067 of file constraint_solveri.h.
|
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.
|
inlineprotectedinherited |
Returns true if node is the first node on the path.
Definition at line 1489 of file constraint_solveri.h.
Insert the inactive node after destination.
Definition at line 457 of file local_search.cc.
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.
|
overridevirtual |
Implements PathOperator.
Definition at line 1809 of file local_search.cc.
|
overridevirtualinherited |
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.
Implements LocalSearchOperator.
Reimplemented in SwapIndexPairOperator, IndexPairSwapActiveOperator, and PairNodeSwapActiveOperator< swap_first >.
Definition at line 74 of file local_search.cc.
|
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.
|
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.
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.
Returns the node after node in the current delta.
Definition at line 1346 of file constraint_solveri.h.
|
inlineinherited |
Number of next variables.
Definition at line 1365 of file constraint_solveri.h.
Definition at line 1074 of file constraint_solveri.h.
Definition at line 1443 of file constraint_solveri.h.
Definition at line 1453 of file constraint_solveri.h.
Definition at line 1448 of file constraint_solveri.h.
Definition at line 850 of file constraint_solveri.h.
|
inlineprotectedvirtualinherited |
Called by OnStart() after initializing node information.
Should be overridden instead of OnStart() to avoid calling PathOperator::OnStart explicitly.
Definition at line 1373 of file constraint_solveri.h.
|
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.
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.
|
inlineprotectedinherited |
Returns the vector of path start nodes.
Definition at line 1404 of file constraint_solveri.h.
|
inlineprotectedinherited |
Returns the class of the path of the ith base node.
Definition at line 1406 of file constraint_solveri.h.
Returns the node before node in the current delta.
Definition at line 1352 of file constraint_solveri.h.
|
overridevirtualinherited |
Reimplemented from LocalSearchOperator.
Definition at line 378 of file local_search.cc.
|
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.
|
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.
Reverses the chain starting after before_chain and ending before after_chain.
Definition at line 434 of file local_search.cc.
|
inlineinherited |
Definition at line 888 of file constraint_solveri.h.
|
inlinevirtualinherited |
Definition at line 806 of file constraint_solveri.h.
Definition at line 1078 of file constraint_solveri.h.
Sets 'to' to be the node after 'from' on the given path.
Definition at line 1474 of file constraint_solveri.h.
|
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.
Definition at line 1082 of file constraint_solveri.h.
Definition at line 851 of file constraint_solveri.h.
|
inlineinherited |
Definition at line 840 of file constraint_solveri.h.
|
overridevirtualinherited |
Reimplemented from VarLocalSearchOperator< IntVar, int64, IntVarLocalSearchHandler >.
Definition at line 399 of file local_search.cc.
|
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.
|
inlineprotectedinherited |
Returns the start node of the ith base node.
Definition at line 1402 of file constraint_solveri.h.
Replaces active by inactive in the current path, making active inactive.
Definition at line 484 of file local_search.cc.
Returns the value in the current assignment of the variable of given index.
Definition at line 843 of file constraint_solveri.h.
Returns the variable of given index.
Definition at line 848 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 935 of file constraint_solveri.h.
|
mutableprotectedinherited |
Definition at line 934 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 937 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 939 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 938 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 1561 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 1562 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 1563 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 1560 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 932 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 933 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 1564 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 931 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 940 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 930 of file constraint_solveri.h.
|
protectedinherited |
Definition at line 936 of file constraint_solveri.h.