In this article we identify a class of two-dimensional knapsack problems with binary weights and related three-criteria unconstrained combinatorial optimization problems that can be solved in polynomial time by greedy algorithms. Starting from the knapsack problem with two equality constraints we show that this problem can be solved efficiently by using an appropriate partitioning of the items with respect to their binary weights. Based on the results for this problem we derive an algorithm for the three-criteria unconstrained combinatorial optimization problem with two binary objectives that explores the connectedness of the set of efficient knapsacks with respect to a combinatorial definition of adjacency. Furthermore, we prove that our approach is asymptotically optimal and provide extensive computational experiments that shows that we can solve the three-criteria problem with up to one million items in less than half an hour. Finally, we derive an efficient algorithm for the two-dimensional knapsack problems with binary constraints that only takes into account the results we obtained for the unconstrained three-criteria problem with binary weights.
Computers & Operations Research, Vol. 39, #3, pp. 498-511, Elsevier, February 2012
Cited by
Year 2015 : 1 citations
C Changdar, GS Mahapatra
An improved genetic algorithm based approach to solve constrained knapsack problem in fuzzy environment
Expert Systems with Applications, 2015
Year 2014 : 5 citations
N Nikolic, I Grujicic, N Mladenovic,A large neighbourhood search heuristic for covering designs, IMA Journal of Management Mathematics, 2014
A Rong, JR Figueira, Dynamic programming algorithms for the bi-objective integer knapsack problem, European Journal of Operational Research, 2014
C Changdar, GS Mahapatra, RK Pal, An improved genetic algorithm based approach to solve constrained knapsack problem in fuzzy environment, Expert Systems with Applications, 2014
N Tcholtchev, I Schieferdecker, Framework for ensuring runtime stability of control loops in multi-agent networked environments, Transactions on Computational Science, 2014
N Nikolic, M Cangalovic, I Grujicic,Symmetry properties of resolving sets and metric bases in hypercubes, Optimization Letters
Year 2013 : 3 citations
A Rong, K Klamroth, J Rui Figueira, Multicriteria 0-1 knapsack problems with k-min objectives, Computers & Operations Research, Volume 40 Issue 5, Pages 1481-1496, 2013
Rung-Ching Chen, Yung-Da Lin, Chia-Ming Tsai, Huiqin Jiang, Constructing a Diet Recommendation System Based on Fuzzy Rules and Knapsack Method, Recent Trends in Applied Artificial Intelligence, Lecture Notes in Computer Science Volume 7906, 2013, pp 490-500
G. H. van der Velde, STREAMLINING STORAGE OF TEST EQUIPMENT AT SIEMENS HENGELO: A CAPACITY BASED APPROACH, MSc thesis, University of Twente, 2013.
Year 2012 : 1 citations
Wei Liu, Gang Liu, "Genetic Algorithm with Directional Mutation Based on Greedy Strategy for Large-scale 0-1 Knapsack Problems", IJACT: International Journal of Advancements in Computing Technology, Vol. 4, No. 3, pp. 66- 74, 2012
