Solving Knapsack Problem with Interval Type-2 Triangular Fuzzy Numbers

EasyChair Preprint 6282

Abstract

In this work, a mean value footprint of uncertainty(MVFOU) method has been proposed for solving Fuzzy Knapsack Problem with Interval Type-2 Triangular Fuzzy numbers as its coefficients. The Knapsack problem is a combinatorial optimization problem with the goal of finding, in a set of items of given prices and weights, the subset of items with the maximum total price, subject to a total weight constraint. In the Knapsack problem, the given items have two attributes at a minimum - an item's value which affects its importance, and an item's weight, which is its limitation aspect. There exist some cases in which the precise value of weight or(and) prices is(are) not specified, but rather a range for these is given. Complexity arises when the possibility of falling of these values within a specified range is also not fixed. In such cases, instead of using real numbers, we rather use fuzzy numbers or more specifically an interval type-2 fuzzy numbers as the coefficients for the values and/or weight of the items. In the first stage of solving a fuzzy knapsack problem with interval type-2 triangular fuzzy numbers, the problem is converted into three different crisp knapsack problems which are then solved optimally by using dynamic programming methods. Then in the second stage, with the help of PGMIR method, feasible solution(s) are selected. The feasible solution for which the profit earned is maximum is known as optimal solution of the problem. In order to explain the methodology, a numerical example has also been worked out in this paper.

Keyphrases: Fuzzy Knapsack Problem, Interval Type-2 Triangular Fuzzy Numbers, Mean Value and Footprint of uncertainty method Dynamic Programming method, Parametric Graded Mean Integration Representation method.

@booklet{EasyChair:6282,
  author    = {Vishnu Singh and Madhav Singh and Kirti Sharma},
  title     = {Solving Knapsack Problem with Interval Type-2 Triangular Fuzzy Numbers},
  howpublished = {EasyChair Preprint 6282},
  year      = {EasyChair, 2021}}