 |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
The consistency level is maintained up to kRedundancy. More...
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 568 of file set_cover_heuristics.h.
#include <set_cover_heuristics.h>
Public Member Functions | |
| GuidedLocalSearch (SetCoverInvariant *inv) | |
| GuidedLocalSearch (SetCoverInvariant *inv, absl::string_view name) | |
| void | Initialize () |
| Initializes the Guided Local Search algorithm. | |
| bool | NextSolution (absl::Span< const SubsetIndex > focus) final |
| 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. | |
|
inlineexplicit |
Definition at line 570 of file set_cover_heuristics.h.
|
inline |
Definition at line 573 of file set_cover_heuristics.h.
| void operations_research::GuidedLocalSearch::Initialize | ( | ) |
Initializes the Guided Local Search algorithm.
Guided Local Search.
Definition at line 710 of file set_cover_heuristics.cc.
|
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.
|
finalvirtual |
Computes the next partial solution considering only the subsets whose indices are in focus.
Improve current solution respective to the current penalties by flipping the best subset.
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.
Implements operations_research::SetCoverSolutionGenerator.
Definition at line 735 of file set_cover_heuristics.cc.
|
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.
1.14.0