Geodesic
The analysis of the stability of some integer programming algorithms with respect to the objective function
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2011), pp. 23-32.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we define the notion of the stability with respect to the objective function for a wide class of integer linear programming algorithms. We study the stability of some of them under small variations of coefficients in the objective function. We prove the existence of both stable and unstable versions of the $L$-class enumeration algorithms. We show that some branch and bound algorithms, as well as some decomposition algorithms with Benders cuts, are unstable. We propose a modification of the considered decomposition algorithms that makes the latter stable with respect to the objective function.
Keywords: discrete optimization, integer programming, stability of algorithms, $L$-class enumeration, branch and bound method, Benders decomposition. 
@article{IVM_2011_4_a3,
     author = {M. V. Devyaterikova and A. A. Kolokolov and N. A. Kosarev},
     title = {The analysis of the stability of some integer programming algorithms with respect to the objective function},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {23--32},
     publisher = {mathdoc},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2011_4_a3/}
}
TY  - JOUR
AU  - M. V. Devyaterikova
AU  - A. A. Kolokolov
AU  - N. A. Kosarev
TI  - The analysis of the stability of some integer programming algorithms with respect to the objective function
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2011
SP  - 23
EP  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2011_4_a3/
LA  - ru
ID  - IVM_2011_4_a3
ER  - 
%0 Journal Article
%A M. V. Devyaterikova
%A A. A. Kolokolov
%A N. A. Kosarev
%T The analysis of the stability of some integer programming algorithms with respect to the objective function
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2011
%P 23-32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2011_4_a3/
%G ru
%F IVM_2011_4_a3
M. V. Devyaterikova; A. A. Kolokolov; N. A. Kosarev. The analysis of the stability of some integer programming algorithms with respect to the objective function. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 4 (2011), pp. 23-32. http://geodesic.mathdoc.fr/item/IVM_2011_4_a3/

[1] 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

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

[3] 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

[4] Kolokolov A. A., Devyaterikova M. V., “Analiz ustoichivosti $L$-razbieniya mnozhestv v konechnomernom prostranstve”, Diskretn. analiz i issled. operatsii. Ser. 2, 7:2 (2000), 47–53 | MR | Zbl

[5] Kolokolov A. A., Kosarev N. A., “Ob ustoichivosti dekompozitsionnykh algoritmov s otsecheniyami Bendersa dlya nekotorykh zadach razmescheniya”, Tr. XIV mezhdunarodn. shk.-sem. “Metody optimizatsii i ikh prilozheniya”, v. 1, Severobaikalsk, 2008, 428–434

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

[7] Kolokolov A. A., Devyaterikova M. V., “Stability analysis of some discrete optimization algorithms”, Proc. of the Second International Workshop “Discrete optimization methods in productions and logistics”, Nasledie Dialog – Sibir Pbs., Omsk, 2004, 180–184

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

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

[10] Benders J. F., “Partitioning procedures for solving mixed-variables programming problems”, Numerische Math., 4:3 (1963), 238–252 | MR

[11] Kolokolov A. A., Kosarev N. A., Rubanova N. A., “Issledovanie otsechenii Bendersa v dekompozitsionnykh algoritmakh resheniya nekotorykh zadach razmescheniya”, Omsk. nauchn. vestn., 2005, no. 2, 76–80