Upper bounds on the average number of iterations for some algorithms of solving the set packing problem |
| |
Authors: | L A Zaozerskaya A A Kolokolov |
| |
Institution: | 1.Omsk Division of the Institute of Mathematics, Siberian Branch,Russian Academy of Sciences,Omsk,Russia |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|