Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | Protected Member Functions | Static Protected Attributes | List of all members
operations_research::BasePathFilter Class Referenceabstract

Generic path-based filter class. More...

#include <routing_filters.h>

Inheritance diagram for operations_research::BasePathFilter:
operations_research::IntVarLocalSearchFilter operations_research::LocalSearchFilter operations_research::BaseObject

Public Member Functions

 BasePathFilter (const std::vector< IntVar * > &nexts, int next_domain_size)
 
 ~BasePathFilter () override
 
bool Accept (const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max) override
 
void OnSynchronize (const Assignment *delta) override
 
- Public Member Functions inherited from operations_research::IntVarLocalSearchFilter
 IntVarLocalSearchFilter (const std::vector< IntVar * > &vars)
 
 ~IntVarLocalSearchFilter () override
 
void Synchronize (const Assignment *assignment, const Assignment *delta) override
 
bool FindIndex (IntVar *const var, int64_t *index) const
 
void AddVars (const std::vector< IntVar * > &vars)
 Add variables to "track" to the filter.
 
int Size () const
 
IntVar * Var (int index) const
 
int64_t Value (int index) const
 
bool IsVarSynced (int index) const
 
- Public Member Functions inherited from operations_research::LocalSearchFilter
virtual void Relax (const Assignment *delta, const Assignment *deltadelta)
 
virtual void Commit (const Assignment *delta, const Assignment *deltadelta)
 Dual of Relax(), lets the filter know that the delta was accepted.
 
virtual bool IsIncremental () const
 
virtual void Revert ()
 Cancels the changes made by the last Relax()/Accept() calls.
 
virtual void Reset ()
 Sets the filter to empty solution.
 
virtual int64_t GetSynchronizedObjectiveValue () const
 Objective value from last time Synchronize() was called.
 
virtual int64_t GetAcceptedObjectiveValue () 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 ()
 
virtual std::string DebugString () const
 

Protected Member Functions

int64_t GetNext (int64_t node) const
 
int NumPaths () const
 
int64_t Start (int i) const
 
int GetPath (int64_t node) const
 
int Rank (int64_t node) const
 
bool IsDisabled () const
 
const std::vector< int64_t > & GetTouchedPathStarts () const
 
bool PathStartTouched (int64_t start) const
 
const std::vector< int64_t > & GetNewSynchronizedUnperformedNodes () const
 
bool lns_detected () const
 
- Protected Member Functions inherited from operations_research::IntVarLocalSearchFilter
void SynchronizeOnAssignment (const Assignment *assignment)
 

Static Protected Attributes

static const int64_t kUnassigned = -1
 

Detailed Description

Generic path-based filter class.

Definition at line 138 of file routing_filters.h.

Constructor & Destructor Documentation

◆ BasePathFilter()

operations_research::BasePathFilter::BasePathFilter ( const std::vector< IntVar * > & nexts,
int next_domain_size )

Definition at line 281 of file routing_filters.cc.

◆ ~BasePathFilter()

operations_research::BasePathFilter::~BasePathFilter ( )
inlineoverride

Definition at line 141 of file routing_filters.h.

Member Function Documentation

◆ Accept()

bool operations_research::BasePathFilter::Accept ( const Assignment * delta,
const Assignment * deltadelta,
int64_t objective_min,
int64_t objective_max )
overridevirtual

Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds the variables which have been modified and their new value. If the filter represents a part of the global objective, its contribution must be between objective_min and objective_max. Sample: supposing one wants to maintain a[0,1] + b[0,1] <= 1, for the assignment (a,1), (b,0), the delta (b,1) will be rejected but the delta (a,0) will be accepted.

Todo
(user): Remove arguments when there are no more need for those.

Determining touched paths and their touched chain start and ends (a node is touched if it corresponds to an element of delta or that an element of delta points to it). The start and end of a touched path subchain will have remained on the same path and will correspond to the min and max ranks of touched nodes in the current assignment.

LNS detected

Checking feasibility of touched paths.

Note
FinalizeAcceptPath() is only called if InitializeAcceptPath() is true and all paths are accepted.

Implements operations_research::LocalSearchFilter.

Definition at line 294 of file routing_filters.cc.

◆ GetNewSynchronizedUnperformedNodes()

const std::vector< int64_t > & operations_research::BasePathFilter::GetNewSynchronizedUnperformedNodes ( ) const
inlineprotected

Definition at line 163 of file routing_filters.h.

◆ GetNext()

int64_t operations_research::BasePathFilter::GetNext ( int64_t node) const
inlineprotected

Definition at line 149 of file routing_filters.h.

◆ GetPath()

int operations_research::BasePathFilter::GetPath ( int64_t node) const
inlineprotected

Definition at line 156 of file routing_filters.h.

◆ GetTouchedPathStarts()

const std::vector< int64_t > & operations_research::BasePathFilter::GetTouchedPathStarts ( ) const
inlineprotected

Definition at line 159 of file routing_filters.h.

◆ IsDisabled()

bool operations_research::BasePathFilter::IsDisabled ( ) const
inlineprotected

Definition at line 158 of file routing_filters.h.

◆ lns_detected()

bool operations_research::BasePathFilter::lns_detected ( ) const
inlineprotected

Definition at line 167 of file routing_filters.h.

◆ NumPaths()

int operations_research::BasePathFilter::NumPaths ( ) const
inlineprotected

Definition at line 154 of file routing_filters.h.

◆ OnSynchronize()

void operations_research::BasePathFilter::OnSynchronize ( const Assignment * delta)
overridevirtual

Subclasses of BasePathFilter might not propagate injected objective values so making sure it is done here (can be done again by the subclass if needed). This code supposes that path starts didn't change.

New unperformed node (its previous start isn't unassigned).

Reimplemented from operations_research::IntVarLocalSearchFilter.

Definition at line 443 of file routing_filters.cc.

◆ PathStartTouched()

bool operations_research::BasePathFilter::PathStartTouched ( int64_t start) const
inlineprotected

Definition at line 162 of file routing_filters.h.

◆ Rank()

int operations_research::BasePathFilter::Rank ( int64_t node) const
inlineprotected

Definition at line 157 of file routing_filters.h.

◆ Start()

int64_t operations_research::BasePathFilter::Start ( int i) const
inlineprotected

Definition at line 155 of file routing_filters.h.

Member Data Documentation

◆ kUnassigned

const int64_t operations_research::BasePathFilter::kUnassigned = -1
staticprotected

Definition at line 147 of file routing_filters.h.

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