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

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