operations_research::GuidedTabuSearch Class Reference

#include <set_cover_heuristics.h>

Public Member Functions
	GuidedTabuSearch (SetCoverInvariant *inv)
void	Initialize ()
	Initializes the Guided Tabu Search algorithm.
bool	NextSolution (int num_iterations)
bool	NextSolution (absl::Span< const SubsetIndex > focus, int num_iterations)
bool	NextSolution (const SubsetBoolVector &in_focus, int num_iterations)
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

Detailed Description

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 321 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

GuidedTabuSearch()

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

inlineexplicit

Definition at line 323 of file set_cover_heuristics.h.

Member Function Documentation

GetEpsilon()

double operations_research::GuidedTabuSearch::GetEpsilon ( ) const

inline

Definition at line 354 of file set_cover_heuristics.h.

GetLagrangianFactor()

double operations_research::GuidedTabuSearch::GetLagrangianFactor ( ) const

inline

Definition at line 351 of file set_cover_heuristics.h.

GetPenaltyFactor()

double operations_research::GuidedTabuSearch::GetPenaltyFactor ( ) const

inline

Definition at line 358 of file set_cover_heuristics.h.

GetTabuListSize()

int operations_research::GuidedTabuSearch::GetTabuListSize ( ) const

inline

Definition at line 361 of file set_cover_heuristics.h.

Initialize()

void operations_research::GuidedTabuSearch::Initialize

(

)

Initializes the Guided Tabu Search algorithm.

Guided Tabu Search.

Definition at line 321 of file set_cover_heuristics.cc.

NextSolution() [1/3]

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

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.

Definition at line 365 of file set_cover_heuristics.cc.

NextSolution() [2/3]

bool operations_research::GuidedTabuSearch::NextSolution	(	const SubsetBoolVector &	in_focus,
		int	num_iterations )

NextSolution() [3/3]

bool operations_research::GuidedTabuSearch::NextSolution

(

int

num_iterations

)

Returns the next solution by running the Tabu Search algorithm for maximum num_iterations iterations.

Definition at line 361 of file set_cover_heuristics.cc.

SetEpsilon()

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

inline

Definition at line 353 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 350 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 357 of file set_cover_heuristics.h.

SetTabuListSize()

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

inline

Definition at line 360 of file set_cover_heuristics.h.

---

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

• ortools/algorithms/set_cover_heuristics.h
• ortools/algorithms/set_cover_heuristics.cc