Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | List of all members
operations_research::GreedySolutionGenerator Class Reference

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

#include <set_cover_heuristics.h>

Public Member Functions

 GreedySolutionGenerator (SetCoverInvariant *inv)
 
bool NextSolution ()
 GreedySolutionGenerator.
 
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.

The first solution is obtained using the Chvatal heuristic, that guarantees that the solution is at most 1 + log(n) times the optimal value. Vasek Chvatal, 1979. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233-235, 1979. http://www.jstor.org/stable/3689577

Chvatal's heuristic works as follows: Choose the subset that covers as many remaining uncovered elements as possible for the least possible cost per element and iterate.

The following papers dive into the details of this class of algorithms.

Young, Neal E. 2008. “Greedy Set-Cover Algorithms.” In Encyclopedia of Algorithms, 379–81. Boston, MA: Springer US. Draft at: http://www.cs.ucr.edu/~neal/non_arxiv/Young08SetCover.pdf

Cormode, Graham, Howard Karloff, and Anthony Wirth. 2010. “Set Cover Algorithms for Very Large Datasets.” In CIKM ’10. ACM Press. https://doi.org/10.1145/1871437.1871501.

Definition at line 114 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ GreedySolutionGenerator()

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

Definition at line 116 of file set_cover_heuristics.h.

Member Function Documentation

◆ NextSolution() [1/3]

bool operations_research::GreedySolutionGenerator::NextSolution ( )

GreedySolutionGenerator.

Returns true if a solution was found.

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

Definition at line 96 of file set_cover_heuristics.cc.

◆ NextSolution() [2/3]

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

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

Definition at line 101 of file set_cover_heuristics.cc.

◆ NextSolution() [3/3]

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

Same with a different set of costs.

NOMUTANTS – reason, for C++

The priority queue maintains the maximum number of elements covered by unit of cost. We chose 16 as the arity of the heap after some testing.

Todo
(user): research more about the best value for Arity.

NOMUTANTS – reason, for C++

Don't expect pq to be empty, because of the break in the while loop.

Definition at line 106 of file set_cover_heuristics.cc.

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