RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2010 Volume 16, Number 2, Pages 48–62 (Mi timm548)

This article is cited in 2 papers

Unimodular transformations for problems of integer programming and analysis of the efficiency of their application

M. V. Devyaterikovaa, A. A. Kolokolovb, A. P. Kolosovc

a Omsk State Technical University
b Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Science
c Engineering Centre "Automation"

Abstract: The paper is devoted to issues of applying unimodular transformations in integer linear programming with the aim of decreasing the cardinality of $L$-covers of problems and increasing the efficiency of algorithms of their solution. Families of problems are constructed that are difficult for some cutting, branch and bound, and $L$-class enumeration algorithms. Unimodular transformations are suggested that allow one to accelerate the process of solving such problems and to increase the stability of some algorithms under small variations of initial data.

Keywords: integer programming, unimodular transformations, stability of algorithms, Gomory cuts.

UDC: 519.854

Received: 10.09.2009



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024