K. Krishna Veni and S. Raja Balachandar
A New Heuristic Approach for Large Size ZeroOne Multi Knapsack Problem Using Intercept Matrix
1044 - 1048
2010
4
7
International Journal of Mathematical and Computational Sciences
https://publications.waset.org/pdf/794
https://publications.waset.org/vol/43
World Academy of Science, Engineering and Technology
This paper presents a heuristic to solve large size 01 Multi constrained Knapsack problem (01MKP) which is NPhard. 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 pseudoutility 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 NPhard problems.
Open Science Index 43, 2010