An Exact Algorithm for Higher-Dimensional Orthogonal Packing
From MaRDI portal
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
(90)- Bidimensional packing by bilinear programming
- A branch and bound algorithm for the strip packing problem
- Heuristics for container loading of furniture
- A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem
- VCS: A new heuristic function for selecting boxes in the single container loading problem
- A new quasi-human algorithm for solving the packing problem of unit equilateral triangles
- Product packing and stacking under uncertainty: a robust approach
- A two-stage tabu search algorithm with enhanced packing heuristics for the 3L-CVRP and M3L-CVRP
- A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints
- A global search framework for practical three-dimensional packing with variable carton orientations
- A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint
- Exact algorithms for the two-dimensional guillotine knapsack
- A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
- Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows
- A new iterative-doubling greedy-lookahead algorithm for the single container loading problem
- MPQ-trees for the orthogonal packing problem
- Conservative scales in packing problems
- The pallet loading problem: three-dimensional bin packing with practical constraints
- Exact solution techniques for two-dimensional cutting and packing
- The maximum diversity assortment selection problem
- A beam search algorithm for the biobjective container loading problem
- Lower bounds for three-dimensional multiple-bin-size bin packing problems
- On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns
- Constraints in container loading -- a state-of-the-art review
- A guided tabu search for the vehicle routing problem with two-dimensional loading constraints
- A three-dimensional bin-packing model: exact multicriteria solution and computational complexity
- An EDA for the 2D knapsack problem with guillotine constraint
- A new constraint programming approach for the orthogonal packing problem
- A better heuristic for area-compaction of orthogonal representations
- 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
- 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 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
- A comparative review of 3D container loading algorithms
- Data structures for higher-dimensional rectilinear packing
- A linear programming approach for the three-dimensional bin-packing problem
- An efficient deterministic optimization approach for rectangular packing problems
- MPQ-trees for orthogonal packing problem
- Denser packings obtained in O(n n) time
- An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints
- An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem
- Modeling two-dimensional guillotine cutting problems via integer programming
- Packing problems in space solved by CPLEX: an experimental analysis
- A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces
- One-dimensional relaxations and LP bounds for orthogonal packing
- The load-balanced multi-dimensional bin-packing problem
- A global optimization approach for solving three-dimensional open dimension rectangular packing problems
- scientific article; zbMATH DE number 1183280 (Why is no real title available?)
- On the weak computability of a four dimensional orthogonal packing and time scheduling problem
- scientific article; zbMATH DE number 1225305 (Why is no real title available?)
- A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
- Packing \(n\)-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an \(n\)-dimensional parallelepiped
- scientific article; zbMATH DE number 2086789 (Why is no real title available?)
- Online square packing with gravity
- scientific article; zbMATH DE number 1830743 (Why is no real title available?)
- Approximation Algorithms for the Orthogonal Z-Oriented Three-Dimensional Packing Problem
- Hybrid greedy heuristics based on linear programming for the three-dimensional single bin-size bin packing problem
- Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
- A fast heuristic for a three-dimensional non-convex domain loading problem
- Efficient algorithms for orthogonal packing problems
- Higher‐Dimensional Packing with Order Constraints
- A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- An introduction to the two‐dimensional rectangular cutting and packing problem
- An exact method for the 2D guillotine strip packing problem
- A mixed‐integer linear model for the multiple heterogeneous knapsack problem with realistic container loading constraints and bins' priority
- A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem
- A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing
- Optimal rectangle packing
- Routing problems with loading constraints
- The off-line group seat reservation problem
- The multiple container loading problem with loading docks
- Modeling soft unloading constraints in the multi-drop container loading problem
- Maximizing revenue with allocation of multiple advertisements on a Web banner
- A two-phase constructive algorithm for the single container mix-loading problem
- EATKG: an open-source efficient \underline{E}xact \underline{A}lgorithm for the \underline{T}wo-dimensional \underline{K}napsack problem with \underline{G}uillotine constraints
- Filtered beam search algorithm for the two-dimensional rectangular packing problem
- A new branch-and-cut approach for integrated planning in additive manufacturing
- A general framework for bounds for higher-dimensional orthogonal packing problems.
- Mixed-integer and constraint programming models for the two-dimensional guillotine cutting problem
- Solving a large-scale 3D packing problem with robot constraints
- Logistic constraints in container loading problems: the impact of complete shipment conditions
- A new heuristic algorithm for rectangle packing
- A new search procedure for the two-dimensional orthogonal packing problem
- Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
- Heuristic approaches for the two- and three-dimensional knapsack packing problem
- Multi-dimensional bin packing problems with guillotine constraints
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)
