A New Heuristic Approach for Large Size Zero-One Multi Knapsack Problem Using Intercept Matrix

Authors: K. Krishna Veni, S. Raja Balachandar

Abstract:

This paper presents a heuristic to solve large size 0-1 Multi constrained Knapsack problem (01MKP) which is NP-hard. Many researchers are used heuristic operator to identify the redundant constraints of Linear Programming Problem before applying the regular procedure to solve it. We use the intercept matrix to identify the zero valued variables of 01MKP which is known as redundant variables. In this heuristic, first the dominance property of the intercept matrix of constraints is exploited to reduce the search space to find the optimal or near optimal solutions of 01MKP, second, we improve the solution by using the pseudo-utility ratio based on surrogate constraint of 01MKP. This heuristic is tested for benchmark problems of sizes upto 2500, taken from literature and the results are compared with optimum solutions. Space and computational complexity of solving 01MKP using this approach are also presented. The encouraging results especially for relatively large size test problems indicate that this heuristic can successfully be used for finding good solutions for highly constrained NP-hard problems.

Keywords: 0-1 Multi constrained Knapsack problem, heuristic, computational complexity, NP-Hard problems.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329086

References:

[1] Arnaud Freville., The multidimensional 0-1 knapsack problem: An overview, European Journal of Operational Research, 155, 1-21,2004.
[2] Balas E. An additive algorithm for solving linear programs with zero-one Variables, Operations Research, 13 : 517-546,1965.
[3] E.Balas,C.H.martin: pivot and Complement - a Heuristic for 0-1 programming, Management Science 26(1),1980.
[4] J.E.Beasley: OR-Library; Distributing Test Problems by Electronic Mail, Journal of Operational Research Society 41, pp.1069-1072, 1990.
[5] Brearley,A.L., G.Mitra and H.P Williams, Analysis of mathematical programming problem prior to applying the simplex algorithm , Math. Prog., 8: 54-83. 1975.
[6] Cabot A.V.An enumeration algorithm for knapsack problems, Operations Reserch ,18:306-311,1970.
[7] P.C.Chu: A Genetic Algorithm Approach for Combinatorial Optimization Problems,Ph.D.thesis at Management School,Imperial College of Science , London, 1997.
[8] P.C.Chu and J.E.Beasley.A genetic algorithm for the multidimensional knapsack problem, Journal of Heurisic,4:63-86,1998.
[9] A.Drexl. A simulated annealing approach to the multiconstraint zero-one knapsack problem,Computing,40:1-8,1988.
[10] M.R.Garey and D.S.Johnson,Computers and Intractability: A Guide to the theory of NP-completeness,W.H.Freeman and company, San Francisco. 1979.
[11] Gavish B. and pirkul H.Efficient algorithms for solving multiconstraint zero- one problems to optimality, Mathematical programming,31:78- 105,1985.
[12] Gilmore P.C and Gomory R.E ,The theory and computations of Knapsack Functions, Operations Research,14:1045-1075,1966.
[13] F.Glover and G.A.Kochenberger.Critical event tabu search for multidimensional knapsack problems.Metaheuristics: The Theory and Applications, pages 407-427.KluwerAcademic Publishers,1996.
[14] Glover. F, A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem, Operations Research 13,879-919. 1965.
[15] Glover. F, Heuristics for Integer Programming Using Surrogate Constraints, Decision Sciences 8, 156-166,1977
[16] Gowdzio, J.,Presolve analysis of linear program prior to applying an interior point method,Inform. J.Comput., 9: 73-91. 1997
[17] S.Hanafi and A.Freville.An efficient tabu search approach for the 0- 1 multidimensional knapsack problem, European Journal of Operational Research,106:659-675,1998.
[18] Ioslovich, I., Robust reduction of a class of large scale linear program, Siam J.Optimization, 12: 262-282,2002.
[19] Karwan,M.H., V. Loffi, J. Telgan and S. Zionts, Redundancy in mathematical Programming, A State of the Art Servey (Berlin: Springer-Verlag). 1983,
[20] S. Khuri, T. Baeck, J. Heitkoetter, The Zero/One Multiple Knapsack Problem and Genetic Algorithms, Proceedings of the 1994 ACM Symposium on Applied Computing, SAC-94, Phoenix, Arizona. pp188-193, ACM press,1994
[21] Kuhn, H.W. and R.E . Quant, An Experimental Study of the Simplex Method, In: Metropolis, N. et al.(Eds.). Preceedings of Symposia in Applied Mathematics. Providence, RI: Am. Math. Soc., 15: 107-124. 1962.
[22] M.J.Magazine,O.Oguz , A Heuristic Algorithm for the Multidimensional zero-one knapsack problem,European Journal of Operational Research 16.pp.319-326,1984.
[23] S.Martello and P.Toth. Knapsack problems: Algorithms and Computer Implementations, John Wiley and Sons, chichester, West Sussex, England, 1990.
[24] Matthesiss,T.H., , An Algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities, Operat. Res., 21: 247- 260. 1973
[25] Meszaros. C. and U.H. Suhl, Advanced preprocessing techniques for linear and quadratic programming, Spectrum, 25: 575-595. 2003.
[26] Osrio M.A.Glover F.and HammerP. Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Technical Report HCES-08-00,Hearing Center for Enterprise Science,2000.
[27] Paulraj, S., C. Chellappan and T.R. Natesan, A heuristic approach for identification of redundant constraints in linear programming models, Int. J. Com. Math., 83(8): 675-683. 2006,
[28] H.Pirkul: A Heuristic Solution procedure for the Multiconstrained zeroone Knapsack problem,Naval Research Logistics 34,pp.161-172,1987.
[29] Sartaj Sahni, Approximate Algorithms for the 01 knapsack problem, ACM Vol 29,no 1 , pp 113-124,1975
[30] Shih W. A. branch and bound method for the multiconstraint zeroone knapsack problem, Journal of Operational Research Society,30: 369- 378,1979.
[31] Srojkovic, N.V. and P.S. Stanimirovic, Two direct methods in linear Programming, European J. Oper. Res., 131: 417-439. 2001.
[32] Telgan, J.,Identifying redundant constraints and implicit equalities in system oflinear constraints, Manage. Sci., 29: 1209-1222,1983.
[33] Tomlin, J.A. and J.S Wetch, Finding duplicate rows in a linear programming Model, Oper. Res. Let., 5: 7-11. 1986.
[34] A.Volgenant,J.A.Zoon : An Improved Heuristic for Multidimensional 0-1 Knapsack Problems, Journal of the Operational Research Society 41,pp.963-970,1990.
[35] Weingartner H.M and Ness D.N,Methods for the solution of the multidimensional 0/1 knapsack problem, Operations Research,15:83-103,1967.