Trudy Instituta Matematiki i Mekhaniki UrO RAN
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Trudy Inst. Mat. i Mekh. UrO RAN: Year: Volume: Issue: Page: Find

 Trudy Inst. Mat. i Mekh. UrO RAN, 2013, Volume 19, Number 2, Pages 193–202 (Mi timm944)

Investigation of integer programming problems by means of unimodular transformations and regular partitions

A. A. Kolokolov, T. G. Orlovskaya

Omsk Branch of Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: Investigations of questions in integer linear programming are carried out concerned with the joint application of unimodular transformations and the method of regular partitions for changing the structure of problems and increasing the efficiency of algorithms. Main results are obtained for the knapsack problem and some of its generalizations based on an $L$-partition. Families of problems with $L$-coverings of exponential cardinality are presented, and unimodular transformations that improve their structure are constructed. New estimates for the number of iterations are described for $L$-class enumeration algorithms.

Keywords: integer programming, unimodular transformation, regular partition, $L$-partition, $L$-class enumeration algorithm.

Full text: PDF file (186 kB)
References: PDF file   HTML file

Bibliographic databases:
UDC: 519.854.3

Citation: A. A. Kolokolov, T. G. Orlovskaya, “Investigation of integer programming problems by means of unimodular transformations and regular partitions”, Trudy Inst. Mat. i Mekh. UrO RAN, 19, no. 2, 2013, 193–202

Citation in format AMSBIB
\Bibitem{KolOrl13} \by A.~A.~Kolokolov, T.~G.~Orlovskaya \paper Investigation of integer programming problems by means of unimodular transformations and regular partitions \serial Trudy Inst. Mat. i Mekh. UrO RAN \yr 2013 \vol 19 \issue 2 \pages 193--202 \mathnet{http://mi.mathnet.ru/timm944} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3364105} \elib{https://elibrary.ru/item.asp?id=19053981}