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/