Google OR-Tools v9.11
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

#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

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

Constructor & Destructor Documentation

◆ GuidedLocalSearch()

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

Definition at line 415 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 445 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.

Get removable subsets (Add them to the heap).

Get new non removable subsets. (Delete them from the heap)

Improve the solution by removing redundant subsets.

Definition at line 475 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 460 of file set_cover_heuristics.cc.

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