Heuristic approaches for the two- and three-dimensional knapsack packing problem

DOI10.1016/J.COR.2007.12.004zbMath1162.90542OpenAlexW2058038705WikidataQ58826413 ScholiaQ58826413MaRDI QIDQ958438

Jens Egeblad, David Pisinger

Publication date: 4 December 2008

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2007.12.004

zbMATH Keywords

heuristicssimulated annealingthree-dimensional knapsack problemcutting and packingsequence pairsequence-trippletwo-dimensional knapsack problems

Mathematics Subject Classification ID

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

Related Items (31)

2DCPackGen: a problem generator for two-dimensional rectangular cutting and packing problems ⋮ An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem ⋮ A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem ⋮ The load-balanced multi-dimensional bin-packing problem ⋮ A cutting plane method and a parallel algorithm for packing rectangles in a circular container ⋮ An MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts ⋮ An EDA for the 2D knapsack problem with guillotine constraint ⋮ Maximizing revenue with allocation of multiple advertisements on a Web banner ⋮ The three-dimensional knapsack problem with balancing constraints ⋮ Solving packing problems by a distributed global optimization algorithm ⋮ An iterated local search algorithm for a place scheduling problem ⋮ Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review ⋮ Two-dimensional knapsack-block packing problem ⋮ A new load balance methodology for container loading problem in road transportation ⋮ A least wasted first heuristic algorithm for the rectangular packing problem ⋮ A global search framework for practical three-dimensional packing with variable carton orientations ⋮ A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem ⋮ A fast heuristic for a three-dimensional non-convex domain loading problem ⋮ An efficient deterministic heuristic for two-dimensional rectangular packing ⋮ Practical constraints in the container loading problem: comprehensive formulations and exact algorithm ⋮ A comparative review of 3D container loading algorithms ⋮ The maximum diversity assortment selection problem ⋮ Data Structures for Higher-Dimensional Rectilinear Packing ⋮ Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem ⋮ Placement of two- and three-dimensional irregular shapes for inertia moment and balance ⋮ Three-dimensional bin packing problem with variable bin height ⋮ Heuristics for container loading of furniture ⋮ Model Development and Optimization for Space Engineering: Concepts, Tools, Applications, and Perspectives ⋮ Constraints in container loading -- a state-of-the-art review

Uses Software

• Knapsack
• Algorithm 864

Cites Work

• Unnamed Item
• Unnamed Item
• A general framework for bounds for higher-dimensional orthogonal packing problems.
• On genetic algorithms for the packing of polygons
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• On the two-dimensional knapsack problem
• Heuristics for the container loading problem
• Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem
• A population heuristic for constrained two-dimensional non-guillotine cutting
• The two-dimensional bin packing problem with variable bin sizes and costs
• An improved typology of cutting and packing problems
• A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
• An Exact Approach to the Strip-Packing Problem
• Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
• Denser Packings Obtained in O(n log log n) Time
• A parallel hybrid local search algorithm for the container loading problem
• An Exact Algorithm for Higher-Dimensional Orthogonal Packing
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• An Algorithm for Two-Dimensional Cutting Problems
• A Minimal Algorithm for the 0-1 Knapsack Problem
• A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems
• New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem

This page was built for publication: Heuristic approaches for the two- and three-dimensional knapsack packing problem