An approximation algorithm for solving unconstrained two-dimensional knapsack problems

DOI10.1016/0377-2217(93)E0221-IzbMath0928.90076OpenAlexW2063603369MaRDI QIDQ1127219

Didier Fayard, Vassilios Zissimopoulos

Publication date: 13 August 1998

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(93)e0221-i

zbMATH Keywords

heuristiccutting stocktwo-dimensional knapsack problems

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (22)

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem ⋮ Heuristic for constrained T-shape cutting patterns of rectangular pieces ⋮ An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock ⋮ Two-stage general block patterns for the two-dimensional cutting problem ⋮ Maximizing revenue with allocation of multiple advertisements on a Web banner ⋮ Improving the efficiency of a best-first bottom-up approach for the constrained 2D cutting problem ⋮ Solving packing problems by a distributed global optimization algorithm ⋮ A recursive branch-and-bound algorithm for constrained homogeneous T-shape cutting patterns ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Two-dimensional knapsack-block packing problem ⋮ Simple block patterns for the two-dimensional cutting problem ⋮ Fast heuristic for constrained homogenous T-shape cutting patterns ⋮ Recursive algorithm for the two‐dimensional cutting problem of punched strips ⋮ Grids for cutting and packing problems: a study in the 2D knapsack problem ⋮ A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems ⋮ A recursive exact algorithm for weighted two-dimensional cutting ⋮ The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems ⋮ Applying genetic algorithms and neural networks to the container loading problem ⋮ A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting ⋮ Unnamed Item ⋮ Generating optimal two-section cutting patterns for rectangular blanks ⋮ On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns

Cites Work

• Unnamed Item
• The cutting stock problem for large sections in the iron and steel industries
• Dynamic programming algorithms for the zero-one knapsack problem
• The trim-loss and assortment problems: A survey
• Heuristic algorithms for the multiple knapsack problem
• An algorithm for the solution of the 0-1 knapsack problem
• Cutting stock problems and solution procedures
• Mathematical Methods of Organizing and Planning Production
• Multiprogram scheduling
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems
• Fast Approximation Algorithms for Knapsack Problems
• Technical Note—A Note on Computational Modifications to the Gilmore-Gomory Cutting Stock Algorithm
• An Algorithm for Large Zero-One Knapsack Problems
• Resolution of the 0–1 knapsack problem: Comparison of methods
• A Solution of the Rectangular Cutting-Stock Problem
• Bounds for Multiprocessor Scheduling with Resource Constraints
• An Algorithm for Two-Dimensional Cutting Problems
• Cutting Stock, Linear Programming, Knapsacking, Dynamic Programming and Integer Programming, Some Interconnections
• Multistage Cutting Stock Problems of Two and More Dimensions
• The Theory and Computation of Knapsack Functions
• Recursive Computational Procedure for Two-dimensional Stock Cutting

This page was built for publication: An approximation algorithm for solving unconstrained two-dimensional knapsack problems