An Exact Algorithm for Higher-Dimensional Orthogonal Packing

Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing feasible packings with our new classes of lower bounds, and other heuristics, we develop a two-level tree search algorithm for solving higher-dimensional packing problems to optimality. Computational results are reported, including optimal solutions for all two-dimensional test problems from recent literature. This is the third in a series of articles describing new approaches to higher-dimensional packing.

• Publication year

  2006

• Venue

  Operational Research

• Publication date

  2006-04-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1287/opre.1060.0369arXiv cs/0604045
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• I Computational Complexity

  2005cited by this paper
• A General Framework for Bounds for Higher-Dimensional Orthogonal Packing Problems

  2004influential reference
• On the two-dimensional Knapsack Problem

  2004cited by this paper
• A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing

  2003influential reference
• Optimization of Dynamic Hardware Reconfigurations

  2001cited by this paper
• Higher-Dimensional Packing with Order Constraints

  2001cited by this paper
• New classes of fast lower bounds for bin packing problems

  2001cited by this paper
• Òòòûòòøø Ååøøøññøøø Ùòò Áòòóöññøøø Íòòúúö××ø Ø Þù Ã Óðò

  2000influential reference
• The Three-Dimensional Bin Packing Problem

  2000influential reference
• Packing small boxes into a big box

  2000cited by this paper
• Òòòûòòøø Ååøøøññøøø Ùòò Áòòóöññøøø Íòòúúö××ø Ø Þù Ã Óðò

  2000influential reference
• Òòòûòòøø Ååøøøññøøø Ùòò Áòòóöññøøø Íòòúúö××ø Ø Þù Ã Óðò

  2000cited by this paper
• New Classes of Lower Bounds for Bin Packing Problems

  1998cited by this paper
• Exact Solution of the Two-Dimensional Finite Bon Packing Problem

  1998cited by this paper
• On the Solution of Traveling Salesman Problems

  1998cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• A New Exact Algorithm for General Orthogonal D-Dimensional Knapsack Problems

  1997influential reference
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems

  1995influential reference
• An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems

  1995cited by this paper
• Data structures and efficient algorithms

  1992cited by this paper
• Knapsack Problems: Algorithms and Computer Implementations

  1990influential reference
• OR-Library: Distributing Test Problems by Electronic Mail

  1990cited by this paper
• Performance of various computers using standard linear equations software

  1990cited by this paper
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs

  1989cited by this paper
• Integer and Combinatorial Optimization

  1988cited by this paper
• An exact algorithm for the pallet loading problem

  1987cited by this paper
• Algorithmic graph theory and perfect graphs

  1986influential reference
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure

  1985cited by this paper
• Network flows and non-guillotine cutting patterns

  1984influential reference
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems

  1983cited by this paper
• On the symmetric travelling salesman problem: Solution of a 120-city problem

  1980cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper
• An Algorithm for Two-Dimensional Cutting Problems

  1977cited by this paper
• A Characterization of Comparability Graphs and of Interval Graphs

  1964cited by this paper

• Solving a large-scale 3D packing problem with robot constraints

  2026cites this paper
• Filtered beam search algorithm for the two-dimensional rectangular packing problem

  2025cites this paper
• Mixed-Integer and Constraint Programming Models for the Two-Dimensional Guillotine Cutting Problem

  2025cites this paper
• EATKG: An Open-Source Efficient Exact Algorithm for the Two-Dimensional Knapsack Problem with Guillotine Constraints

  2025cites this paper
• Machine Learning-Assisted Multiobjective Evolutionary Algorithm for Routing and Packing

  2025cites this paper
• Split-Aperture Phased Array Radar Resource Management for Tracking Tasks

  2025cites this paper
• Dynamic feedback algorithm based on spatial corner fitness for solving the three-dimensional multiple bin-size bin packing problem

  2024cites this paper
• A new representation in 3D VLSI floorplan: 3D O-Tree

  2024influential citation
• An exact algorithm for two-dimensional cutting problems based on multi-level pattern

  2024cites this paper
• Maximum Polygon Packing: The CG: SHOP Challenge 2024

  2024cites this paper
• Scheduling for additive manufacturing with two-dimensional packing and incompatible items

  2024cites this paper
• A new branch-and-cut approach for integrated planning in additive manufacturing

  2023cites this paper
• A Constraint Programming Solution to the Guillotine Rectangular Cutting Problem

  2023cites this paper
• The multiple container loading problem with loading docks

  2023cites this paper
• Solving Pallet loading Problem with Real-World Constraints

  2023cites this paper
• A two-phase constructive algorithm for the single container mix-loading problem

  2023cites this paper
• Integrated warehouse assignment and carton configuration optimization using deep clustering-based evolutionary algorithms

  2022cites this paper
• An improved Harris Hawks Optimization algorithm for continuous and discrete optimization problems

  2022cites this paper
• The Floating-Cuts model: a general and flexible mixed-integer programming model for non-guillotine and guillotine rectangular cutting problems

  2022cites this paper
• Modeling soft unloading constraints in the multi-drop container loading problem

  2022cites this paper
• Deep reinforcement learning in POMDPs for 3-D palletization problem

  2022cites this paper
• An Efficient Constructive Heuristic for the Cutting Stock Problem Applied in a Foam Mattress Industry

  2022cites this paper
• A Constructive Heuristic Algorithm for 3D Bin Packing of Irregular Shaped Items

  2022cites this paper
• An introduction to the two-dimensional rectangular cutting and packing problem

  2022cites this paper
• A cutting plane method and a parallel algorithm for packing rectangles in a circular container

  2022cites this paper
• Application of Metaheuristics to Packing Formation Support Systems of Pre-Cut Lumber Factory

  2022cites this paper
• Exact solutions for the 2d-strip packing problem using the positions-and-covering methodology

  2021cites this paper
• The rectangular two-dimensional strip packing problem real-life practical constraints: A bibliometric overview

  2021cites this paper
• NB-IoT via LEO Satellites: An Efficient Resource Allocation Strategy for Uplink Data Transmission

  2021cites this paper
• Adaptive Sequence-Based Heuristic for Two-Dimensional Non-guillotine Packing Problems

  2021cites this paper
• A Branch-and-Cut and a Parallel Algorithm for Packing Two-Dimensional Rectangles in a Circular Container

  2021cites this paper
• Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem

  2021cites this paper
• The maximum diversity assortment selection problem

  2021cites this paper
• A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem

  2021cites this paper
• Carton Set Optimization in E‐commerce Warehouses: A Case Study

  2020cites this paper
• Logistic constraints in container loading problems: the impact of complete shipment conditions

  2020cites this paper
• The Pallet Loading Problem: Three-dimensional bin packing with practical constraints

  2020cites this paper
• A beam search algorithm for the biobjective container loading problem

  2020cites this paper
• Exact solution techniques for two-dimensional cutting and packing

  2020cites this paper
• Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem

  2020cites this paper
• The Vehicle Routing Problem with Stochastic Two-Dimensional Items

  2020cites this paper
• The Offline Group Seat Reservation Knapsack Problem With Profit on Seats

  2019cites this paper
• A Primal Decomposition Algorithm for the Two-dimensional Bin Packing Problem

  2019influential citation
• Progressively-Refined Tree Search for Container Loading Problem

  2019cites this paper
• A MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts

  2019cites this paper
• An Innovative Genetic Algorithm for a Multi-Objective Optimization of Two-Dimensional Cutting-Stock Problem

  2019cites this paper
• Product packing and stacking under uncertainty: A robust approach

  2019cites this paper
• Adaptive Sequence-Based Heuristic for the Three-Dimensional Bin Packing Problem

  2019cites this paper
• Three-Dimensional Bin Packing and Mixed-Case Palletization

  2019cites this paper
• A mixed-integer linear model for the multiple heterogeneous knapsack problem with realistic container loading constraints and bins' priority

  2019cites this paper
• Optimized Packings in Space Engineering Applications: Part I

  2019cites this paper
• A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem

  2018cites this paper
• Quasi-Monte-Carlo Tree Search for 3D Bin Packing

  2018cites this paper
• MATHEMATICAL MODELLING IN NATURAL SCIENCES AND INFORMATION TECHNOLOGIES PROBLEM OF CONVECTIVE HEAT CONDUCTIVITY OF A DOUBLE ENVIRONMENT UNDER HEAVY BORDER CONDITIONS

  2018cites this paper
• A multi-objective model for order cartonization and fulfillment center assignment in the e-tail/retail industry

  2018cites this paper
• Packing Compaction Algorithm for Rectangular Cutting and Orthogonal Packing Problems

  2018cites this paper
• Orthogonal Packing Feasibility, Two-Dimensional Knapsack Problems

  2018cites this paper
• An EDA for the 2D knapsack problem with guillotine constraint

  2018cites this paper
• DNestMap: Mapping Deeply-Nested Loops on Ultra-Low Power CGRAs

  2018cites this paper
• A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem

  2018cites this paper
• Developing column generation approach to solve the rectangular two-dimensional single knapsack problem

  2017cites this paper
• Algorithm selection and runtime prediction for the two dimensional bin packing problem; analysis and characterization of instances

  2017cites this paper
• Algorithms and Methods in Multidimensional Orthogonal Packing Problems

  2017cites this paper
• Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints

  2017cites this paper
• An integer programming model for the single container loading problem with axle weight constraints

  2017cites this paper
• Deleting Objects Algorithm for the Optimization of Orthogonal Packing Problems

  2017cites this paper
• Heuristic algorithm for the container loading problem with multiple constraints

  2017cites this paper
• VCS: A new heuristic function for selecting boxes in the single container loading problem

  2017cites this paper
• Two-dimensional Disjunctively Constrained Knapsack Problem: Heuristic and exact approaches

  2017cites this paper
• Combination of nearest neighbor and heuristics algorithms for sequential two dimensional loading capacitated vehicle routing problem

  2017cites this paper
• Developing Column Generation Approach to Solve the Rectangular Two-dimensional Single Knapsack Problem

  2017cites this paper
• The load-balanced multi-dimensional bin-packing problem

  2016cites this paper
• Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming

  2016cites this paper
• Packing Problems in Space Solved by CPLEX: An Experimental Analysis

  2016cites this paper
• An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem

  2016cites this paper
• ALGORITHMS FOR MANAGEMENT OBJECTS IN ORTHOGONAL PACKING PROBLEMS

  2016cites this paper
• Heuristics for Packing Semifluids

  2016cites this paper
• Demand Uncertainty for the Location-Routing Problem with Two-dimensional Loading Constraints

  2016cites this paper
• A comparative review of 3D container loading algorithms

  2016cites this paper
• A container loading algorithm with static mechanical equilibrium stability constraints

  2016cites this paper
• A GRASP ALGORITHM FOR THE CONTAINER LOADING PROBLEM WITH MULTI-DROP CONSTRAINTS

  2015cites this paper
• A New Search Procedure for the Two-dimensional Orthogonal Packing Problem

  2015cites this paper
• Vehicle routing strategies for pick-up and delivery service under two dimensional loading constraints

  2015cites this paper
• Two-Dimensional Bin Packing Problem with Guillotine Restrictions

  2015cites this paper
• UMA PROPOSTA DE MODELO MATEMÁTICO PARA O PROBLEMA DE CARREGAMENTO DE MÚLTIPLOS CONTÊINERES HETEROGÊNEOS COM RESTRIÇÕES ADICIONAIS

  2015cites this paper
• A global optimization approach for solving three-dimensional open dimension rectangular packing problems

  2015cites this paper
• A hybrid differential evolution algorithm for multiple container loading problem with heterogeneous containers

  2015influential citation
• A three-dimensional bin-packing model: exact multicriteria solution and computational complexity

  2015cites this paper
• On the $$L$$L-approach for generating unconstrained two-dimensional non-guillotine cutting patterns

  2015cites this paper
• Heuristics for Multidimensional Packing Problems

  2015cites this paper
• Non-standard Packing Problems: A Modelling-Based Approach

  2014cites this paper
• A tree search algorithm for the container loading problem

  2014cites this paper
• Efficient reconfiguration of processing modules on FPGAs for space instruments

  2014cites this paper
• Hybrid greedy heuristics based on linear programming for the three-dimensional single bin-size bin packing problem

  2014cites this paper
• Résolution de problèmes de bin packing à une dimension par la programmation DC

  2014cites this paper
• UNIVERSIDADE ESTADUAL PAULISTA "JÚLIO DE MESQUITA FILHO" PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA DEPARTAMENTO DE ENGENHARIA ELÉTRICA

  2014cites this paper
• An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints

  2014cites this paper
• Two‐Dimensional Bin Packing Problems

  2014cites this paper
• A New Quasi-Human Algorithm for Solving the Packing Problem of Unit Equilateral Triangles

  2014cites this paper
• A genetic algorithm for the three-dimensional bin packing problem with heterogeneous bins

  2014cites this paper