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

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

#include <set_cover_heuristics.h>

Public Member Functions

 GuidedLocalSearch (SetCoverInvariant *inv)
 
void Initialize ()
 Initializes the Guided Local 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)
 

Detailed Description

The consistency level is maintained up to kRedundancy.

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. At each iteration, the algorithm selects a subset from the focus with maximum utility of penalization and penalizes it. It has been observed that good values for the penalisation factor can be found by dividing the value of the objective function of a local minimum with the number of features present in it [1]. In our case, the penalisation factor is the sum of the costs of the subsets selected in the focus divided by the number of subsets in the focus times a tunable factor alpha_. [1] C. Voudouris (1997) "Guided local search for combinatorial optimisation problems", PhD Thesis, University of Essex, Colchester, UK, July, 1997.

Definition at line 409 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ GuidedLocalSearch()

operations_research::GuidedLocalSearch::GuidedLocalSearch ( SetCoverInvariant * inv)
inlineexplicit

Definition at line 411 of file set_cover_heuristics.h.

Member Function Documentation

◆ Initialize()

void operations_research::GuidedLocalSearch::Initialize ( )

Initializes the Guided Local Search algorithm.

Guided Local Search.

Definition at line 711 of file set_cover_heuristics.cc.

◆ NextSolution() [1/3]

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

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

Improve current solution respective to the current penalties.

Getting the subset with highest utility. utility_heap_ is not empty, because we just inserted a pair.

Get removable subsets (Add them to the heap).

Get new non removable subsets and remove them from the heap. This is when the priority_heap_ can become empty and end the outer loop early.

Improve the solution by removing redundant subsets.

Definition at line 741 of file set_cover_heuristics.cc.

◆ NextSolution() [2/3]

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

◆ NextSolution() [3/3]

bool operations_research::GuidedLocalSearch::NextSolution ( int num_iterations)

Returns the next solution by running the Guided Local algorithm for maximum num_iterations iterations.

Definition at line 726 of file set_cover_heuristics.cc.

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