![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#include <set_cover_heuristics.h>
Public Member Functions | |
LazySteepestSearch (SetCoverInvariant *inv) | |
LazySteepestSearch (SetCoverInvariant *inv, absl::string_view name) | |
bool | NextSolution (const SubsetBoolVector &in_focus) final |
LazySteepestSearch. | |
bool | NextSolution (absl::Span< const SubsetIndex > focus) final |
bool | NextSolution () final |
Virtual methods that must be implemented by derived classes. | |
Public Member Functions inherited from operations_research::BoolVectorBasedSolutionGenerator | |
BoolVectorBasedSolutionGenerator (SetCoverInvariant *inv, SetCoverInvariant::ConsistencyLevel consistency_level, absl::string_view class_name, absl::string_view name) | |
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. |
Lazy Steepest Search is a variant of Steepest Search that does not use any priority queue to update the priorities of the subsets. The priorities are computed when needed. It is faster to compute because there are relatively few subsets in the solution, because the cardinality of the solution is bounded by the number of elements.
Definition at line 390 of file set_cover_heuristics.h.
|
inlineexplicit |
Definition at line 392 of file set_cover_heuristics.h.
|
inline |
Definition at line 395 of file set_cover_heuristics.h.
|
inlinefinalvirtual |
Virtual methods that must be implemented by derived classes.
Computes the next full solution taking into account all the subsets.
Reimplemented from operations_research::BoolVectorBasedSolutionGenerator.
Definition at line 222 of file set_cover_heuristics.h.
|
inlinefinalvirtual |
Computes the next partial solution considering only the subsets whose indices are in focus.
Reimplemented from operations_research::BoolVectorBasedSolutionGenerator.
Definition at line 218 of file set_cover_heuristics.h.
|
finalvirtual |
First part of the trick: Since the heuristic is greedy, it only considers subsets that are selected and in_focus.
Second part of the trick: ComputeIsRedundant is expensive, but it is going to be called only once per subset in the solution. Once this has been done, there is no need to update any priority queue, nor to use a stronger level of consistency than kCostAndCoverage. In the non-lazy version, the redundancy of a subset may be updated many times and the priority queue must be updated accordingly, including just for removing the subset that was just considered, A possible optimization would be to sort the elements by coverage and run ComputeIsRedundant with the new element order. This would make the subsets which cover only one element easier to prove non-redundant.
Reimplemented from operations_research::BoolVectorBasedSolutionGenerator.
Definition at line 529 of file set_cover_heuristics.cc.