Analysis of the knapsack problem using L-partition. (English. Russian original) Zbl 0749.90053
Cybernetics 27, No. 2, 207-214 (1991); translation from Kibernetika 1991, No. 2, 38-43 (1991).
Summary: A periodicity region of the knapsack problem with a parameter in the right-hand side is analyzed using a partition of a finite-dimensional space. Upper bounds are constructed on the cardinality of \(L\)-covers and on the number of regular cuts required to solve the problem.
MSC:
| 90C10 | Integer programming |
References:
| [1] | A. A. Kolokolov, ?Regular cuts for solving integer optimization problems,? Upr. Sist.,21, 18?25 (1981). |
| [2] | A. A. Kolokolov, ?Cutting plane algorithms and some set partitions,? in: Discrete Optimization and Numerical Methods of Solution of Applied Problems [in Russian], VTs Sib. Otd. Akad. Nauk SSSR, Novosibirsk (1986) pp. 50?67. |
| [3] | A. A. Kolokolov, ?Investigation of integer programming problems and methods using L-partitions,? 33 Intern.-Wiss. Koll. Th., Ilmenau (1988), pp. 53?55. |
| [4] | A. A. Kolokolov, ?On some trends in the bounding partition method,? in: Methods of Mathematical Programming and Software, Proc. 6th Sci. Conf., Sverdlovsk (1989), p. 122. |
| [5] | A. A. Kolokolov and E. V. Tsepkova, ?Upper bound on the number of regular cuts for a family of problems on a cone,? Upr. Sist.,25, 75?79 (1984). · Zbl 0589.90057 |
| [6] | A. A. Kolokolov and E. V. Tsepkova, ?Periodicity of the fractional cover of the knapsack problem,? in: Problems of Theoretical Cybernetics, Abstracts of Papers at 8th All-Union Conf., 4.1 (1988), p. 167. |
| [7] | I. V. Sergienko, Mathematical Models and Methods of Solution of Discrete Optimization Problems [in Russian], Naukova Dumka, Kiev (1988). |
| [8] | T. C. Hu, Integer Programming and Network Flows, Addison-Wesley, Reading, MA (1969). · Zbl 0197.45701 |
| [9] | V. N. Shevchenko, ?On the periodicity property in the knapsack problem,? in: Analysis and Modeling of Economic Processes [in Russian], Izd. Gor’k. Univ., Gor’kii (1981), pp. 36?38. |
| [10] | P. C. Gilmore and R. E. Gomory, ?The theory and computation of knapsack functions,? IBM, 1045?1074 (1966). · Zbl 0173.21502 |
| [11] | H. Greenberg, ?An algorithm for the periodic solution of the knapsack problem,? J. Math. Anal. Appl.,111, 327?331 (1985). · Zbl 0591.90062 · doi:10.1016/0022-247X(85)90219-7 |
| [12] | A. A. Kolokolov, ?Upper bounds on the number of cut planes for the Gomory cyclic algorithm,? in: Methods of Simulation and Data Processing [in Russian], Nauka, Novosibirsk (1976), pp. 106?116. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
