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

#include <set_cover_heuristics.h>

Public Member Functions
	ElementDegreeSolutionGenerator (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

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 degree are also updated and set to zero.

Definition at line 144 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ ElementDegreeSolutionGenerator()

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

inlineexplicit

Definition at line 146 of file set_cover_heuristics.h.

Member Function Documentation

◆ NextSolution() [1/3]

bool operations_research::ElementDegreeSolutionGenerator::NextSolution ( )

Returns true if a solution was found.

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

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.

Definition at line 365 of file set_cover_heuristics.cc.

◆ NextSolution() [2/3]

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

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

Definition at line 371 of file set_cover_heuristics.cc.

◆ NextSolution() [3/3]

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

Same with a different set of costs.

Definition at line 378 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