This chapter describes how to build a greedy heuristic for a set covering problem, e.g., the miplib problem fast0507. A more general (and efficient) version of the heuristic is in `CbcHeuristicGreedy.hpp` and `CbcHeuristicGreedy.cpp` located in the `COIN/Cbc/Samples` directory, see Chapter 8, *
More Samples
*.

The greedy heuristic will leave all variables taking value one at this node of the tree at value one, and will initially set all other variables to value zero. All variables are then sorted in order of their cost divided by the number of entries in rows which are not yet covered. (We may randomize that value a bit so that ties will be broken in different ways on different runs of the heuristic.) The best one is choosen, and set to one. The process is repeated. Because this is a set covering problem (i.e., all constraints are ≥), the heuristic is guaranteed to find a solution (but not necessarily an improved solution). The speed of the heuristic could be improved by just redoing those affected, but for illustrative purposes we will keep it simple. (The speed could also be improved if all elements are 1.0).

The key `CbcHeuristic` method is `int solution(double & solutionValue,
double * betterSolution)`.
The `solution()` method returns 0 if no solution found, and returns 1 if a solution is found, in which case it fills in the objective value and primal solution. The code in `CbcHeuristicGreedy.cpp` is a little more complicated than this following example. For instance, the code here assumes all variables are integer. The important bit of data is a copy of the matrix (stored by column) before any cuts have been made. The data used are bounds, objective and the matrix plus two work arrays.

The `newSolution` is then initialized to the rounded down solution.