An Exact Algorithm for Higher-Dimensional Orthogonal Packing
From MaRDI portal
Publication:3392097
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.
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
- A global search framework for practical three-dimensional packing with variable carton orientations
- Denser packings obtained in \(O(n \log \log n)\) time
- A beam search algorithm for the biobjective container loading problem
- Exact solution techniques for two-dimensional cutting and packing
- A fast heuristic for a three-dimensional non-convex domain loading problem
- A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces
- 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
- An introduction to the two‐dimensional rectangular cutting and packing problem
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- Higher‐Dimensional Packing with Order Constraints
- 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
- Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
- Packing problems in space solved by CPLEX: an experimental analysis
- The multiple container loading problem with loading docks
- Modeling soft unloading constraints in the multi-drop container loading problem
- scientific article; zbMATH DE number 1225305 (Why is no real title available?)
- VCS: A new heuristic function for selecting boxes in the single container loading problem
- MPQ-trees for orthogonal packing problem
- A two-phase constructive algorithm for the single container mix-loading 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
- 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
- One-dimensional relaxations and LP bounds for orthogonal packing
- A linear programming approach for the three-dimensional bin-packing problem
- A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing
- Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows
- Modeling two-dimensional guillotine cutting problems via integer programming
- A global optimization approach for solving three-dimensional open dimension rectangular packing problems
- An exact method for the 2D guillotine strip packing problem
- Exact algorithms for the two-dimensional guillotine knapsack
- Lower bounds for three-dimensional multiple-bin-size bin packing problems
- 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.
- A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem
- Heuristic approaches for the two- and three-dimensional knapsack packing problem
- A new constraint programming approach for the orthogonal packing problem
- A new heuristic algorithm for rectangle packing
- The off-line group seat reservation problem
- A guided tabu search for the vehicle routing problem with two-dimensional loading constraints
- The maximum diversity assortment selection problem
- A branch and bound algorithm for the strip packing problem
- The pallet loading problem: three-dimensional bin packing with practical constraints
- A new search procedure for the two-dimensional orthogonal packing problem
- Data structures for higher-dimensional rectilinear packing
- Efficient algorithms for orthogonal packing problems
- 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 three-dimensional bin-packing model: exact multicriteria solution and computational complexity
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
- An EDA for the 2D knapsack problem with guillotine 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 cutting plane method and a parallel algorithm for packing rectangles in a circular container
- A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
- Optimal rectangle packing
- Multi-dimensional bin packing problems with guillotine constraints
- scientific article; zbMATH DE number 1830743 (Why is no real title available?)
- A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
- 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
- Constraints in container loading -- a state-of-the-art review
- Hybrid greedy heuristics based on linear programming for the three-dimensional single bin-size bin packing problem
- 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
- scientific article; zbMATH DE number 2086789 (Why is no real title available?)
- A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
- scientific article; zbMATH DE number 1183280 (Why is no real title available?)
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)
