Google OR-Tools v9.11
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

#include <set_cover_heuristics.h>

Public Member Functions

 GreedySolutionGenerator (SetCoverInvariant *inv)
 
bool NextSolution ()
 GreedySolutionGenerator.
 
bool NextSolution (const std::vector< SubsetIndex > &focus)
 
bool NextSolution (const std::vector< SubsetIndex > &focus, const SubsetCostVector &costs)
 Same with a different set of costs.
 

Detailed Description

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 164 of file set_cover_heuristics.h.

Constructor & Destructor Documentation

◆ GreedySolutionGenerator()

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

Definition at line 166 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 115 of file set_cover_heuristics.cc.

◆ NextSolution() [2/3]

bool operations_research::GreedySolutionGenerator::NextSolution ( const std::vector< SubsetIndex > & focus)

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

Definition at line 120 of file set_cover_heuristics.cc.

◆ NextSolution() [3/3]

bool operations_research::GreedySolutionGenerator::NextSolution ( const std::vector< 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 the queue to be empty, because of the break in the while loop.

Definition at line 125 of file set_cover_heuristics.cc.

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