Knapsack problem in fuzzy nature: Different models based on credibility ranking method
DOI:
https://doi.org/10.2298/YJOR210219021NKeywords:
fuzzy knapsack problem, credibility ranking method, expected-value model, chance-constraint model, pre-disaster investment decision problemAbstract
This paper deals with knapsack problem in fuzzy nature, where both the objective function and constraints are considered to be fuzzy. Three different models for fuzzy knapsack problem are proposed including, expected value model, chance-constrained model, and dependent-chance model. Credibility ranking method is applied to convert the fuzzy models into a crisp equivalent linear one considering triangular and trapezoidal fuzzy numbers. The solution of the fuzzy problem is obtained with respect to different satisfaction degrees in the objective function and constraints. Several numerical examples are given to demonstrate different models and concepts. The proposed approaches are applied to model and to solve a fuzzy pre-disaster investment decision problem.References
Abass, S. A., and Abdallah, A. S., "Stability of Multiple Knapsack Problems with Interval Capacities", Journal of Advances in Mathematics and Computer Science, 2018, 1-11.
Abboud, N. J., Sakawa, M., and Inuiguchi, M., "A fuzzy programming approach to multiobjective multidimensional 0-1 knapsack problems", Fuzzy sets and systems, 86 (1) (1997) 1-14.
Attari, H., and Nasseri, S. H, "New concepts of feasibility and efficiency of solutions in fuzzy mathematical programming problems", Fuzzy Information and Engineering, 6 (2) (2014) 203-221.
Buchheim, C., and Kurtz, J., "Robust combinatorial optimization under convex and discrete cost uncertainty", EURO Journal on Computational Optimization, 6 (3) (2018) 211-238.
Chen, S. P., "Analysis of maximum total return in the continuous knapsack problem with fuzzy object weights", Applied Mathematical Modelling, 33 (7) (2009) 2927-2933.
Cheng, L., Rao, C., and Chen, L., "Multidimensional knapsack problem based on uncertain measure", Scientia Iranica. Transaction E, Industrial Engineering, (24) (5) (2017) 2527- 2539.
Coniglio, S., Furini, F., and San, S. P., "A new combinatorial branch-and-bound algorithm for the knapsack problem with conicts", European Journal of Operational Research, 289 (2) (2021) 435-455.
Dang, T., and Peng, M., "Joint radio communication, caching, and computing design for mobile virtual reality delivery in fog radio access networks", IEEE Journal on Selected Areas in Communications, 37 (7) (2019) 1594-1607.
İç, Tansel, Y., Özel, M., and Kara, İ., "An integrated fuzzy TOPSIS-knapsack problem model for order selection in a bakery", Arabian Journal for Science and Engineering, 42 (12) (2017) 5321-5337.
Ivanchev, D., and Radovanova, E., "Realization of knapsack problem solving algorithm and some of its applications", Yugoslav Journal of Operations Research, 19 (1) (2009) 113-122.
Inuiguchi, M., and Ramık, J., "Possibilistic linear programming: a brief review of fuzzy mathematical programming and a comparison with stochastic programming in portfolio selection problem", Fuzzy sets and systems, 111 (1) (2000) 3-28.
Ghatee, M., and Niksirat, M., "A Hop eld neural network applied to the fuzzy maximum cut problem under credibility measure", Information Sciences, 229 (2013) 77-93.
Kasperski, A., and Kulej, M., "The 0-1 knapsack problem with fuzzy data", Fuzzy Optimization and Decision Making, 6 (2) (2007) 163-172.
Khalili, F., Naseri, S. H., and Taghi-Nezhad, N. A., "A new interactive approach for solving fully fuzzy mixed integer linear programming problems", Yugoslav journal of operations research, 30 (1) (2019) 71-89.
Lin, F. T., and Yao, J. S., "Using fuzzy numbers in knapsack problems", European Journal of Operational Research, 135 (1) (2001) 158-176.
Liu, B., and Liu, Y. K., "Expected value of fuzzy variable and fuzzy expected value models", IEEE transactions on Fuzzy Systems, 10 (4) (2002) 445-450.
Mahmoudi, F., and Nasseri, S. H., "A new approach to solve fully fuzzy linear programming problem", Journal of applied research on industrial engineering, 6 (2) (2019) 139-149.
Meng, T., and Pan, Q. K., "An improved fruit y optimization algorithm for solving the multidimensional knapsack problem", Applied Soft Computing, 50 (2017) 79-93.
Mengistu, T., Che, D., and Lu, S., "Multi-objective resource mapping and allocation for volunteer cloud computing", 2019 IEEE 12th International Conference on Cloud Computing (CLOUD), 2019, 344-348.
Mougouei, D., Powers, D. M. W., and Moeini, A., "An integer linear programming model for binary knapsack problem with dependent item values", Australasian Joint Conference on Artificial Intelligence, 2017, 144-154.
Nasseri, S. H., Ebrahimnejad, A., and Cao, B. Y., "Fuzzy linear programming", Fuzzy linear programming: solution techniques and applications, 2019, 39-61.
Niksirat, M., Hashemi, S. M., and Ghatee, M., "Branch-and-price algorithm for fuzzy integer programming problems with block angular structure", Fuzzy Sets and Systems, 296 (2016) 70-96.
Niksirat, M., "Fuzzy Integer Credibility Programming for Modeling and Solving Humanitarian Relief and Transportation Problem After the Crisis Under Uncertainty", Defensive Future Study Researches Journal, 4 (15) (2020) 61-84.
Olivas, F., Amaya, I., Ortiz-Bayliss, J. C., Conant-Pablos, S. E., and Terashima-Marín, H., "Enhancing Hyperheuristics for the Knapsack Problem through Fuzzy Logic", Computational Intelligence and Neuroscience, 2021, (2021)
Peeta, S., and Salman, F. S., Gunnec, D., and Viswanath, K., "Pre-disaster investment decisions for strengthening a highway network", Computers & Operations Research, 37 (10) (2010) 1708-1719.
Ren, A., Wang, Y., and Xue, X., "Interactive programming approach for solving the fully fuzzy bilevel linear programming problem", Knowledge-Based Systems, 99 (2016) 103-111.
Saffarian, M., Niksirat, M., and Kazemi, S. M., "A Hybrid Genetic-Simulated Annealing- Auction Algorithm for a Fully Fuzzy Multi-Period Multi-Depot Vehicle Routing Problem", International Journal of Supply and Operations Management, 8 (2) (2021) 96-113.
Singh, V. P., and Chakraborty, D., "Solving Knapsack Problem with Fuzzy Random Variable Coefficients", International Conference on Innovation in Modern Science and Tech- nology, 1037-1048, 2019.
Singh, V. P., "An Approach to Solve Fuzzy Knapsack Problem in Investment and Business Model", Networked Business Models in the Circular Economy, 154-173, 2020.
Sahoo, A., Hall, T. A., and Hagwood, C., "Optimal dynamic spectrum access scheme for utilizing white space in lte systems", 2019 IEEE Wireless Communications and Networking Conference (WCNC) 1-8, 2019.
Wan, S. P., and Dong, J. Y., "Possibility linear programming with trapezoidal fuzzy numbers", Applied Mathematical Modelling, 38 (5-6) (2014) 1660-1672.
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
