Home > Information Control Problems in Manufacturing > 13th IFAC Symposium on Information Control Problems in Manufacturing > On Average Number of Iterations of Some Algorithms for Solving the Set Packing Problem
» Download Article
Document
Reference
On Average Number of Iterations of Some Algorithms for Solving the Set Packing Problem
Information Control Problems in Manufacturing, Volume # 13 | Part# 1
Location: V.A. Trapeznikov Institute of Control Sciences, Russia
National Organizing Committee Chair: Bakhtadze, Natalia,
Dozortsev, Victor
International Program Committee Chair: Dolgui, Alexandre,
Pereira, Carlos Eduardo,
Mirkin, Evgeny A. ,
Kostyukov, Valentin E.
Conference Editor: Bakhtadze, Natalia,
Dolgui, Alexandre
Authors
Kolokolov, Alexander; Zaozerskaya, Lidia
Digital Object Identifier (DOI)
10.3182/20090603-3-RU-2001.00249
Page Numbers:
1510-1513
Index Terms
Integer Linear Programming; Branch and Bound; Mathematical Approaches for Scheduling
Abstract
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.
References
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).