On Average Number of Iterations of Some Algorithms for Solving the Set Packing Problem
Information Control Problems in Manufacturing, Volume # 13 | Part# 1
Kolokolov, Alexander; Zaozerskaya, Lidia
Digital Object Identifier (DOI)
Integer Linear Programming; Branch and Bound; Mathematical Approaches for Scheduling
We consider the set packing problem as a corresponding integer linear programming problem. For L-class enumeration algorithm and the first Gomory cutting plane algorithm we found the polynomial upper bounds on average iterations number. The regular partitions approach and known upper bounds on the average number of feasible solutions were used for the estimations.
Hu, T. (1974). Integer programming and network flows. Moscow, Mir. (in Russian). Kolokolov, A. (1994). Regular partitions and cuts in integer programming. Journal of Operational Research, 1(2), 18-39. (in Russian). Kolokolov, A. and Devyaterikova, M. (2006). On the stability of some integer programming algorithms. Operations Research Letters, 34, 149-154. Kuzurin, N. (1994). Polynomial algorithm on average in integer linear programming. Siberian Journal of Operational Research, 1(3), 38-48. (in Russian). Nemhauser, G. and Wolsey, L. (1999). Integer and combinatorial optimization. AWiley-Interscience Publication: John Wiley & Sons, inc. Saiko, L. (1989). The study of l-covering cardinality of some problems on covering. In Discrete optimization and analysis of complex systems, 76-97. Computation Centre of Acad.of Sc. (Siberian Department), USSR, Novosibirsk. (in Russian). Zaozerskaya, L. and Kolokolov, A. (2008). On average number of iterations of some algorithms for solving the set packing problem. In Materials of the 16th Baikal International Workshop "The methods of optimization and eir application", Vol. 1, Irkutsk, 388-395. (in Russian).