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

The consistency level is maintained up to kFreeAndUncovered. More...

Detailed Description

The consistency level is maintained up to kFreeAndUncovered.

Solution generator based on the degree of elements. The degree of an element is the number of subsets covering it. The generator consists in iteratively choosing a non-covered element with the smallest degree, and selecting a subset that covers it with the least ratio cost / number of uncovered elements. The number of uncovered elements are updated for each impacted subset. The newly-covered elements degrees are also updated and set to zero.

Definition at line 324 of file set_cover_heuristics.h.

#include <set_cover_heuristics.h>

Inheritance diagram for operations_research::ElementDegreeSolutionGenerator:
operations_research::BoolVectorBasedSolutionGenerator operations_research::SetCoverSolutionGenerator

Public Member Functions

 ElementDegreeSolutionGenerator (SetCoverInvariant *inv)
 ElementDegreeSolutionGenerator (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)
SetCoverInvariantinv () const
virtual SetCoverSolutionGeneratorResetLimits ()
 Resets the limits to their default values.
SetCoverSolutionGeneratorSetMaxIterations (int64_t max_iterations)
 Sets the maximum number of iterations.
int64_t max_iterations () const
 Returns the maximum number of iterations.
SetCoverSolutionGeneratorSetTimeLimitInSeconds (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
SetCoverModelmodel () 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

◆ ElementDegreeSolutionGenerator() [1/2]

operations_research::ElementDegreeSolutionGenerator::ElementDegreeSolutionGenerator ( SetCoverInvariant * inv)
inlineexplicit

Definition at line 326 of file set_cover_heuristics.h.

◆ ElementDegreeSolutionGenerator() [2/2]

operations_research::ElementDegreeSolutionGenerator::ElementDegreeSolutionGenerator ( SetCoverInvariant * inv,
absl::string_view name )
inline

Definition at line 329 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::ElementDegreeSolutionGenerator::NextSolution ( const SubsetBoolVector & in_focus)
finalvirtual

ElementDegreeSolutionGenerator. 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.

Compare R = costs[subset] / num_free_elements with B = best_subset_cost / best_subset_num_free_elts. If R < B, we choose subset. If the ratios are the same, we choose the subset with the most free elements.

Todo
(user): What about adding a tolerance for equality, which could further favor larger columns?

Reimplemented from operations_research::BoolVectorBasedSolutionGenerator.

Definition at line 366 of file set_cover_heuristics.cc.


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