Finding and analysis of estimation of the number of iterations in integer programming algorithms using the regular partitioning method

A. A. Kolokolov ; L. A. Zaozerskaya

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 1 (2014), pp. 41-54.

Résumé

We review the results of studying integer linear programming algorithms which exploit properties of problem relaxation sets. The main attention is paid to the estimation of the number of iterations of these algorithms by means of the regular partitions method and other approaches. We present such estimates for some cutting plane, branch and bound (Land and Doig scheme), and $L$-class enumeration algorithms and consider questions of their stability. We establish the upper bounds for the average number of iterations of the mentioned algorithms as applied to the knapsack problem and the set packing one.

Détail

Keywords: discrete optimization, integer programming, regular partitions method, estimates of the number of iterations, cuts, $L$-class enumeration, branch and bound method, estimates on average, stability of algorithms.

Bibliographie

[1] Sergienko I. V., Matematicheskie modeli i metody resheniya zadach diskretnoi optimizatsii, Nauk. dumka, Kiev, 1988 | MR

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

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

[4] Nemhauser G. L., Wolsey L. A., Integer and combinatorial optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley Sons, inc., 1999 | MR

[5] Kolokolov A. A., “Primenenie regulyarnykh razbienii v tselochislennom programmirovanii”, Izv. vuzov. Matem., 1993, no. 12, 11–30 | MR | Zbl

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

[7] Kolokolov A. A., “O chisle otsekayuschikh ploskostei v pervom algoritme Gomori”, Probl. analiza diskretnoi informatsii, Cb., ch. 1, Novosibirsk, 1975, 84–96

[8] Kolokolov A. A., “O leksikograficheskoi strukture nekotorykh vypuklykh mnogogrannykh mnozhestv”, Tez. dokl. 5-i Vsesoyuzn. konf. po problemam teor. kibernetiki, Novosibirsk, 1980, 77–79

[9] Kolokolov A. A., “Regulyarnye otsecheniya pri reshenii zadach tselochislennoi optimizatsii”, Upravlyaemye sistemy, 21, 1981, 18–25 | MR | Zbl

[10] Devyaterikova M. V., Kolokolov A. A., Kolosov A. P., Issledovanie nekotorykh algoritmov tselochislennogo programmirovaniya s ispolzovaniem $L$-razbienii i unimodulyarnykh preobrazovanii, Preprint, OmGU, Omsk, 2009

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

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

[13] Kolokolov A. A., Devyaterikova M. V., Zaozerskaya L. A., Regulyarnye razbieniya v tselochislennom programmirovanii, Ucheb. posobie, OmGU, Omsk, 2007

[14] Kolokolov A. A., Tsepkova E. V., “Issledovanie zadachi o ryukzake na osnove $L$-razbieniya”, Kibernetika, 1991, no. 2, 38–43 | MR | Zbl

[15] Kolokolov A. A., “On the $L$-structure of integer linear programming problems”, Lect. Notes in Control and Inform. Sci. Syst. Modelling and Optimization, 197, 1994, 756–761 | MR

[16] Kolokolov A. A., “O dline leksikograficheski monotonnykh posledovatelnostei”, Optimizatsiya territorialnykh i otraslevykh sistem, metody resheniya ekonomicheskikh zadach, Cb., ch. III, Novosibirsk, 1973, 93–99

[17] Nourie F. J., Venta E. R., “An upper bound on the number of cuts needed in Gomory's method of integer forms”, Oper. Res. Letters, 1:4 (1981/82), 129–133 | MR

[18] Zablotskaya O. A., Kolokolov A. A., “Vpolne regulyarnye otsecheniya v bulevom programmirovanii”, Upravlyaemye sistemy, 23, 1983, 55–63 | MR | Zbl

[19] Simanchev R. Yu., “O vpolne regulyarnykh otsecheniyakh v zadachakh tselochislennoi optimizatsii”, Upravlyaemye sistemy, 30, 1990, 61–71 | MR | Zbl

[20] Korbut A. A., Finkelshtein Yu. Yu., Diskretnoe programmirovanie, Nauka, M., 1969 | MR | Zbl

[21] Saiko L. A., “Issledovanie odnogo klassa razbienii v tselochislennom programmirovanii”, Upravlyaemye sistemy, 29, 1989, 72–82 | MR

[22] Finkelshtein Yu. Yu., Priblizhennye metody i prikladnye zadachi diskretnogo programmirovaniya, Nauka, M., 1976

[23] Kolpakov R. M., Posypkin M. A., “Asimptoticheskaya otsenka slozhnosti metoda vetvei i granits s vetvleniem po drobnoi peremennoi dlya zadachi o rantse”, Diskretn. analiz i issledov. operatsii, 15:1 (2008), 58–81 | MR | Zbl

[24] Eremeev A. V., Zaozerskaya L. A., Kolokolov A. A., “Zadacha o pokrytii mnozhestva: slozhnost, algoritmy, eksperimentalnye issledovaniya”, Diskretn. analiz i issledovanie operatsii. Ser. 2, 7:2 (2000), 22–46 | MR | Zbl

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

[26] Kolokolov A. A., Orlovskaya T. G., Rybalka M. F., “Analiz algoritmov tselochislennogo programmirovaniya s ispolzovaniem $L$-razbieniya i unimodulyarnykh preobrazovanii”, Avtomatika i telemekhanika, 2012, no. 2, 178–190

[27] Jeroslow R., Kortanek K., “On an algorithm of Gomory”, SIAM J. Appl. Math., 21:1 (1971), 55–60 | MR | Zbl

[28] Kolokolov A., Kosarev N., “Analysis of decomposition algorithms with Benders cuts for $p$-median problem”, J. Math. Modelling and Algorithms, 5:2 (2006), 189–199 | DOI | MR | Zbl

[29] Zaozerskaya L. A., “Analysis of fractional covering of some supply management problems”, J. Math. Modelling and Algorithms, 5:2 (2006), 201–213 | DOI | MR | Zbl

[30] Saiko L. A., “O chisle iteratsii pryamykh algoritmov otsecheniya”, Diskretnaya optimizatsiya i chislennye metody resheniya prikladnykh zadach, Cb., VTs SO AN SSSR, Novosibirsk, 1986, 86–98 | MR

[31] Kolokolov A. A., “K otsenke chisla iteratsii dlya pryamykh algoritmov otsecheniya v tselochislennom lineinom programmirovanii”, Matem. analiz ekonom. modelei, Cb., ch. I, IEiOPP SO AN SSSR, Novosibirsk, 1971, 137–164

[32] Mathis S. I. (Jr.), “A counterexample to the rudimentary primal integer programming algorithm”, Oper. Res., 19:6 (1971), 1518–1522 | DOI | Zbl

[33] Devyaterikova M. V., Kolokolov A. A., “Ob ustoichivosti nekotorykh algoritmov tselochislennogo programmirovaniya”, Izv. vuzov. Matem., 2003, no. 12, 41–48 | MR | Zbl

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

[35] Devyaterikova M. V., Kolokolov A. A., “On the stability of some integer programming algorithms”, Oper. Res Letters, 34:2 (2006), 149–154 | DOI | MR

[36] Sergienko I. V., Kozeratskaya L. N., Lebedeva T. T., Issledovanie ustoichivosti i parametricheskii analiz diskretnykh optimizatsionnykh zadach, Nauk. dumka, Kiev, 1995

[37] Gordeev E. N., Leontev V. K., “Obschii podkhod k issledovaniyu ustoichivosti reshenii v zadachakh diskretnoi optimizatsii”, Zhurn. vychisl. matem. i matem. fiz., 36:1 (1996), 66–72 | MR | Zbl

[38] Emelichev V. A., Podkopaev D. P., “O kolichestvennoi mere ustoichivosti vektornoi zadachi tselochislennogo programmirovaniya”, Zhurn. vychisl. matem. i matem. fiz., 38:11 (1998), 1801–1805 | MR | Zbl

[39] Zaozerskaya L. A., Kolokolov A. A., “O srednem chisle iteratsii nekotorykh algoritmov dlya resheniya zadachi ob upakovke mnozhestva”, Matematicheskoe programmirovanie, Tr. XIV Baikalskoi mezhdunarodn. shk.-semin. “Metody optimizatsii i ikh prilozheniya” (Irkutsk, Baikal, 2–8 iyulya 2008), v. 1, ISEM SO RAN, Irkutsk, 2008, 388–395

[40] Zaozerskaya L. A., Kolokolov A. A., “O srednem chisle iteratsii dlya nekotorykh algoritmov resheniya zadachi ob upakovke mnozhestva”, Zhurn. vychisl. matem. i matem. fiz., 50:2 (2010), 242–248 | MR | Zbl

[41] Zaozerskaya L. A., Kolokolov A. A., Gofman N. G., “Otsenki srednego chisla iteratsii dlya algoritmov resheniya nekotorykh zadach buleva programmirovaniya”, Diskretn. analiz i issledov. operatsii, 18:3 (2011), 49–64 | MR | Zbl

[42] Kolokolov A. A., Zaozerskaya L. A., “On average number of iterations of some algorithms for solving the set packing”, Preprints of 13th IFAC Symposium on Inform. Control Probl. in Manufacturing, INCOM' 09 (June 3–5, 2009, Moscow, Russia), v. I, 1493–1496

[43] Kuzyurin N. N., “Polinomialnyi v srednem algoritm v tselochislennom lineinom programmirovanii”, Sib. zhurn. issledov. operatsii, 1:3 (1994), 38–48 | MR | Zbl

[44] Kuzyurin N. N., Fomin S. A., Effektivnye algoritmy i slozhnost vychislenii, http://discopal.ispras.ru/ru.book-advanced-algorithms.htm

[45] Zaozerskaya L. A., Kolokolov A. A., “Otsenki srednego chisla iteratsii dlya nekotorykh algoritmov resheniya zadachi o ryukzake”, Diskretnye modeli v upravlyayuschikh sistem, Tr. VIII Mezhdunarodn. konf. (Moskva, 6–9 aprelya 2009), MAKS PRESS, Moskva, 2009, 101–106

[46] Kolokolov A. A., Zaozerskaya L. A., “On the approach of obtaining the upper bounds on the average number of iterations of some integer programming algorithms”, Optimization and applications, Proc. of II Intern. Conf. (Petrovac, Montenegro, September 25 – October 2, 2011), ed. A. I. Golikov, VTs im. A. A. Dorodnitsyna RAN, Moskva, 2011, 137–140