Geodesic
Investigation of one algorithm for solving problems of integer linear programming
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 140-145
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A famous algorithm for solving problems of integer linear programming based on the method of regular partitions is investigated. In particular, it is shown that the algorithm is regular with respect to some of such partitions in the case of problems that simplify its application. A subclass of matrices generating such problems is given. A family of problems of special form is constructed for which the algorithm is exponential with respect to the length of the input.
Keywords: integer programming, unimodular transformations, regular partitions. 
@article{TIMM_2010_16_3_a13,
     author = {A. A. Kolokolov and T. G. Orlovskaya},
     title = {Investigation of one algorithm for solving problems of integer linear programming},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {140--145},
     year = {2010},
     volume = {16},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/}
}
TY  - JOUR
AU  - A. A. Kolokolov
AU  - T. G. Orlovskaya
TI  - Investigation of one algorithm for solving problems of integer linear programming
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 140
EP  - 145
VL  - 16
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/
LA  - ru
ID  - TIMM_2010_16_3_a13
ER  - 
%0 Journal Article
%A A. A. Kolokolov
%A T. G. Orlovskaya
%T Investigation of one algorithm for solving problems of integer linear programming
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 140-145
%V 16
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/
%G ru
%F TIMM_2010_16_3_a13
A. A. Kolokolov; T. G. Orlovskaya. Investigation of one algorithm for solving problems of integer linear programming. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 3, pp. 140-145. http://geodesic.mathdoc.fr/item/TIMM_2010_16_3_a13/

[1] Votyakov A. A., “Nekotorye voprosy tselochislennogo programmirovaniya”, Ekonomika i matematicheskie metody, 4:4 (1968), 611–621

[2] Votyakov A. A., “O zadachakh, invariantnykh otnositelno $z$-okrugleniya”, Ekonomika i matematicheskie metody, 7:2 (1971), 259–264

[3] Devyaterikova M. V., Kolokolov A. A., Kolosov A. P., “Unimodulyarnye preobrazovaniya i nekotorye algoritmy tselochislennogo programmirovaniya”, Diskret. optimizatsiya i issled. operatsii, Materialy Ros. konf., In-t matematiki SO RAN, Novosibirsk, 2007, 124

[4] Devyaterikova M. V., Kolokolov A. A., Kolosov A. P., “Ob odnom podkhode k resheniyu diskretnoi zadachi planirovaniya proizvodstva s intervalnymi dannymi”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14, no. 2, 2008, 48–57 | Zbl

[5] Devyaterikova M. V., Kolokolov A. A., Kolosov A. P., Issledovanie nekotorykh algoritmov tselochislennogo programmirovaniya s ispolzovaniem $L$-razbieniya i unimodulyarnykh preobrazovanii, OmGU, Omsk, 2009, 20 pp.

[6] Zaozerskaya L. A., Issledovanie i reshenie nekotorykh klassov zadach tselochislennogo programmirovaniya na osnove regulyarnykh razbienii, Avtoref. dis. kand. fiz.-mat. nauk, Omsk, 1998, 16 pp.

[7] Kolokolov A. A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sib. zhurn. issled. operatsii, 1:2 (1994), 18–39 | MR | Zbl

[8] Kolokolov A. A., Orlovskaya T. G., “Issledovanie $z$-algoritma dlya resheniya nekotorykh zadach tselochislennogo programmirovaniya”, Problemy optimizatsii i ekonomicheskie prilozheniya, Materialy IV vseross. konf., Poligraficheskii tsentr KAN, Omsk, 2009, 137

[9] Kolokolov A. A., Orlovskaya T. G., “O regulyarnosti odnogo algoritma resheniya zadach tselochislennogo programmirovaniya”, Dinamika sistem, mekhanizmov i mashin, Materialy VII mezhdunar. nauch.-tekhn. konf., kn. 3, Izd-vo OmGTU, Omsk, 2009, 51–55

[10] Lotov A. V., Vvedenie v ekonomiko-matematicheskoe modelirovanie, Nauka, M., 1984, 392 pp. | MR | Zbl

[11] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya, v 2 t., v. 1, Mir, M., 1991, 360 pp. | MR

[12] Krishnamoorthy B., Pataki G., “Column basis reduction and decomposable knapsack problems”, Discrete Optimization, 6:3 (2009), 242–270 | MR | Zbl