Upper bounds on the average number of iterations for some algorithms of solving the set packing problem

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