Geodesic
Unimodular transformations for problems of integer programming and analysis of the efficiency of their application
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 2, pp. 48-62
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper is devoted to issues of applying unimodular transformations in integer linear programming with the aim of decreasing the cardinality of $L$-covers of problems and increasing the efficiency of algorithms of their solution. Families of problems are constructed that are difficult for some cutting, branch and bound, and $L$-class enumeration algorithms. Unimodular transformations are suggested that allow one to accelerate the process of solving such problems and to increase the stability of some algorithms under small variations of initial data.
Keywords: integer programming, unimodular transformations, stability of algorithms, Gomory cuts. 
@article{TIMM_2010_16_2_a3,
     author = {M. V. Devyaterikova and A. A. Kolokolov and A. P. Kolosov},
     title = {Unimodular transformations for problems of integer programming and analysis of the efficiency of their application},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {48--62},
     year = {2010},
     volume = {16},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a3/}
}
TY  - JOUR
AU  - M. V. Devyaterikova
AU  - A. A. Kolokolov
AU  - A. P. Kolosov
TI  - Unimodular transformations for problems of integer programming and analysis of the efficiency of their application
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2010
SP  - 48
EP  - 62
VL  - 16
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a3/
LA  - ru
ID  - TIMM_2010_16_2_a3
ER  - 
%0 Journal Article
%A M. V. Devyaterikova
%A A. A. Kolokolov
%A A. P. Kolosov
%T Unimodular transformations for problems of integer programming and analysis of the efficiency of their application
%J Trudy Instituta matematiki i mehaniki
%D 2010
%P 48-62
%V 16
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a3/
%G ru
%F TIMM_2010_16_2_a3
M. V. Devyaterikova; A. A. Kolokolov; A. P. Kolosov. Unimodular transformations for problems of integer programming and analysis of the efficiency of their application. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 16 (2010) no. 2, pp. 48-62. http://geodesic.mathdoc.fr/item/TIMM_2010_16_2_a3/

[1] Votyakov A. A., “Algoritm resheniya obobschennoi tselochislennoi zadachi lineinogo programmirovaniya”, Matematicheskie metody v nekotorykh zadachakh optimalnogo planirovaniya, Sb., Matematicheskii in-t im. V. A. Steklova, Sverdlovskoe otdelenie, Sverdlovsk, 1967, 73–82

[2] Devyaterikova M. V., Kolokolov A. A., “Analiz ustoichivosti nekotorykh algoritmov diskretnoi optimizatsii”, Avtomatika i telemekhanika, 2004, no. 3, 48–54 | MR | Zbl

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

[4] Devyaterikova M. V., Kolokolov A. A., Kolosov A. P., Issledovanie nekotorykh algoritmov tselochislennogo programmirovaniya s ispolzovaniem $L$-razbieniya i unimodulyarnykh preobrazovanii, preprint, Omskii gos. un-t, Omsk, 2009, 20 pp.

[5] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981, 344 pp. | MR | Zbl

[6] Kolokolov A. A., Metody diskretnoi optimizatsii, Uch. posobie, Omskii gos. un-t, Omsk, 1984, 76 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., Devyaterikova M. V., “Zadachi tselochislennogo programmirovaniya i unimodulyarnye preobrazovaniya”, Matematicheskoe programmirovanie, Tr. XIV Baikal. mezhdunar. shk.-seminara “Metody optimizatsii i ikh prilozheniya”, v. 1, ISEM SO RAN, Irkutsk, 2008, 111–118

[9] Kolokolov A. A., Kosarev N. A., “Ob ustoichivosti dekompozitsionnykh algoritmov s otsecheniyami Bendersa dlya nekotorykh zadach razmescheniya”, Matematicheskoe programmirovanie, Tr. XIV Baikal. mezhdunar. shk.-seminara “Metody optimizatsii i ikh prilozheniya”, v. 1, ISEM SO RAN, Irkutsk, 2008, 428–434

[10] Eisenbrand F., Schulz A. S., “Bounds on the Chvatal rank of polytopes in the 0/1-cube”, Combinatorica, 23:2 (2003), 245–261 | DOI | MR | Zbl

[11] Lenstra H. W. (Jr.), “Integer programming with a fixed number of variables”, Math. Oper. Res., 8:4 (1983), 538–548 | DOI | MR | Zbl

[12] van Maaren H., Dang C., “Simplicial pivoting algorithms for tractable class of integer programs”, J. Comb. Optim., 6:2 (2002), 133–142 | DOI | MR | Zbl

[13] Nemhauser G. L., Wolsey L. A., Integer and combinatorial optimization, John Wiley Sons, New York, 1999, 766 pp. | MR