Comparison Between Exact Optimization and Heuristics Approaches for Maximizing Benefit of Point Redemption: A Knapsack Problem

Abstract

Knapsack problem (KP) is a well-known NP-hard combinatorial optimization problem which seeks to assign several items into a limited capacity knapsack with the objective to maximize the total profit. KP has been used to model many real-life problems. In this study, a point redemption problem based on a membership Clubcard is considered. Customers with certain amount of points sometimes having problem to redeem a selection of coupons to maximize the value of their money. Thus, this problem can be modelled as a knapsack problem and solved by using optimization or heuristics approaches. The objective of this study is to evaluate the solutions produced by greedy techniques compared to optimal solution. This study presents solution comparison between optimal solution and solutions produced by three greedy heuristics which are greedy by profit, greedy by weight and greedy by profit density. Two different total points of customers were considered with fifteen different coupons for selection. Comparison for two total points of customers found that the greedy by profit density is the best greedy method so far for
maximizing the value of money because the total value obtained is the nearest to the optimal solution. This is because this greedy method considers two criteria i.e. coupon values and points in calculating the density which give benefit for identifying suitable coupons to be selected. It can be concluded that this point redemption problem can be modelled as a knapsack problem and
heuristic approaches can be used to find reasonable solution which is comparable to the optimal solution.