TY - JFULL
AU - K. Krishna Veni and S. Raja Balachandar
PY - 2010/8/
TI - A New Heuristic Approach for Large Size Zero-One Multi Knapsack Problem Using Intercept Matrix
T2 - International Journal of Mathematical and Computational Sciences
SP - 1043
EP - 1048
VL - 4
SN - 1307-6892
UR - https://publications.waset.org/pdf/794
PU - World Academy of Science, Engineering and Technology
NX - Open Science Index 43, 2010
N2 - 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.
ER -