#include <set_cover_heuristics.h>

Public Member Functions
	LazyElementDegreeSolutionGenerator (SetCoverInvariant *inv)

bool	NextSolution ()

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

bool	NextSolution (absl::Span< const SubsetIndex > focus, const SubsetCostVector &costs)
	Same with a different set of costs.

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 seems to be 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 179 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ LazyElementDegreeSolutionGenerator()

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

inlineexplicit

Definition at line 181 of file set_cover_heuristics.h.

Member Function Documentation

◆ NextSolution() [1/3]

bool operations_research::LazyElementDegreeSolutionGenerator::NextSolution ( )

Returns true if a solution was found.

Todo: (user): Add time-outs and exit with a partial solution.

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.

Definition at line 440 of file set_cover_heuristics.cc.

◆ NextSolution() [2/3]

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

Computes the next partial solution considering only the subsets whose indices are in focus.

Definition at line 446 of file set_cover_heuristics.cc.

◆ NextSolution() [3/3]

bool operations_research::LazyElementDegreeSolutionGenerator::NextSolution	(	absl::Span< const SubsetIndex >	focus,
		const SubsetCostVector &	costs )

Same with a different set of costs.

Definition at line 453 of file set_cover_heuristics.cc.

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

ortools/algorithms/set_cover_heuristics.h
ortools/algorithms/set_cover_heuristics.cc