A New Heuristic Approach for Large Size Zero-One Multi Knapsack Problem Using Intercept Matrix
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:49937", author = "K. Krishna Veni and S. Raja Balachandar", title = "A New Heuristic Approach for Large Size Zero-One Multi Knapsack Problem Using Intercept Matrix", 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.", volume = "4", number = "7", pages = "783-5", }
