Skip to content

Latest commit

 

History

History

algorithms

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Various algorithms

This directory contains data structures and algorithms for various problems.

Set covering

An instance of set covering is composed of two entities: elements and sets; sets cover a series of elements. The problem of set covering is about finding the cheapest combination of sets that cover all the elements.

More information on Wikipedia.

Create an instance:

// If the elements are integers, a subset can be a std::vector<int> (in a pair
// along its cost).
std::vector<std::pair<std::vector<int>, int>> subsets = ...;

SetCoverModel model;
for (const auto [subset, subset_cost] : subsets) {
  model.AddEmptySubset(subset_cost)
  for (const int element : subset) {
    model.AddElementToLastSubset(element);
  }
}
SetCoverLedger ledger(&model);

Solve it using a MIP solver (guarantees to yield the optimum solution if it has enough time to run):

SetCoverMip mip(&ledger);
mip.SetTimeLimitInSeconds(10);
mip.NextSolution();
SubsetBoolVector best_choices = ledger.GetSolution();
LOG(INFO) << "Cost: " << ledger.cost();

A custom combination of heuristics (10,000 iterations of: clearing 10% of the variables, running a Chvatal greedy descent, using steepest local search):

Cost best_cost = std::numeric_limits<Cost>::max();
SubsetBoolVector best_choices = ledger.GetSolution();
for (int i = 0; i < 10000; ++i) {
  ledger.LoadSolution(best_choices);
  ClearRandomSubsets(0.1 * model.num_subsets().value(), &ledger);

  GreedySolutionGenerator greedy(&ledger);
  CHECK(greedy.NextSolution());

  SteepestSearch steepest(&ledger);
  CHECK(steepest.NextSolution(10000));

  EXPECT_TRUE(ledger.CheckSolution());
  if (ledger.cost() < best_cost) {
    best_cost = ledger.cost();
    best_choices = ledger.GetSolution();
    LOG(INFO) << "Better cost: " << best_cost << " at iteration = " << i;
  }
}
ledger.LoadSolution(best_choices);
LOG(INFO) << "Best cost: " << ledger.cost();