operations_research::GuidedTabuSearch Class Reference

#include <set_cover.h>

Public Member Functions
	GuidedTabuSearch (SetCoverInvariant *inv)
void	Initialize ()
	Initializes the Guided Tabu Search algorithm.
bool	NextSolution (int num_iterations)
bool	NextSolution (const std::vector< SubsetIndex > &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 191 of file set_cover.h.

Constructor & Destructor Documentation

GuidedTabuSearch()

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

inlineexplicit

Definition at line 193 of file set_cover.h.

Member Function Documentation

GetEpsilon()

double operations_research::GuidedTabuSearch::GetEpsilon ( ) const

inline

Definition at line 223 of file set_cover.h.

GetLagrangianFactor()

double operations_research::GuidedTabuSearch::GetLagrangianFactor ( ) const

inline

Definition at line 220 of file set_cover.h.

GetPenaltyFactor()

double operations_research::GuidedTabuSearch::GetPenaltyFactor ( ) const

inline

Definition at line 227 of file set_cover.h.

GetTabuListSize()

int operations_research::GuidedTabuSearch::GetTabuListSize ( ) const

inline

Definition at line 230 of file set_cover.h.

Initialize()

void operations_research::GuidedTabuSearch::Initialize

(

)

Initializes the Guided Tabu Search algorithm.

Guided Tabu Search.

Definition at line 186 of file set_cover.cc.

NextSolution() [1/2]

bool operations_research::GuidedTabuSearch::NextSolution	(	const std::vector< 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 230 of file set_cover.cc.

NextSolution() [2/2]

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 226 of file set_cover.cc.

SetEpsilon()

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

inline

Definition at line 222 of file set_cover.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 219 of file set_cover.h.

SetPenaltyFactor()

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

inline

Setters and getters for the Guided Tabu Search algorithm parameters.

Definition at line 226 of file set_cover.h.

SetTabuListSize()

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

inline

Definition at line 229 of file set_cover.h.

---

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

• ortools/algorithms/set_cover.h
• ortools/algorithms/set_cover.cc