Geodesic
Estimates for the average number of iterations for some algorithms for solving the set packing problem
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 2, pp. 242-248

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{ZVMMF_2010_50_2_a3,
     author = {L. A. Zaozerskaya and A. A. Kolokolov},
     title = {Estimates for the average number of iterations for some algorithms for solving the set packing problem},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {242--248},
     publisher = {mathdoc},
     volume = {50},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_2_a3/}
}
TY  - JOUR
AU  - L. A. Zaozerskaya
AU  - A. A. Kolokolov
TI  - Estimates for the average number of iterations for some algorithms for solving the set packing problem
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 242
EP  - 248
VL  - 50
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_2_a3/
LA  - ru
ID  - ZVMMF_2010_50_2_a3
ER  - 
%0 Journal Article
%A L. A. Zaozerskaya
%A A. A. Kolokolov
%T Estimates for the average number of iterations for some algorithms for solving the set packing problem
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 242-248
%V 50
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_2_a3/
%G ru
%F ZVMMF_2010_50_2_a3
L. A. Zaozerskaya; A. A. Kolokolov. Estimates for the average number of iterations for some algorithms for solving the set packing problem. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 2, pp. 242-248. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_2_a3/