Convex Matrices and Multidimensional Knapsack Problem of Generalized Ladder Structure

The article deals with solving multidimensional knapsack problems with the so-called convex constraint matrices - consisting of zeros and ones in which in each row (or each column) the ones are consecutive, with no gaps. It is proved that convex matrices are absolutely unimodular. This allows for the usual simplex method to be applied to solve such problems. For multidimensional knapsack problems with convex constraint matrices of the generalized ladder structure we proposed the decomposition solution method, which makes it possible to significantly increase the solved problems dimension. Decomposition is exposed on the constraints and the objective function. In the general case, the iteration loop consists of solving various knapsack problems with two constraints with at least one common variable. After solving the knapsack problem with two constraints, it is equivalently replaced by a combination of the two knapsack problems with one constraint each. It is done by modifying the coefficients of the objective function for the common variables. The method has an additional advantage - it does not accumulate computation errors, since in each cycle the objective function coefficients restore their values. Numerical example is given to illustrate the proposed method.

References

[1] Taha Hamdy A. Operations research: An Introduction. Prentice Hall, Inc., 1997.

[2] Kagirov R.R. Multiple Knapsack problem: new solving methods. Vestnik SibGAU [Vestnik of the Reshetnev Siberian State Aerospace University], 2007, iss. 3, pp. 16-20 (in Russ.).

[3] Fedorin A.N. Mnogokriterial’nye zadachi rantsevogo tipa: razrabotka i sravnitel’nyy analiz algoritmov. Avtoreferat diss. kand. tekh. nauk [Multicriteria problems of knapsack type: Development and comparative analysis of algorithms. Cand. tech. sci. diss. abstr.]. Nizhniy Novgorod, 2010.

[4] Dumbadze L.G. Razrabotka metodov i algoritmov v zadachakh optimal’nogo ispol’zovaniya i razvitiya setey. Avtoreferat diss. kand. fiz.-mat. nauk [Development of methods and algorithms in the problems of network optimal use and development. Cand. phys.-math. sci. diss. abstr.]. Moscow, 2007.

[5] Batishchev D.I., Kogan D.I., Leykin M.V. Decisions synthesis algorithms for multicriteria many-dimensional Knapsack problem. Informatsionnye tekhnologii [Information Technologies], 2004, no. 1.

[6] Mamedov K.Sh., Mamedov N.N. Algorithms for constructing multidimensional Knapsack problem guaranteed solutions and guaranteed approximate solution. Problemy upravleniya i informatiki [Journal of Automation and Information Sciences], 2014, no. 5, pp. 30-37 (in Russ.).

[7] Korbut A.A., Sigal I.Kh. Exact and greedy solutions of the Knapsack problem: The ratio of values of objective functions. Journal of Computer and Systems Sciences International, 2010, vol. 49, no. 5, pp. 757-764. DOI: 10.1134/S1064230710050102

[8] Galim’yanova N.N., Korbut A.A., Sigal I.Kh. Ratios of optimal values of objective functions of the Knapsack problem and its linear relaxation. Journal of Computer and Systems Sciences International, 2009, vol. 48, no. 6, pp. 906-913. DOI: 10.1134/S1064230709060070

[9] Dyubin G.N., Korbut A.A. Average behavior of greedy algorithms for the minimization Knapsack problem: General coefficient distributions. Comput. Math. and Math. Phys., 2008, vol. 48, no. 9, pp. 1521-1535. DOI: 10.1134/S0965542508090042

[10] Dyubin G.N., Korbut A.A. Greedy algorithms for the minimization Knapsack problem: Average behavior. Journal of Computer and Systems Sciences International, 2008, vol. 47, no. 1, pp. 14-24. DOI: 10.1007/s11488-008-1003-1

[11] Davis T.A., Hager W.W., Hungerford J.T. An efficient hybrid algorithm for the separable convex quadratic Knapsack problem. ACM Transactions on Mathematical Software (TOMS), 2016, vol. 42, no. 3.

[12] Caprara A., Furini F., Malaguti E., Traversi E. Solving the temporal Knapsack problem via recursive Dantzig - Wolfe reformulation. Information Processing Letters, 2016, vol. 116, no. 5, pp. 379-386.

[13] Cunha J.O., Simonetti L., Lucena A. Lagrangian heuristics for the quadratic Knapsack problem. Computational Optimization and Applications, 2016, vol. 63, no. 1, pp. 97-120.

[14] Peng B., Liu M., Lu Z., Kochengber G., Wang H. An ejection chain approach for the quadratic multiple Knapsack problem. European Journal of Operational Research, 2016, vol. 253, no. 2, pp. 328-336.

[15] Qin J., Xu X., Wu Q., Cheng T.C.E. Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple Knapsack problem. Computers & Operations Research, 2016, vol. 66, pp. 199-214.

[16] Taylor R. Approximation of the quadratic Knapsack problem. Operations Research Letters, 2016, vol. 44, no. 4, pp. 495-497.

[17] Haddar B., Khemakhem M., Hanafi S., Wilbaut C. A hybrid quantum particle swarm optimization for the multidimensional Knapsack problem. Engineering Applications of Artificial Intelligence, 2016, vol. 55, pp. 1-13.

[18] Dumbadze L.G., Tizik A.P. Many-dimensional Knapsack problem of a special ladder structure. Journal of Computer and Systems Sciences International, 1996, vol. 35, no. 4, pp. 614-617.

[19] Esenkov A.S., Leonov V.Yu., Tizik A.P., Tsurkov V.I. Nonlinear integer transportation problem with additional supply and consumption points. Journal of Computer and Systems Sciences International, 2015, vol. 54, no. 1, pp. 86-92. DOI: 10.1134/S1064230715010050

[20] Kuzovlev D.I., Tizik A.P., Treskov Yu.P. Decompositional algorithm for solving transportation problem with fixed channel capasities. Mekhatronika, avtomatizatsiya, upravlenie [Mechatronics, automation, control], 2012, no. 1, pp. 45-48 (in Russ.).

[21] Tizik A.P., Kuzovlev D.I., Sokolov A.A. Method of successive modifications of functional for transportation problem with additional warehouse points for suppliers and consumers. Vestnik TvGU. Ser. prikladnaya matematika [Herald of Tver State University. Series: Applied Mathematics], 2012, no. 4, pp. 91-98 (in Russ.).