Solving fuzzy Multidimensional Multiple-Choice Knapsack Problems: The multi-start Partial Bound Enumeration method versus the efficient epsilon-constraint method

In this paper a new fuzzy Multidimensional Multiple-choice Knapsack Problem (MMKP) is proposed. In the proposed fuzzy MMKP, each item may belong to several groups according to a predefined fuzzy membership value. The total profit and the total cost of the knapsack problem are considered as two conflicting objectives. A mathematical approach and a heuristic algorithm are proposed to solve the fuzzy MMKP. One method is an improved version of a well-known exact multi-objective mathematical programming technique, called the efficient ɛ-constraint method. The second method is a heuristic algorithm called multi-start Partial-Bound Enumeration (PBE). Both methods are used to comparatively generate a set of non-dominated solutions for the fuzzy MMKP. The performance of the two methods is statistically compared with respect to a set of simulated benchmark cases using different diversity and accuracy metrics.

Figure optionsDownload as PowerPoint slideHighlights
► A new fuzzy Multidimensional Multiple-Choice Knapsack Problem (MMKP) is proposed.
► An efficient ɛ-constraint method is proposed to solve the fuzzy MMKP.
► A multi-start Partial-Bound Enumeration is also proposed to solve the MMKP.
► Both methods are used to generate non-dominated solutions for the fuzzy MMKP.
► The performance of the two methods is compared with simulated benchmark cases.