Upper Bounds on the Average Number of Iterations for SomeAlgorithms of Solving the Set Packing Problem

摘要

The set packing problem and the corresponding integer linear programming model areconsidered. Using the regular partitioning method and available estimates of the average number offeasible solutions of this problem, upper bounds on the average number of iterations for the firstGomory method, the branch-and-bound method (the Land and Doig scheme), and the L-class enu-meration algorithm are obtained. The possibilities of using the proposed approach for other integerprograms are discussed.