The authors present a new and conceptually simple approach for finding exact solutions to large set covering, packing and partitioning problems. The proposed algorithm is based on a new method, called the column subtraction (or row sum) method. First, a linear programming relaxation of the set problem is solved to optimality, using a specialized version of the pivot and prove algorithm of Sethi and Thompson, which has proved to be very effective in avoiding the massive degeneracy typical of these problems. Then, the column subtraction branch and bound method, which proceeds by subtracting certain non-basic columns of the final simplex tableau, one at a time from the right hand side column, is used to produce optimal integer solutions. The algorithm begins with a novel greedy heuristic that makes use of only the nonbasic surplus variables for the column subtractions, and which generates excellent bounds quickly. Computational comparisons, based upon problems having up to 9000 variables and 800 constraints, highlight the effective overall performance of the column subtraction algorithm.
