![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#include <set_cover_heuristics.h>
Public Member Functions | |
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. | |
virtual bool | NextSolution ()=0 |
Virtual methods that must be implemented by derived classes. | |
virtual bool | NextSolution (absl::Span< const SubsetIndex > focus)=0 |
virtual bool | NextSolution (const SubsetBoolVector &in_focus)=0 |
Same as above, but with a vector of Booleans as focus. | |
bool | CheckInvariantConsistency () const |
Protected Member Functions | |
SetCoverModel * | model () const |
Accessors. | |
BaseInt | num_subsets () const |
double | time_limit_in_seconds () const |
The time limit in seconds. |
Protected Attributes | |
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. |
Solver classes for the weighted set covering problem.
The solution procedure is based on the general scheme known as local search. Once a solution exists, it is improved by modifying it slightly, for example by flipping a binary variable, so as to minimize the cost. But first, we have to generate a first solution that is as good as possible.
The first solution is then improved by using local search descent, which eliminates the S_j's that have no interest in the solution.
A mix of the guided local search (GLS) and Tabu Search (TS) metaheuristic is also provided.
The term 'focus' hereafter means a subset of the S_j's designated by their indices. Focus make it possible to run the algorithms on the corresponding subproblems. Base class for all set cover solution generators. This is almost an interface.
Definition at line 51 of file set_cover_heuristics.h.
|
inline |
By default, the maximum number of iterations is set to infinity, and the maximum time in seconds is set to infinity as well (and the time limit is not yet implemented).
Definition at line 56 of file set_cover_heuristics.h.
|
virtualdefault |
bool operations_research::SetCoverSolutionGenerator::CheckInvariantConsistency | ( | ) | const |
Definition at line 45 of file set_cover_heuristics.cc.
|
inline |
Returns the name of the class.
Definition at line 112 of file set_cover_heuristics.h.
|
inline |
Returns the current cost of the solution in the invariant.
Definition at line 115 of file set_cover_heuristics.h.
|
inline |
Definition at line 72 of file set_cover_heuristics.h.
|
inline |
Returns the maximum number of iterations.
Definition at line 88 of file set_cover_heuristics.h.
|
inlineprotected |
Accessors.
Definition at line 133 of file set_cover_heuristics.h.
|
inline |
Returns the name of the heuristic.
Definition at line 109 of file set_cover_heuristics.h.
|
pure virtual |
Virtual methods that must be implemented by derived classes.
Computes the next full solution taking into account all the subsets.
Implemented in operations_research::BoolVectorBasedSolutionGenerator, operations_research::ElementDegreeSolutionGenerator, operations_research::GreedySolutionGenerator, operations_research::GuidedLocalSearch, operations_research::GuidedTabuSearch, operations_research::LazyElementDegreeSolutionGenerator, operations_research::LazySteepestSearch, operations_research::RandomSolutionGenerator, operations_research::SetCoverLagrangian, operations_research::SetCoverMip, operations_research::SteepestSearch, operations_research::SubsetListBasedSolutionGenerator, and operations_research::TrivialSolutionGenerator.
|
pure virtual |
Computes the next partial solution considering only the subsets whose indices are in focus.
Implemented in operations_research::BoolVectorBasedSolutionGenerator, operations_research::ElementDegreeSolutionGenerator, operations_research::GreedySolutionGenerator, operations_research::GuidedLocalSearch, operations_research::GuidedTabuSearch, operations_research::LazyElementDegreeSolutionGenerator, operations_research::LazySteepestSearch, operations_research::RandomSolutionGenerator, operations_research::SetCoverLagrangian, operations_research::SetCoverMip, operations_research::SteepestSearch, operations_research::SubsetListBasedSolutionGenerator, and operations_research::TrivialSolutionGenerator.
|
pure virtual |
Same as above, but with a vector of Booleans as focus.
Implemented in operations_research::BoolVectorBasedSolutionGenerator, operations_research::ElementDegreeSolutionGenerator, operations_research::GreedySolutionGenerator, operations_research::GuidedLocalSearch, operations_research::GuidedTabuSearch, operations_research::LazyElementDegreeSolutionGenerator, operations_research::LazySteepestSearch, operations_research::RandomSolutionGenerator, operations_research::SetCoverLagrangian, operations_research::SetCoverMip, operations_research::SteepestSearch, operations_research::SubsetListBasedSolutionGenerator, and operations_research::TrivialSolutionGenerator.
|
inlineprotected |
Definition at line 134 of file set_cover_heuristics.h.
|
inlinevirtual |
Resets the limits to their default values.
Definition at line 75 of file set_cover_heuristics.h.
|
inline |
Definition at line 96 of file set_cover_heuristics.h.
|
inline |
Returns the total elapsed runtime in microseconds.
Definition at line 104 of file set_cover_heuristics.h.
|
inline |
Returns the total elapsed runtime in seconds.
Definition at line 99 of file set_cover_heuristics.h.
|
inline |
Sets the maximum number of iterations.
Definition at line 82 of file set_cover_heuristics.h.
|
inline |
Definition at line 70 of file set_cover_heuristics.h.
|
inline |
Sets the time limit in seconds.
Definition at line 91 of file set_cover_heuristics.h.
|
inlineprotected |
The time limit in seconds.
Definition at line 137 of file set_cover_heuristics.h.
|
protected |
The consistency needed by the solution generator.
Definition at line 143 of file set_cover_heuristics.h.
|
protected |
run_time_ is an abstract duration for the time spent in NextSolution().
Definition at line 140 of file set_cover_heuristics.h.