This article is cited in 3 papers

The analysis of the stability of some integer programming algorithms with respect to the objective function

M. V. Devyaterikova^a, A. A. Kolokolov^bc, N. A. Kosarev<sup>c

a</sup> Chair of Applied Mathematics and Information Systems, Omsk State Technical University, Omsk, Russia
^b Chair of Applied and Calculus Mathematics, Omsk State University, Omsk, Russia
^c Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of Russian Academy of Sciences, Omsk, Russia

Abstract: 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.

UDC: 519.854

Received: 20.10.2009

 English version: Russian Mathematics (Izvestiya VUZ. Matematika), 2011, 55:4, 18–25

Bibliographic databases:

• 
•