This describes how to build a greedy heuristic for a set covering problem.
A more general version is in `CbcHeuristicGreedy.hpp` and
`CbcHeuristicGreedy.cpp` which can be found in the `COIN/Cbc/Samples` directory, see Chapter 6, *
More Samples
*.
The heuristic we will code will leave all variables which are at one at this node of the
tree to that value and will
initially set all others to zero. We then sort all variables 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.
We then choose the best one and set it to one and repeat the exercise. Because this is
a set covering problem ≥ we are guaranteed to find a solution (not necessarily a
better one though). We could
improve the speed by just redoing those affected but in this text we will keep it simple.
Also if all elements are 1.0 then we could do faster.
The key CbcHeuristic method is `int solution(double & solutionValue,
double * betterSolution)`
which returns 0 if no solution found and 1 if found when it fills in the objective value
and primal solution. The actual code in `CbcHeuristicGreedy.cpp` is
a little more complicated but this will work and gives the basic idea. 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.

Then we initialize newSolution as rounded down solution.

We have finished so now we need to see if solution is better and doublecheck we are feasible.