The consistency level is maintained up to kFreeAndUncovered. More...

Detailed Description

The consistency level is maintained up to kFreeAndUncovered.

As usual and well-known with local search, SteepestSearch reaches a local minimum. We therefore implement Guided Tabu Search, which is a crossover of Guided Local Search and Tabu Search.

Guided Local Search penalizes the parts of the solution that have been often used. It behaves as a long-term memory which "learns" the most used features and introduces some diversification in the search.

C. Voudouris (1997) "Guided local search for combinatorial optimisation problems", PhD Thesis, University of Essex, Colchester, UK, July, 1997.

Tabu Search makes it possible to degrade the solution temporarily by disallowing to go back for a certain time (changes are put in a "Tabu" list).

Tabu behaves like a short-term memory and is the intensification part of the local search metaheuristic.

F. Glover (1989) "Tabu Search – Part 1". ORSA Journal on Computing. 1 (2):190–206. doi:10.1287/ijoc.1.3.190. F. Glover (1990) "Tabu Search – Part 2". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4.

Definition at line 476 of file set_cover_heuristics.h.

#include <set_cover_heuristics.h>

Inheritance diagram for operations_research::GuidedTabuSearch:

Public Member Functions
	GuidedTabuSearch (SetCoverInvariant *inv)
	GuidedTabuSearch (SetCoverInvariant *inv, absl::string_view name)
void	Initialize ()
	Initializes the Guided Tabu Search algorithm.
bool	NextSolution (absl::Span< const SubsetIndex > focus) final
void	SetLagrangianFactor (double factor)
double	GetLagrangianFactor () const
void	SetEpsilon (double r)
double	GetEpsilon () const
void	SetPenaltyFactor (double factor)
	Setters and getters for the Guided Tabu Search algorithm parameters.
double	GetPenaltyFactor () const
void	SetTabuListSize (int size)
int	GetTabuListSize () const
bool	NextSolution () final
	Virtual methods that must be implemented by derived classes.
bool	NextSolution (const SubsetBoolVector &in_focus) final
	Same as above, but with a vector of Booleans as focus.
Public Member Functions inherited from operations_research::SubsetListBasedSolutionGenerator
	SubsetListBasedSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name)
bool	NextSolution (absl::Span< const SubsetIndex > _) override
bool	NextSolution () final
	Virtual methods that must be implemented by derived classes.
bool	NextSolution (const SubsetBoolVector &in_focus) final
	Same as above, but with a vector of Booleans as focus.
Public Member Functions inherited from operations_research::SetCoverSolutionGenerator
	SetCoverSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name)
virtual	~SetCoverSolutionGenerator ()=default
void	SetName (const absl::string_view name)
SetCoverInvariant *	inv () const
virtual SetCoverSolutionGenerator &	ResetLimits ()
	Resets the limits to their default values.
SetCoverSolutionGenerator &	SetMaxIterations (int64_t max_iterations)
	Sets the maximum number of iterations.
int64_t	max_iterations () const
	Returns the maximum number of iterations.
SetCoverSolutionGenerator &	SetTimeLimitInSeconds (double seconds)
	Sets the time limit in seconds.
absl::Duration	run_time () const
double	run_time_in_seconds () const
	Returns the total elapsed runtime in seconds.
double	run_time_in_microseconds () const
	Returns the total elapsed runtime in microseconds.
std::string	name () const
	Returns the name of the heuristic.
std::string	class_name () const
	Returns the name of the class.
Cost	cost () const
	Returns the current cost of the solution in the invariant.
bool	CheckInvariantConsistency () const

Additional Inherited Members
Protected Member Functions inherited from operations_research::SetCoverSolutionGenerator
SetCoverModel *	model () const
	Accessors.
BaseInt	num_subsets () const
double	time_limit_in_seconds () const
	The time limit in seconds.
Protected Attributes inherited from operations_research::SetCoverSolutionGenerator
absl::Duration	run_time_
	run_time_ is an abstract duration for the time spent in NextSolution().
SetCoverInvariant::ConsistencyLevel	consistency_level_
	The consistency needed by the solution generator.

Constructor & Destructor Documentation

◆ GuidedTabuSearch() [1/2]

operations_research::GuidedTabuSearch::GuidedTabuSearch ( SetCoverInvariant * inv )

inlineexplicit

Definition at line 478 of file set_cover_heuristics.h.

◆ GuidedTabuSearch() [2/2]

operations_research::GuidedTabuSearch::GuidedTabuSearch	(	SetCoverInvariant *	inv,
		absl::string_view	name )

inline

Definition at line 481 of file set_cover_heuristics.h.

Member Function Documentation

◆ GetEpsilon()

double operations_research::GuidedTabuSearch::GetEpsilon ( ) const

inline

Definition at line 507 of file set_cover_heuristics.h.

◆ GetLagrangianFactor()

double operations_research::GuidedTabuSearch::GetLagrangianFactor ( ) const

inline

Definition at line 504 of file set_cover_heuristics.h.

◆ GetPenaltyFactor()

double operations_research::GuidedTabuSearch::GetPenaltyFactor ( ) const

inline

Definition at line 511 of file set_cover_heuristics.h.

◆ GetTabuListSize()

int operations_research::GuidedTabuSearch::GetTabuListSize ( ) const

inline

Definition at line 514 of file set_cover_heuristics.h.

◆ Initialize()

void operations_research::GuidedTabuSearch::Initialize ( )

Initializes the Guided Tabu Search algorithm.

Guided Tabu Search.

Definition at line 585 of file set_cover_heuristics.cc.

◆ NextSolution() [1/3]

bool operations_research::SubsetListBasedSolutionGenerator::NextSolution ( )

inlinefinalvirtual

Virtual methods that must be implemented by derived classes.

Computes the next full solution taking into account all the subsets.

Implements operations_research::SetCoverSolutionGenerator.

Definition at line 181 of file set_cover_heuristics.h.

◆ NextSolution() [2/3]

bool operations_research::GuidedTabuSearch::NextSolution ( absl::Span< const SubsetIndex > focus )

finalvirtual

Computes the next partial solution considering only the subsets whose indices are in focus.

Try to remove subset from solution, if the gain from removing is worth it:

and it can be removed, and

it is not Tabu OR decreases the actual cost (aspiration):

Try to use subset in solution, if its penalized delta is good.

The limit kMaxPossibleCost is ill-defined, there is always a best_subset. Is it intended?

Todo: (user): make the cost computation incremental.

Implements operations_research::SetCoverSolutionGenerator.

Definition at line 625 of file set_cover_heuristics.cc.

◆ NextSolution() [3/3]

bool operations_research::SubsetListBasedSolutionGenerator::NextSolution ( const SubsetBoolVector & in_focus )

inlinefinalvirtual

Same as above, but with a vector of Booleans as focus.

Implements operations_research::SetCoverSolutionGenerator.

Definition at line 183 of file set_cover_heuristics.h.

◆ SetEpsilon()

void operations_research::GuidedTabuSearch::SetEpsilon ( double r )

inline

Definition at line 506 of file set_cover_heuristics.h.

◆ SetLagrangianFactor()

void operations_research::GuidedTabuSearch::SetLagrangianFactor ( double factor )

inline

Todo: (user): re-introduce this is the code. It was used to favor subsets with the same marginal costs but that would cover more elements. But first, see if it makes sense to compute it.

Definition at line 503 of file set_cover_heuristics.h.

◆ SetPenaltyFactor()

void operations_research::GuidedTabuSearch::SetPenaltyFactor ( double factor )

inline

Setters and getters for the Guided Tabu Search algorithm parameters.

Definition at line 510 of file set_cover_heuristics.h.

◆ SetTabuListSize()

void operations_research::GuidedTabuSearch::SetTabuListSize ( int size )

inline

Definition at line 513 of file set_cover_heuristics.h.

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

ortools/set_cover/set_cover_heuristics.h
ortools/set_cover/set_cover_heuristics.cc

Detailed Description

Public Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ GuidedTabuSearch() [1/2]

◆ GuidedTabuSearch() [2/2]

Member Function Documentation

◆ GetEpsilon()

◆ GetLagrangianFactor()

◆ GetPenaltyFactor()

◆ GetTabuListSize()

◆ Initialize()

◆ NextSolution() [1/3]

◆ NextSolution() [2/3]

◆ NextSolution() [3/3]

◆ SetEpsilon()

◆ SetLagrangianFactor()

◆ SetPenaltyFactor()

◆ SetTabuListSize()