#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

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 cost. The newly-covered elements degree are also updated.

Definition at line 190 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ ElementDegreeSolutionGenerator()

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

inlineexplicit

Definition at line 192 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 181 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 187 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 194 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