Investigation of integer programming problems by means of unimodular transformations and regular partitions

A. A. Kolokolov ; T. G. Orlovskaya

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 193-202

Résumé

Investigations of questions in integer linear programming are carried out concerned with the joint application of unimodular transformations and the method of regular partitions for changing the structure of problems and increasing the efficiency of algorithms. Main results are obtained for the knapsack problem and some of its generalizations based on an $L$-partition. Families of problems with $L$-coverings of exponential cardinality are presented, and unimodular transformations that improve their structure are constructed. New estimates for the number of iterations are described for $L$-class enumeration algorithms.

Détail

Keywords: integer programming, unimodular transformation, regular partition, $L$-class enumeration algorithm.
Mots-clés : $L$-partition

Bibliographie

[1] Beresnev V. L., Gimadi E. Kh., Dementev V. T., Ekstremalnye zadachi standartizatsii, Nauka, Novosibirsk, 1978, 333 pp. | MR

[2] Bulatov V.P., Metody pogruzheniya v zadachakh optimizatsii, Nauka, Novosibirsk, 1977, 161 pp. | MR

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

[4] Devyaterikova M. V., Kolokolov A. A., Kolosov A. P., “Unimodulyarnye preobrazovaniya dlya zadach tselochislennogo programmirovaniya i analiz effektivnosti ikh primeneniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 2, 2010, 48–62

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

[6] Zablotskaya O. A., Dvoistvennye protsessy otsecheniya i $L$-struktura nekotorykh zadach tselochislennogo programmirovaniya, Avtoref. dis. kand. fiz.-mat. nauk, Novosibirsk, 1985

[7] Zaozerskaya L. A., Kolokolov A. A., “Otsenki srednego chisla iteratsii dlya nekotorykh algoritmov resheniya zadachi ob upakovke mnozhestva”, Zhurn. vychislit. matematiki i mat. fiziki, 50:2 (2010), 242–248 | MR | Zbl

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

[9] Kolokolov A. A., Adelshin A. V., Yagofarova D. I., “Reshenie zadachi vypolnimosti s ispolzovaniem metoda perebora $L$-klassov”, Informatsionnye tekhnologii, 2009, no. 2, 54–59

[10] Kolokolov A. A., Orlovskaya T. G., “Issledovanie odnogo algoritma resheniya zadach tselochislennogo lineinogo programmirovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 3, 2010, 140–145

[11] Kolokolov A. A., Orlovskaya T. G., “O nekotorykh unimodulyarnykh preobrazovaniyakh dlya zadachi o ryukzake”, Metody optimizatsii i ikh prilozheniya, Tr. XV Baikalskoi Mezhdunar. shk.-seminara, v. 4, Irkutsk, 2011, 161–166

[12] Kolokolov A. A., Orlovskaya T. G., “Analiz algoritmov resheniya nekotorykh zadach o ryukzake na osnove $L$-razbieniya”, Tez. Mezhdunar. konf. “Algebra i lineinaya optimizatsiya”, posvyasch. 100-letiyu S. N. Chernikova, Ekaterinburg, 2012, 94–95

[13] Kolokolov A. A., Orlovskaya T. G., “Issledovanie nekotorykh postanovok zadachi o ryukzake i algoritmov ikh resheniya s ispolzovaniem unimodulyarnykh preobrazovanii i $L$-razbieniya”, Intellektualizatsiya obrabotki informatsii, Cb. dokl. 9-i mezhdunarodnaya konf., Torus Press, M., 2012, 286–289

[14] Kolokolov A. A., Orlovskaya T. G., Rybalka M. F., “Issledovanie algoritmov tselochislennogo programmirovaniya s ispolzovaniem regulyarnykh razbienii i unimodulyarnykh preobrazovanii”, Avtomatika i telemekhanika, 2012, no. 2, 178–190

[15] Eremin I. I., Mazurov Vl. D., Skarin V. D., Khachai M. Yu., Matematicheskie metody v ekonomike, Izd-vo “U-Faktoriya”, Ekaterinburg, 2000, 279 pp. | MR

[16] Leontev V. K., “Ustoichivost v lineinykh diskretnykh zadachakh”, Probl. kibernetiki, 35, Nauka, M., 1979, 169–184 | MR

[17] Orlovskaya T. G., “Uluchshenie struktury semeistv zadach o ryukzake s ispolzovaniem unimodulyarnykh preobrazovanii”, Tez. Mezhdunar. konf. “Algebra i lineinaya optimizatsiya”, posvyasch. 100-letiyu S. N. Chernikova, Ekaterinburg, 2012, 122–124

[18] Popkov V. K., Matematicheskie modeli svyaznosti, 2-e izd., ispr. i dop., Izd.-vo IVMiMG SO RAN, Novosibirsk, 2006, 490 pp.

[19] Sergienko I. V., Matematicheskie modeli i metody resheniya zadach diskretnoi optimizatsii, AN USSR, In-t kibernetiki im. V. M. Glushkova, 2-e izd., dop. i pererab., Nauk. dumka, Kiev, 1988, 471 pp. | MR

[20] Khachai M. Yu., “Vychislitelnaya slozhnost kombinatornykh zadach, indutsirovannykh kollektivnymi protsedurami obucheniya raspoznavaniyu obrazov”, Tr. In-ta matematiki i mekhaniki UrO RAN, 16, no. 3, 2010, 276–284

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

[22] Eremeev A. V., Kolokolov A. A., “On some genetic and $L$-class enumeration algorithms in integer programming”, Proc. of the I Intern. Conf. on Evolutionary Computation and its Applicatios, Moscow, 1996, 297–303

[23] Jeroslow R. G., “Trivial integer programs unsolvable by branch-and-bound”, Math. Programming, 6:1 (1974), 105–109 | DOI | MR | Zbl

[24] Kolokolov A. A., Orlovskaya T. G., Rybalka M. F., “Analysis of some integer programming algorithms based on the method of regular partitions”, Proc. of II Intern. Conf. “Optimization and Applications” (OPTIMA-2011), 2011, 133–136

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

[26] Land A. H., Doig A. G., “An automatic Method for Solving Discrete Programming Problems”, Econometrica, 28:3 (1960), 497–520 | DOI | MR | Zbl

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

[28] Nemhauser G. L., Wolsey L. A., Integer and combinatorial optimization, A Wiley-Interscience Publication, John Wiley and Sons, Inc., New York, 1999, 763 pp. | MR