An Approach to Solve Fuzzy Knapsack Problem in Investment and Business Model

An Approach to Solve Fuzzy Knapsack Problem in Investment and Business Model

Vishnu Pratap Singh (Visvesvaraya National Institute of Technology Nagpur, India)
Copyright: © 2020 |Pages: 20
DOI: 10.4018/978-1-5225-7850-5.ch007


In this chapter, the author studies the knapsack problem with fuzzy weights for single and bi-objective function. The knapsack problem has been widely used in the investment and business model. In real-world decision-making situations, the existence of fuzziness of the weights and the profit is a common requirement. To overcome this difficulty, these weights and profit can be considered as a triangular fuzzy number. Thus, a fuzzy knapsack problem is introduced. The author introduces the possibility index which gives the possibility of choosing the items with fuzzy weights for knapsack with crisp capacity. The possibility index gives an idea to choose the solution according to the decision maker's choice. The dynamic programming approach using multi-stage decision making has been given for the different type of decision makers to find the solution. An investment problem in an imprecise environment has been defined as a fuzzy knapsack problem and the solution procedure is given to demonstrate the methodology.
Chapter Preview


The knapsack problem is one of the most relevant mathematical programming problem with numerous applications in different areas. The knapsack problem (Martello et al, 199) is a problem where a tramper is searching for a combination of different items for filling the knapsack. The objective is to optimize the total utility value of all chosen items by the tramper subject to the total weight of chosen items is less than the capacity of a knapsack. The knapsack may correspond to a ship, truck or a resource. There are varieties of applications available for fuzzy knapsack problem such as various packing problem, cargo loading, cutting stock or economic planning. For example the problem of making investment decisions in which the size of an investment is based on the amount of money required, the knapsack capacity is the amount of available money to invest, the investment profit is the expected return. Knapsack problem has a simple structure which permits it to study in combinatorial optimization problems.

In the real world, the utility value used for knapsack problem is imprecise in nature because of the presence of inherent subjectivity. Some researcher used fuzzy theory to solve this type of problem. (Singh et al, 2017) proposed the fuzzy set theory, using this theory (Okada et al, 1994) described multiple-choice knapsack problem with fuzzy coefficients. (Kasperski eta l, 2007) solved the 0-1 knapsack problem with fuzzy data. (Lin et al, 2001) described fuzzy knapsack problem (FKP) by taking each weight wi, i=1,2,…,n as imprecise value. They consider 978-1-5225-7850-5.ch007.m01 as fuzzy number such that the decision maker should determine an acceptable range of values for each 978-1-5225-7850-5.ch007.m02, which is the interval 978-1-5225-7850-5.ch007.m03 and 0≤∆i2. Then the decision maker chooses a value from the interval 978-1-5225-7850-5.ch007.m04 as an estimate of each weight. Estimate is exactly wi if the acceptable grade is 1, otherwise, the acceptable grade will get smaller when the estimate approaches either wi-∆i2 or wi+∆i2.To calculate an estimate of the fuzzy weight defuzzification of the fuzzy number 978-1-5225-7850-5.ch007.m05 from the interval 978-1-5225-7850-5.ch007.m06 has been used.

Complete Chapter List

Search this Book: