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 
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/
@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},
     year = {2010},
     volume = {50},
     number = {2},
     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
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
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_2_a3/
%G ru
%F ZVMMF_2010_50_2_a3

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.

[1] Saiko L. A., “Issledovanie moschnosti $L$-nakrytii nekotorykh zadach o pokrytii”, Diskretnaya optimizatsiya i analiz slozhnykh sistem, VTs SO AN SSSR, Novosibirsk, 1989, 76–97

[2] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, Mir, M., 1981

[3] Nemhauser G. L., Wolsey L. A., Integer and combinatorial optimization, John Wiley Sons, inc., 1999 | MR

[4] Shevchenko V. N., Kachestvennye voprosy tselochislennogo programmirovaniya, Fizmatlit, M., 1995 | MR | Zbl

[5] Kolokolov A. A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sibirskii zhurnal issl. operatsii, 1:2 (1994), 18–39 | MR | Zbl

[6] Kolokolov A. A., Devyaterikova M. V., Zaozerskaya L. A., Regulyarnye razbieniya v tselochislennom programmirovanii, Uch. posobie, Izd-vo OmGU, Omsk, 2007

[7] Zaozerskaya L. A., Kolokolov A. A., “O srednem chisle iteratsii nekotorykh algoritmov dlya resheniya zadachi ob upakovke mnozhestva”, Metody optimizatsii i ikh prilozh., Materialy XIV Baikalskoi mezhdunar. shkoly-seminara, v. 1, Irkutsk, 2008, 388–395

[8] Kuzyurin N. N., Fomin S. A., Effektivnye algoritmy i slozhnost vychislenii, MFTI, M., 2007

[9] Khu T., Tselochislennoe programmirovanie i potoki v setyakh, Mir, M., 1974 | MR