AN APPROXIMATION ALGORITHM FOR SOLVING UNCONSTRAINED 2-DIMENSIONAL KNAPSACK-PROBLEMS

An efficient heuristic for solving two-dimensional knapsack problems i s proposed. The algorithm selects an optimal subset of optimal generat ed strips by solving a sequence of one-dimensional knapsack problems. We show that the number of these knapsacks can be reduced to only four knapsacks. The algorithm gives an excellent worst-case experimental a pproximation ratio (0.98), and a high percentage of optimal solutions (91%). From this heuristic, we derive an approximation algorithm for w hich we prove some refined bounds and we show that its approximation r atio is 4/9. Our numerical study on large size instances shows the eff iciency of these algorithms for solving real-world problems which are hardly handled by other known methods, which are often limited by comp uter storage facilities.