Loading solver…

Set Cover - greedy heuristic

Problem: choose a minimum-cost collection of subsets whose union covers every required element.

Show code

import {
  GreedySolutionGenerator,
  SetCoverInvariant,
  SetCoverModel,
} from 'or-tools-wasm/set-cover';

const model = new SetCoverModel();
model.addEmptySubset(2.0);
model.addElementToLastSubset(0);
model.addEmptySubset(2.0);
model.addElementToLastSubset(1);
model.addEmptySubset(1.0);
model.addElementToLastSubset(0);
model.addElementToLastSubset(1);

const inv = new SetCoverInvariant(model);
const greedy = new GreedySolutionGenerator(inv);
const hasFound = await greedy.nextSolution(undefined, { executor: 'worker' });

if (hasFound) {
  const solution = inv.exportSolutionAsProto();
  console.log(solution.cost, solution.subset);
}

Elements are the things that must be covered.
Each colored region is a subset with a cost and a fixed list of covered elements.
The greedy heuristic chooses subsets until every element is covered, while trying to keep cost low.
After solving, chosen subsets and covered elements are highlighted.

Executor

Solution

Run the solver to view the solution.

Status: