Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::SetCoverSolutionGenerator Class Referenceabstract

Detailed Description

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.

#include <set_cover_heuristics.h>

Inheritance diagram for operations_research::SetCoverSolutionGenerator:
operations_research::BoolVectorBasedSolutionGenerator operations_research::SubsetListBasedSolutionGenerator operations_research::ElementDegreeSolutionGenerator operations_research::LazyElementDegreeSolutionGenerator operations_research::LazySteepestSearch operations_research::SteepestSearch operations_research::GreedySolutionGenerator operations_research::GuidedLocalSearch operations_research::GuidedTabuSearch operations_research::RandomSolutionGenerator operations_research::SetCoverLagrangian operations_research::SetCoverMip operations_research::TrivialSolutionGenerator

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.

Constructor & Destructor Documentation

◆ SetCoverSolutionGenerator()

operations_research::SetCoverSolutionGenerator::SetCoverSolutionGenerator ( SetCoverInvariant * inv,
SetCoverInvariant::ConsistencyLevel consistency_level,
absl::string_view class_name,
absl::string_view name )
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.

◆ ~SetCoverSolutionGenerator()

virtual operations_research::SetCoverSolutionGenerator::~SetCoverSolutionGenerator ( )
virtualdefault

Member Function Documentation

◆ CheckInvariantConsistency()

bool operations_research::SetCoverSolutionGenerator::CheckInvariantConsistency ( ) const

Definition at line 45 of file set_cover_heuristics.cc.

◆ class_name()

std::string operations_research::SetCoverSolutionGenerator::class_name ( ) const
inline

Returns the name of the class.

Definition at line 112 of file set_cover_heuristics.h.

◆ cost()

Cost operations_research::SetCoverSolutionGenerator::cost ( ) const
inline

Returns the current cost of the solution in the invariant.

Definition at line 115 of file set_cover_heuristics.h.

◆ inv()

SetCoverInvariant * operations_research::SetCoverSolutionGenerator::inv ( ) const
inline

Definition at line 72 of file set_cover_heuristics.h.

◆ max_iterations()

int64_t operations_research::SetCoverSolutionGenerator::max_iterations ( ) const
inline

Returns the maximum number of iterations.

Definition at line 88 of file set_cover_heuristics.h.

◆ model()

SetCoverModel * operations_research::SetCoverSolutionGenerator::model ( ) const
inlineprotected

Accessors.

Definition at line 133 of file set_cover_heuristics.h.

◆ name()

std::string operations_research::SetCoverSolutionGenerator::name ( ) const
inline

Returns the name of the heuristic.

Definition at line 109 of file set_cover_heuristics.h.

◆ NextSolution() [1/3]

virtual bool operations_research::SetCoverSolutionGenerator::NextSolution ( )
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.

◆ NextSolution() [2/3]

virtual bool operations_research::SetCoverSolutionGenerator::NextSolution ( absl::Span< const SubsetIndex > focus)
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.

◆ NextSolution() [3/3]

virtual bool operations_research::SetCoverSolutionGenerator::NextSolution ( const SubsetBoolVector & in_focus)
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.

◆ num_subsets()

BaseInt operations_research::SetCoverSolutionGenerator::num_subsets ( ) const
inlineprotected

Definition at line 134 of file set_cover_heuristics.h.

◆ ResetLimits()

virtual SetCoverSolutionGenerator & operations_research::SetCoverSolutionGenerator::ResetLimits ( )
inlinevirtual

Resets the limits to their default values.

Definition at line 75 of file set_cover_heuristics.h.

◆ run_time()

absl::Duration operations_research::SetCoverSolutionGenerator::run_time ( ) const
inline

Definition at line 96 of file set_cover_heuristics.h.

◆ run_time_in_microseconds()

double operations_research::SetCoverSolutionGenerator::run_time_in_microseconds ( ) const
inline

Returns the total elapsed runtime in microseconds.

Definition at line 104 of file set_cover_heuristics.h.

◆ run_time_in_seconds()

double operations_research::SetCoverSolutionGenerator::run_time_in_seconds ( ) const
inline

Returns the total elapsed runtime in seconds.

Definition at line 99 of file set_cover_heuristics.h.

◆ SetMaxIterations()

SetCoverSolutionGenerator & operations_research::SetCoverSolutionGenerator::SetMaxIterations ( int64_t max_iterations)
inline

Sets the maximum number of iterations.

Definition at line 82 of file set_cover_heuristics.h.

◆ SetName()

void operations_research::SetCoverSolutionGenerator::SetName ( const absl::string_view name)
inline

Definition at line 70 of file set_cover_heuristics.h.

◆ SetTimeLimitInSeconds()

SetCoverSolutionGenerator & operations_research::SetCoverSolutionGenerator::SetTimeLimitInSeconds ( double seconds)
inline

Sets the time limit in seconds.

Definition at line 91 of file set_cover_heuristics.h.

◆ time_limit_in_seconds()

double operations_research::SetCoverSolutionGenerator::time_limit_in_seconds ( ) const
inlineprotected

The time limit in seconds.

Definition at line 137 of file set_cover_heuristics.h.

Member Data Documentation

◆ consistency_level_

SetCoverInvariant::ConsistencyLevel operations_research::SetCoverSolutionGenerator::consistency_level_
protected

The consistency needed by the solution generator.

Definition at line 143 of file set_cover_heuristics.h.

◆ run_time_

absl::Duration operations_research::SetCoverSolutionGenerator::run_time_
protected

run_time_ is an abstract duration for the time spent in NextSolution().

Definition at line 140 of file set_cover_heuristics.h.

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