An exact strip packing algorithm based on canonical forms

DOI10.1016/j.cor.2012.03.003zbMath1349.90704OpenAlexW1973264127MaRDI QIDQ339635

Takashi Imamichi, Hiroshi Nagamochi, Yohei Arahori

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.03.003

zbMATH Keywords

branch-and-boundcanonical formone-dimensional contiguous bin packing problemtwo-dimensional strip packing problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Logic based Benders' decomposition for orthogonal stock cutting problems ⋮ Combinatorial Benders' Cuts for the Strip Packing Problem ⋮ Mathematical models for the berth allocation problem in dry bulk terminals ⋮ The value of integrating loading and routing ⋮ Order and static stability into the strip packing problem ⋮ Grids for cutting and packing problems: a study in the 2D knapsack problem ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ Upper bounds for heuristic approaches to the strip packing problem

Cites Work

• Unnamed Item
• Unnamed Item
• A squeaky wheel optimisation methodology for two-dimensional strip packing
• Reactive GRASP for the strip-packing problem
• A least wasted first heuristic algorithm for the rectangular packing problem
• A branch and bound algorithm for the strip packing problem
• Exact algorithms for the two-dimensional strip packing problem with and without rotations
• On genetic algorithms for the packing of polygons
• Some experiments with simulated annealing techniques for packing problems
• Local search algorithms for the rectangle packing problem with general spatial costs
• An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
• A review of the application of meta-heuristic algorithms to 2D strip packing problems
• An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles
• Two-dimensional packing problems: a survey
• Exhaustive approaches to 2D rectangular perfect packings
• Improved local search algorithms for the rectangle packing problem with general spatial costs
• A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces
• A new heuristic recursive algorithm for the strip rectangular packing problem
• An improved typology of cutting and packing problems
• Exact Solution of the Two-Dimensional Finite Bin Packing Problem
• An Exact Approach to the Strip-Packing Problem
• A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem
• The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation
• An Improved Heuristic Recursive Strategy Based on Genetic Algorithm for the Strip Rectangular Packing Problem
• Two-Dimensional Finite Bin-Packing Algorithms
• Orthogonal Packings in Two Dimensions
• The Three-Dimensional Bin Packing Problem
• A New Placement Heuristic for the Orthogonal Stock-Cutting Problem
• One-dimensional heuristics adapted for two-dimensional rectangular strip packing
• New heuristic and interactive approaches to 2D rectangular strip packing

This page was built for publication: An exact strip packing algorithm based on canonical forms