operations_research::LazyElementDegreeSolutionGenerator Class Reference

Detailed Description

Solution generator based on the degree of elements. The heuristic is the same as ElementDegreeSolutionGenerator, but the number of uncovered elements for a subset is computed on-demand. In empirical tests, this is faster than ElementDegreeSolutionGenerator because a very small percentage of need to be computed, and even fewer among them need to be computed again later on. Because the number of uncovered elements is computed on-demand, the consistency level only needs to be set to kCostAndCoverage.

Definition at line 347 of file set_cover_heuristics.h.

#include <set_cover_heuristics.h>

Inheritance diagram for operations_research::LazyElementDegreeSolutionGenerator:

Public Member Functions
	LazyElementDegreeSolutionGenerator (SetCoverInvariant *inv)
	LazyElementDegreeSolutionGenerator (SetCoverInvariant *inv, absl::string_view name)
bool	NextSolution (const SubsetBoolVector &in_focus) final
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.

Constructor & Destructor Documentation

LazyElementDegreeSolutionGenerator() [1/2]

operations_research::LazyElementDegreeSolutionGenerator::LazyElementDegreeSolutionGenerator ( SetCoverInvariant * inv )

inlineexplicit

Definition at line 350 of file set_cover_heuristics.h.

LazyElementDegreeSolutionGenerator() [2/2]

operations_research::LazyElementDegreeSolutionGenerator::LazyElementDegreeSolutionGenerator ( SetCoverInvariant * inv, absl::string_view name )

inline

Definition at line 353 of file set_cover_heuristics.h.

Member Function Documentation

NextSolution() [1/3]

bool operations_research::BoolVectorBasedSolutionGenerator::NextSolution ( )

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.

NextSolution() [2/3]

bool operations_research::BoolVectorBasedSolutionGenerator::NextSolution ( absl::Span< const SubsetIndex > focus )

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.

NextSolution() [3/3]

bool operations_research::LazyElementDegreeSolutionGenerator::NextSolution ( const SubsetBoolVector & in_focus )

finalvirtual

LazyElementDegreeSolutionGenerator. There is no need to use a priority queue here, as the ratios are computed on-demand. Also elements are sorted based on degree once and for all and moved past when the elements become already covered.

Create the list of all the indices in the problem.

No need to cover an element that is already covered.

If the ratio with the initial number elements is greater, we skip this subset.

Same as ElementDegreeSolutionGenerator.

Reimplemented from operations_research::BoolVectorBasedSolutionGenerator.

Definition at line 424 of file set_cover_heuristics.cc.

---

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

• ortools/set_cover/set_cover_heuristics.h
• ortools/set_cover/set_cover_heuristics.cc