Cover Image

Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem

Link to publisher's homepage at https://amci.unimap.edu.my/

Saved in:
Bibliographic Details
Main Authors: Ahmad Afiq Iqmal, Ahmad Saidi, Lai, Jing Yee, Zhen, Ivy Lee Xin, Syariza, Abdul-Rahman
Other Authors: syariza@uum.edu.my
Format: Article
Language:English
Published: Institute of Engineering Mathematics, Universiti Malaysia Perlis 2022
Subjects:
Greedy heuristics
Knapsack problem
Maximum benefit
Optimization
Point redemption
Online Access:http://dspace.unimap.edu.my:80/xmlui/handle/123456789/74165
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.unimap-74165
record_format dspace
spelling my.unimap-741652022-02-15T08:02:19Z Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem Ahmad Afiq Iqmal, Ahmad Saidi Lai, Jing Yee Zhen, Ivy Lee Xin Syariza, Abdul-Rahman syariza@uum.edu.my Greedy heuristics Knapsack problem Maximum benefit Optimization Point redemption Link to publisher's homepage at https://amci.unimap.edu.my/ 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. 2022-02-15T08:02:19Z 2022-02-15T08:02:19Z 2021-12 Article Applied Mathematics and Computational Intelligence (AMCI), vol.10(1), 2021, pages 78-86 2289-1315 (print) 2289-1323 (online) http://dspace.unimap.edu.my:80/xmlui/handle/123456789/74165 https://amci.unimap.edu.my/ en Institute of Engineering Mathematics, Universiti Malaysia Perlis
institution Universiti Malaysia Perlis
building UniMAP Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Malaysia Perlis
content_source UniMAP Library Digital Repository
url_provider http://dspace.unimap.edu.my/
language English
topic Greedy heuristics
Knapsack problem
Maximum benefit
Optimization
Point redemption
spellingShingle Greedy heuristics
Knapsack problem
Maximum benefit
Optimization
Point redemption
Ahmad Afiq Iqmal, Ahmad Saidi
Lai, Jing Yee
Zhen, Ivy Lee Xin
Syariza, Abdul-Rahman
Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
description Link to publisher's homepage at https://amci.unimap.edu.my/
author2 syariza@uum.edu.my
author_facet syariza@uum.edu.my
Ahmad Afiq Iqmal, Ahmad Saidi
Lai, Jing Yee
Zhen, Ivy Lee Xin
Syariza, Abdul-Rahman
format Article
author Ahmad Afiq Iqmal, Ahmad Saidi
Lai, Jing Yee
Zhen, Ivy Lee Xin
Syariza, Abdul-Rahman
author_sort Ahmad Afiq Iqmal, Ahmad Saidi
title Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
title_short Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
title_full Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
title_fullStr Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
title_full_unstemmed Comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
title_sort comparison between exact optimization and heuristics approaches for maximizing benefit of point redemption: a knapsack problem
publisher Institute of Engineering Mathematics, Universiti Malaysia Perlis
publishDate 2022
url http://dspace.unimap.edu.my:80/xmlui/handle/123456789/74165
_version_ 1729704734682513408
score 13.222552

Similar Items