THE COLUMN SUBTRACTION ALGORITHM - AN EXACT METHOD FOR SOLVING WEIGHTED SET COVERING, PACKING AND PARTITIONING PROBLEMS

We present a new and conceptually simple approach for finding exact so lutions to large set covering, packing and partitioning problems. The proposed algorithm is based on a new method, called the column subtrac tion (or row sum) method. First, a linear programming relaxation of th e set problem is solved to optimality, using a specialized version of the pivot and probe algorithm of Sethi and Thompson, which has proved to be very effective in avoiding the massive degeneracy typical of the se problems. Then, the column subtraction branch and bound method, whi ch proceeds by subtracting certain non-basic columns of the final simp lex 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 qui ckly. Computational comparisons, based upon problems having up to 9000 variables and 800 constraints, highlight the effective overall perfor mance of the column subtraction algorithm.