An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure

DOI10.1287/OPRE.33.1.49zbMath0569.90038OpenAlexW2088674138MaRDI QIDQ3686413

John E. Beasley

Publication date: 1985

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/opre.33.1.49

zbMATH Keywords

Lagrangean relaxationcutting stocktwo-dimensional cuttingtree searchSubgradient optimizationrectangular pieces

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Production models (90B30) Boolean programming (90C09)

Related Items (only showing first 100 items - show all)

Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem ⋮ A simulated annealing approach for the circular cutting problem ⋮ A mathematical model and a solution method for the problem of placing various-sized circles into a strip ⋮ A population heuristic for constrained two-dimensional non-guillotine cutting ⋮ Logistic constraints in container loading problems: the impact of complete shipment conditions ⋮ On the effectivity of gradient methods for cutting stock problems ⋮ A hybrid evolutionary algorithm for the two-dimensional packing problem ⋮ A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang ⋮ A hybrid algorithm based on variable neighbourhood for the strip packing problem ⋮ An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry ⋮ Practical adaptations of the Gilmore-Gomory approach to cutting stock problems ⋮ An improved typology of cutting and packing problems ⋮ PackLib\(^{2}\): an integrated library of multi-dimensional packing problems ⋮ A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem ⋮ A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem ⋮ Logic based Benders' decomposition for orthogonal stock cutting problems ⋮ An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation ⋮ A simple randomized algorithm for two-dimensional strip packing ⋮ Models and algorithms for packing rectangles into the smallest square ⋮ Efficient heuristics for robot acquisition planning for a CIM system ⋮ Packing into the smallest square: worst-case analysis of lower bounds ⋮ A hybrid demon algorithm for the two-dimensional orthogonal strip packing problem ⋮ Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem ⋮ An application of simulated annealing to the cutting stock problem ⋮ Regular packing of congruent polygons on the rectangular sheet ⋮ An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems ⋮ Packing different-sized circles into a rectangular container ⋮ An analytical model for the container loading problem ⋮ A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing ⋮ An exact algorithm for general, orthogonal, two-dimensional knapsack problems ⋮ A method for the cutting stock problem with different qualities ⋮ On the weak computability of a four dimensional orthogonal packing and time scheduling problem ⋮ An EDA for the 2D knapsack problem with guillotine constraint ⋮ A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects ⋮ MPQ-trees for the orthogonal packing problem ⋮ Symmetry-breaking constraints for packing identical rectangles within polyhedra ⋮ A skyline heuristic for the 2D rectangular packing and strip packing problems ⋮ Maximizing revenue with allocation of multiple advertisements on a Web banner ⋮ The three-dimensional knapsack problem with balancing constraints ⋮ Integer programming formulations for approximate packing circles in a rectangular container ⋮ Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation ⋮ Characterization and modelling of guillotine constraints ⋮ On the two-dimensional knapsack problem ⋮ Minimum tiling of a rectangle by squares ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Cutting stock problems and solution procedures ⋮ Application of the method of Lagrangian multipliers in the combinatorial problem of rectangle arrangement ⋮ Rectangle blanket problem: binary integer linear programming formulation and solution algorithms ⋮ Reactive GRASP for the strip-packing problem ⋮ Packing circular-like objects in a rectangular container ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ Two-dimensional knapsack-block packing problem ⋮ Lagrangean relaxation with clusters for point-feature cartographic label placement problems ⋮ Composite stock cutting through simulated annealing ⋮ Knowledge based approach to the cutting stock problem ⋮ Packing problems ⋮ Heuristic approaches for the two- and three-dimensional knapsack packing problem ⋮ MIP-based approaches for the container loading problem with multi-drop constraints ⋮ A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem ⋮ Three-dimensional container loading models with cargo stability and load bearing constraints ⋮ An efficient deterministic heuristic for two-dimensional rectangular packing ⋮ Recent advances on two-dimensional bin packing problems ⋮ A new heuristic recursive algorithm for the strip rectangular packing problem ⋮ Bidirectional best-fit heuristic for orthogonal rectangular strip packing ⋮ A branch-and-cut algorithm for the pallet loading problem ⋮ Grids for cutting and packing problems: a study in the 2D knapsack problem ⋮ Practical constraints in the container loading problem: comprehensive formulations and exact algorithm ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ Queue-constrained packing: a vehicle ferry case study ⋮ Computing stable loads for pallets ⋮ An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem ⋮ A bidirectional building approach for the 2D constrained guillotine knapsack packing problem ⋮ A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem ⋮ The maximum diversity assortment selection problem ⋮ On calculating the packing efficiency for embedding hexagonal and dodecagonal sensors in a circular container ⋮ Approximation algorithm for the oriented two-dimensional bin packing problem ⋮ A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem ⋮ The exact solutions of several types of container loading problems ⋮ A branch and bound algorithm for the strip packing problem ⋮ Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem ⋮ An open space based heuristic for the 2D strip packing problem with unloading constraints ⋮ An algorithm for the two-dimensional assortment problem ⋮ A two-phase approach for single container loading with weakly heterogeneous boxes ⋮ An exact algorithm for the pallet loading problem ⋮ A recursive exact algorithm for weighted two-dimensional cutting ⋮ The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems ⋮ Efficient automated pallet loading ⋮ Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations ⋮ Load planning for shipments of low density products ⋮ A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting ⋮ Some experiments with a simple tabu search algorithm for the manufacturer's pallet loading problem ⋮ Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems ⋮ Two-dimensional packing problems: a survey ⋮ LP models for bin packing and cutting stock problems ⋮ An \(n\)-tet graph approach for non-guillotine packings of \(n\)-dimensional boxes into an \(n\)-container ⋮ An effective quasi-human based heuristic for solving the rectangle packing problem ⋮ Strip based compact formulation for two-dimensional guillotine cutting problems ⋮ On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns ⋮ 2DPackLib: a two-dimensional cutting and packing library ⋮ Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem

This page was built for publication: An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure