A general framework for bounds for higher-dimensional orthogonal packing problems.
From MaRDI portal
Publication:703155
DOI10.1007/S001860400376zbMATH Open1076.90049arXivcs/0402044OpenAlexW1713438669MaRDI QIDQ703155FDOQ703155
Authors: Sándor P. Fekete, Jörg Schepers 
Publication date: 11 January 2005
Published in: Mathematical Methods of 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. In the context of a branch-and-bound framework for solving these packing problems to optimality, it is of crucial importance to have good and easy bounds for an optimal solution. Previous efforts have produced a number of special classes of such bounds. Unfortunately, some of these bounds are somewhat complicated and hard to generalize. We present a new approach for obtaining classes of lower bounds for higher-dimensional packing problems; our bounds improve and simplify several well-known bounds from previous literature. In addition, our approach provides an easy framework for proving correctness of new bounds.
Full work available at URL: https://arxiv.org/abs/cs/0402044
Recommendations
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Cited In (52)
- A two-phase constructive algorithm for the single container mix-loading problem
- On the weak computability of a four dimensional orthogonal packing and time scheduling problem
- Exact solution techniques for two-dimensional cutting and packing
- Title not available (Why is that?)
- An introduction to the two‐dimensional rectangular cutting and packing problem
- Conservative scales in packing problems
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- Higher‐Dimensional Packing with Order Constraints
- Packing \(n\)-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an \(n\)-dimensional parallelepiped
- A computational study of lower bounds for the two dimensional bin packing problem
- New lower bounds for bin packing problems with conflicts
- Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization
- A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates
- An Exact Algorithm for Higher-Dimensional Orthogonal Packing
- The minimum raster set problem and its application to the \(d\)-dimensional orthogonal packing problem
- A skyline heuristic for the 2D rectangular packing and strip packing problems
- One-dimensional relaxations and LP bounds for orthogonal packing
- A hybrid algorithm for constrained order packing
- New data-dependent dual-feasible functions and lower bounds for a two-dimensional bin-packing problem
- 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
- A survey of dual-feasible and superadditive functions
- Queue-constrained packing: a vehicle ferry case study
- New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation
- Lower bounds for three-dimensional multiple-bin-size bin packing problems
- Heuristic approaches for the two- and three-dimensional knapsack packing problem
- An agent-based approach to the two-dimensional guillotine bin packing problem
- A new constraint programming approach for the orthogonal packing problem
- Determining the best shipper sizes for sending products to customers
- Upper bounds for heuristic approaches to the strip packing problem
- LP bounds in various constraint programming approaches for orthogonal packing
- A branch and bound algorithm for the strip packing problem
- A branch-and-price algorithm for the two-dimensional level strip packing problem
- Single batch machine scheduling with dual setup times for autoclave molding manufacturing
- The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview
- A new exact method for the two-dimensional bin-packing problem with fixed orientation
- Bidimensional packing by bilinear programming
- A new quasi-human algorithm for solving the packing problem of unit equilateral triangles
- Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem
- A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
- Optimal rectangle packing
- Title not available (Why is that?)
- Relations between capacity utilization, minimal bin size and bin number
- Using dual feasible functions to construct fast lower bounds for routing and location problems
- A lookahead matheuristic for the unweighed variable-sized two-dimensional bin packing problem
- A new lower bound for the non-oriented two-dimensional bin-packing problem
- New resolution algorithm and pretreatments for the two-dimensional bin-packing problem
- Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems
- An exact algorithm for the two-dimensional stage-unrestricted guillotine cutting/packing decision problem
- A new exact method for the two-dimensional orthogonal packing problem
- Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution
- A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
This page was built for publication: A general framework for bounds for higher-dimensional orthogonal packing problems.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q703155)
