An Exact Algorithm for Higher-Dimensional Orthogonal Packing
From MaRDI portal
Publication:3392097
DOI10.1287/OPRE.1060.0369zbMATH Open1167.90483arXivcs/0604045OpenAlexW2155839396MaRDI QIDQ3392097FDOQ3392097
Authors: Sándor P. Fekete, Jörg Schepers, Jan C. van der Veen 
Publication date: 13 August 2009
Published in: Operations Research (Search for Journal in Brave)
Abstract: 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; see cs.DS/0310032 and cs.DS/0402044.
Full work available at URL: https://arxiv.org/abs/cs/0604045
Recommendations
- A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
- scientific article; zbMATH DE number 1264415
- A general framework for bounds for higher-dimensional orthogonal packing problems.
- A new exact algorithm for general orthogonal d-dimensional knapsack problems
- scientific article; zbMATH DE number 1183280
Cited In (85)
- On the weak computability of a four dimensional orthogonal packing and time scheduling problem
- Denser packings obtained in \(O(n \log \log n)\) time
- A global search framework for practical three-dimensional packing with variable carton orientations
- A beam search algorithm for the biobjective container loading problem
- Exact solution techniques for two-dimensional cutting and packing
- A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces
- A fast heuristic for a three-dimensional non-convex domain loading problem
- Logistic constraints in container loading problems: the impact of complete shipment conditions
- A better heuristic for area-compaction of orthogonal representations
- A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem
- Routing problems with loading constraints
- Conservative scales in packing problems
- Higher‐Dimensional Packing with Order Constraints
- Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
- Product packing and stacking under uncertainty: a robust approach
- Packing \(n\)-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an \(n\)-dimensional parallelepiped
- Modeling soft unloading constraints in the multi-drop container loading problem
- Title not available (Why is that?)
- VCS: A new heuristic function for selecting boxes in the single container loading problem
- MPQ-trees for orthogonal packing problem
- A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints
- A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP
- One-dimensional relaxations and LP bounds for orthogonal packing
- Modeling two-dimensional guillotine cutting problems via integer programming
- A global optimization approach for solving three-dimensional open dimension rectangular packing problems
- Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows
- A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing
- An exact method for the 2D guillotine strip packing problem
- Exact algorithms for the two-dimensional guillotine knapsack
- A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem
- Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
- A general framework for bounds for higher-dimensional orthogonal packing problems.
- Heuristic approaches for the two- and three-dimensional knapsack packing problem
- A new constraint programming approach for the orthogonal packing problem
- A guided tabu search for the vehicle routing problem with two-dimensional loading constraints
- A new heuristic algorithm for rectangle packing
- The off-line group seat reservation problem
- The pallet loading problem: three-dimensional bin packing with practical constraints
- A branch and bound algorithm for the strip packing problem
- A new search procedure for the two-dimensional orthogonal packing problem
- An MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts
- On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns
- Heuristics for container loading of furniture
- Online square packing with gravity
- Maximizing revenue with allocation of multiple advertisements on a Web banner
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
- The load-balanced multi-dimensional bin-packing problem
- Bidimensional packing by bilinear programming
- A new iterative-doubling greedy-lookahead algorithm for the single container loading problem
- A new quasi-human algorithm for solving the packing problem of unit equilateral triangles
- A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
- A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
- Optimal rectangle packing
- Multi-dimensional bin packing problems with guillotine constraints
- A comparative review of 3D container loading algorithms
- An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints
- An efficient deterministic optimization approach for rectangular packing problems
- MPQ-trees for the orthogonal packing problem
- Hybrid greedy heuristics based on linear programming for the three-dimensional single bin-size bin packing problem
- Constraints in container loading -- a state-of-the-art review
- Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem
- The two-dimensional bin packing problem with variable bin sizes and costs
- A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
- An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem
- A hybrid genetic algorithm for the two-dimensional single large object placement problem
- A new exact method for the two-dimensional orthogonal packing problem
- A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
- Title not available (Why is that?)
- An introduction to the two‐dimensional rectangular cutting and packing problem
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- The multiple container loading problem with loading docks
- Packing problems in space solved by CPLEX: an experimental analysis
- A two-phase constructive algorithm for the single container mix-loading problem
- A mixed‐integer linear model for the multiple heterogeneous knapsack problem with realistic container loading constraints and bins' priority
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- A linear programming approach for the three-dimensional bin-packing problem
- Lower bounds for three-dimensional multiple-bin-size bin packing problems
- The maximum diversity assortment selection problem
- Efficient algorithms for orthogonal packing problems
- Data structures for higher-dimensional rectilinear packing
- A three-dimensional bin-packing model: exact multicriteria solution and computational complexity
- An EDA for the 2D knapsack problem with guillotine constraint
- A cutting plane method and a parallel algorithm for packing rectangles in a circular container
- Title not available (Why is that?)
- Title not available (Why is that?)
Uses Software
This page was built for publication: An Exact Algorithm for Higher-Dimensional Orthogonal Packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392097)
