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

Generic filter-based heuristic applied to IntVars. More...

#include <routing_search.h>

Inheritance diagram for operations_research::IntVarFilteredHeuristic:
operations_research::RoutingFilteredHeuristic operations_research::CheapestAdditionFilteredHeuristic operations_research::CheapestInsertionFilteredHeuristic operations_research::ChristofidesFilteredHeuristic operations_research::SavingsFilteredHeuristic operations_research::ComparatorCheapestAdditionFilteredHeuristic operations_research::EvaluatorCheapestAdditionFilteredHeuristic operations_research::GlobalCheapestInsertionFilteredHeuristic operations_research::LocalCheapestInsertionFilteredHeuristic operations_research::ParallelSavingsFilteredHeuristic operations_research::SequentialSavingsFilteredHeuristic

Public Member Functions

 IntVarFilteredHeuristic (Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, LocalSearchFilterManager *filter_manager)
 — First solution heuristics —
 
virtual ~IntVarFilteredHeuristic ()=default
 
Assignment * BuildSolution ()
 
int64_t number_of_decisions () const
 
int64_t number_of_rejects () const
 
virtual std::string DebugString () const
 

Protected Member Functions

void ResetSolution ()
 Resets the data members for a new solution.
 
virtual void Initialize ()
 Initialize the heuristic; called before starting to build a new solution.
 
virtual bool InitializeSolution ()
 Virtual method to initialize the solution.
 
virtual bool BuildSolutionInternal ()=0
 Virtual method to redefine how to build a solution.
 
std::optional< int64_t > Evaluate (bool commit, bool ignore_upper_bound=false, bool update_upper_bound=true)
 
virtual bool StopSearch ()
 Returns true if the search must be stopped.
 
void SetValue (int64_t index, int64_t value)
 
const std::vector< int > & delta_indices () const
 Returns the indices of the nodes currently in the insertion delta.
 
int64_t Value (int64_t index) const
 
bool Contains (int64_t index) const
 Returns true if the variable of index 'index' is in the current solution.
 
IntVar * Var (int64_t index) const
 Returns the variable of index 'index'.
 
int64_t SecondaryVarIndex (int64_t index) const
 Returns the index of a secondary var.
 
bool HasSecondaryVars () const
 Returns true if there are secondary variables.
 
bool IsSecondaryVar (int64_t index) const
 Returns true if 'index' is a secondary variable index.
 
void SynchronizeFilters ()
 Synchronizes filters with an assignment (the current solution).
 

Protected Attributes

Assignment *const assignment_
 

Detailed Description

Generic filter-based heuristic applied to IntVars.

Definition at line 218 of file routing_search.h.

Constructor & Destructor Documentation

◆ IntVarFilteredHeuristic()

operations_research::IntVarFilteredHeuristic::IntVarFilteredHeuristic ( Solver * solver,
const std::vector< IntVar * > & vars,
const std::vector< IntVar * > & secondary_vars,
LocalSearchFilterManager * filter_manager )

— First solution heuristics —

IntVarFilteredHeuristic

Definition at line 462 of file routing_search.cc.

◆ ~IntVarFilteredHeuristic()

virtual operations_research::IntVarFilteredHeuristic::~IntVarFilteredHeuristic ( )
virtualdefault

Member Function Documentation

◆ BuildSolution()

Assignment * operations_research::IntVarFilteredHeuristic::BuildSolution ( )

Builds a solution. Returns the resulting assignment if a solution was found, and nullptr otherwise.

Initialize must be called before the state of the heuristic is changed, in particular before InitializeSolution() and BuildSolutionInternal().

Definition at line 494 of file routing_search.cc.

◆ BuildSolutionInternal()

virtual bool operations_research::IntVarFilteredHeuristic::BuildSolutionInternal ( )
protectedpure virtual

Virtual method to redefine how to build a solution.

Implemented in operations_research::CheapestAdditionFilteredHeuristic, operations_research::ChristofidesFilteredHeuristic, operations_research::GlobalCheapestInsertionFilteredHeuristic, operations_research::LocalCheapestInsertionFilteredHeuristic, and operations_research::SavingsFilteredHeuristic.

◆ Contains()

bool operations_research::IntVarFilteredHeuristic::Contains ( int64_t index) const
inlineprotected

Returns true if the variable of index 'index' is in the current solution.

Definition at line 277 of file routing_search.h.

◆ DebugString()

virtual std::string operations_research::IntVarFilteredHeuristic::DebugString ( ) const
inlinevirtual

Reimplemented in operations_research::ChristofidesFilteredHeuristic, operations_research::ComparatorCheapestAdditionFilteredHeuristic, operations_research::EvaluatorCheapestAdditionFilteredHeuristic, operations_research::GlobalCheapestInsertionFilteredHeuristic, operations_research::LocalCheapestInsertionFilteredHeuristic, operations_research::ParallelSavingsFilteredHeuristic, and operations_research::SequentialSavingsFilteredHeuristic.

Definition at line 235 of file routing_search.h.

◆ delta_indices()

const std::vector< int > & operations_research::IntVarFilteredHeuristic::delta_indices ( ) const
inlineprotected

Returns the indices of the nodes currently in the insertion delta.

Definition at line 270 of file routing_search.h.

◆ Evaluate()

std::optional< int64_t > operations_research::IntVarFilteredHeuristic::Evaluate ( bool commit,
bool ignore_upper_bound = false,
bool update_upper_bound = true )
protected

Evaluates the modifications to the current solution. If these modifications are "filter-feasible" returns their corresponding cost computed by filters. If 'commit' is true, the modifications are committed to the current solution. In any case all modifications to the internal delta are cleared before returning.

objective upper_bound_ is used to reduce the number of potential insertion candidates, specifically when filter_manager_ filters cost. Rationale: the best cost candidate will always be valid and will be inserted so no use accepting degrading ones. However when a candidate is committed, the upper bound is relaxed to make sure further (cost-degrading) insertions will be accepted (cf. SynchronizeFilters()).

Reset is_in_delta to all false.

Definition at line 539 of file routing_search.cc.

◆ HasSecondaryVars()

bool operations_research::IntVarFilteredHeuristic::HasSecondaryVars ( ) const
inlineprotected

Returns true if there are secondary variables.

Definition at line 288 of file routing_search.h.

◆ Initialize()

virtual void operations_research::IntVarFilteredHeuristic::Initialize ( )
inlineprotectedvirtual

Initialize the heuristic; called before starting to build a new solution.

Reimplemented in operations_research::LocalCheapestInsertionFilteredHeuristic.

Definition at line 241 of file routing_search.h.

◆ InitializeSolution()

virtual bool operations_research::IntVarFilteredHeuristic::InitializeSolution ( )
inlineprotectedvirtual

Virtual method to initialize the solution.

Definition at line 243 of file routing_search.h.

◆ IsSecondaryVar()

bool operations_research::IntVarFilteredHeuristic::IsSecondaryVar ( int64_t index) const
inlineprotected

Returns true if 'index' is a secondary variable index.

Definition at line 290 of file routing_search.h.

◆ number_of_decisions()

int64_t operations_research::IntVarFilteredHeuristic::number_of_decisions ( ) const
inline

Returns statistics on search, number of decisions sent to filters, number of decisions rejected by filters.

Definition at line 232 of file routing_search.h.

◆ number_of_rejects()

int64_t operations_research::IntVarFilteredHeuristic::number_of_rejects ( ) const
inline

Definition at line 233 of file routing_search.h.

◆ ResetSolution()

void operations_research::IntVarFilteredHeuristic::ResetSolution ( )
protected

Resets the data members for a new solution.

Wiping assignment when starting a new search.

Definition at line 484 of file routing_search.cc.

◆ SecondaryVarIndex()

int64_t operations_research::IntVarFilteredHeuristic::SecondaryVarIndex ( int64_t index) const
inlineprotected

Returns the index of a secondary var.

Definition at line 283 of file routing_search.h.

◆ SetValue()

void operations_research::IntVarFilteredHeuristic::SetValue ( int64_t index,
int64_t value )
inlineprotected

Modifies the current solution by setting the variable of index 'index' to value 'value'.

Definition at line 259 of file routing_search.h.

◆ StopSearch()

virtual bool operations_research::IntVarFilteredHeuristic::StopSearch ( )
inlineprotectedvirtual

Returns true if the search must be stopped.

Reimplemented in operations_research::RoutingFilteredHeuristic.

Definition at line 256 of file routing_search.h.

◆ SynchronizeFilters()

void operations_research::IntVarFilteredHeuristic::SynchronizeFilters ( )
protected

Synchronizes filters with an assignment (the current solution).

Resetting the upper bound to allow cost-increasing insertions.

Definition at line 588 of file routing_search.cc.

◆ Value()

int64_t operations_research::IntVarFilteredHeuristic::Value ( int64_t index) const
inlineprotected

Returns the value of the variable of index 'index' in the last committed solution.

Definition at line 273 of file routing_search.h.

◆ Var()

IntVar * operations_research::IntVarFilteredHeuristic::Var ( int64_t index) const
inlineprotected

Returns the variable of index 'index'.

Definition at line 281 of file routing_search.h.

Member Data Documentation

◆ assignment_

Assignment* const operations_research::IntVarFilteredHeuristic::assignment_
protected

Definition at line 294 of file routing_search.h.

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