A new fast reduction algorithm for binary knapsack problem
The first reduction algorithm for binary knapsack problems was developed by Ingargiola and Korsh (1973) It is a preprocessing algorithm which significantly reduces the number of variables by fixing the optimal value of as many variables as possible. However, the speed of the algorithm is pretty slow, because it only fixes one variable at one time. This paper presents a new reduction algorithm for binary knapsack problem which can fix several variables at one time. When combined with available algorithms for binary knapsack problems, it can substantially reduce the total running time and the space requirements.
2016 IEEE 13th International Conference on Networking, Sensing, and Control (ICNSC)