Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

No abstract is available for this paper.

• Publication year

  2008

• Venue

  European Journal of Operational Research

• Publication date

  2008-11-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.ejor.2007.08.007
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An improved typology of cutting and packing problems

  2007influential reference
• Models and algorithms for three-stage two-dimensional bin packing

  2007cited by this paper
• A note on the approximability of cutting stock problems

  2007cited by this paper
• An Exact Algorithm for Higher-Dimensional Orthogonal Packing

  2006influential reference
• A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

  2006cited by this paper
• On strip packing With rotations

  2005cited by this paper
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing

  2005cited by this paper
• The two-dimensional cutting stock problem revisited

  2005cited by this paper
• Dynamic Programming and Column Generation Based Approaches for Two-Dimensional Guillotine Cutting Problems

  2004cited by this paper
• Packing Problems with Orthogonal Rotations

  2004influential reference
• On the two-dimensional Knapsack Problem

  2004influential reference
• On rectangle packing: maximizing benefits

  2004influential reference
• Models and Bounds for Two-Dimensional Level Packing Problems

  2004cited by this paper
• An Evolutionary Algorithm for Column Generation in Integer Programming: An Effective Approach for 2D Bin Packing

  2004cited by this paper
• The Rectangular Packing Problem: Local Optimum Search Methods Based on Block Structures

  2004cited by this paper
• Integer linear programming models for 2-staged two-dimensional Knapsack problems

  2003cited by this paper
• An Exact Approach to the Strip-Packing Problem

  2003cited by this paper
• Two Dimensional Packing: The Power of Rotation

  2003influential reference
• Packing 2-dimensional bins in harmony

  2002influential reference
• A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems

  2002cited by this paper
• An Approximation Scheme for the Two-Stage, Two-Dimensional Bin Packing Problem

  2002cited by this paper
• A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem

  2001cited by this paper
• Constrained two‐dimensional cutting stock problems a best‐first branch‐and‐bound algorithm

  2000cited by this paper
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem

  2000cited by this paper
• Exact algorithms for the guillotine strip cutting/packing problem

  1998cited by this paper
• The solution of two-stage guillotine cutting stock problems having extremely varying order demands

  1996cited by this paper
• Heuristics for the integer one-dimensional cutting stock problem: A computational study

  1996cited by this paper
• An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems

  1995cited by this paper
• An and—or-graph approach for two-dimensional cutting problems

  1992cited by this paper
• An improved version of Wang's algorithm for two-dimensional cutting problems

  1990cited by this paper
• OR-Library: Distributing Test Problems by Electronic Mail

  1990cited by this paper
• A probabilistic analysis of the simplex method

  1986cited by this paper
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure

  1985cited by this paper
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting

  1985influential reference
• New results on the average behavior of simplex algorithms

  1984cited by this paper
• On Packing Two-Dimensional Bins

  1982cited by this paper
• A 5/4 Algorithm for Two-Dimensional Packing

  1981cited by this paper
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms

  1980cited by this paper
• An Algorithm for Two-Dimensional Cutting Problems

  1977influential reference
• Recursive computational procedure for two-dimensional stock cutting

  1972cited by this paper
• Multistage Cutting Stock Problems of Two and More Dimensions

  1965cited by this paper
• A Linear Programming Approach to the Cutting Stock Problem---Part II

  1963influential reference
• A Linear Programming Approach to the Cutting-Stock Problem

  1961influential reference
• Als Manuskript Gedruckt Technische Universität Dresden Herausgeber: Der Rektor Models with Variable Strip Widths for Two-dimensional Two-stage Cutting

  year unknowncited by this paper

• Lexicographic column generation with a tree search pricing algorithm

  2026cites this paper
• Deep reinforcement learning-based column generation for the two-dimensional vector variable-sized packing problem

  2025cites this paper
• A Robust Optimization Approach for the Multi-Period Strip Cutting Problem with Multi-Cutter Slitting Machines

  2025cites this paper
• Two-dimensional cutting stock problem with flexible length and usable leftovers in the steel industry

  2025cites this paper
• An improved column generation algorithm for a two dimensional variable-size bin packing optimization problem with time windows

  2025cites this paper
• EATKG: An Open-Source Efficient Exact Algorithm for the Two-Dimensional Knapsack Problem with Guillotine Constraints

  2025cites this paper
• Column generation approach for 1.5-dimensional cutting stock problem with technical constraints

  2024cites this paper
• Optimisation of Categorical Choices in Exploration Mission Concepts of Operations Using Column Generation Method

  2024cites this paper
• Two-Level Approach for Simultaneous Component Assignment and Layout Optimization with Applications to Spacecraft Optimal Layout

  2024cites this paper
• A bay design problem in less-than-unit-load production warehouse

  2024cites this paper
• Energy-efficient scheduling in an identical parallel machine environment with peak power consumption and deadline constraints

  2024cites this paper
• A Genetic Algorithm with Lower Neighborhood Search for the Three-Dimensional Multiorder Open-Size Rectangular Packing Problem

  2024cites this paper
• Boosted Arc Flow Formulation Using Graph Compression for the Two-Dimensional Strip Cutting Problem

  2023cites this paper
• A 2-dimensional guillotine cutting stock problem with variable-sized stock for the honeycomb cardboard industry

  2023cites this paper
• The two-dimensional cutting stock problem with usable leftovers and uncertainty in demand

  2023cites this paper
• The integrated lot-sizing and cutting stock problem under demand uncertainty

  2022influential citation
• Lexicographic Branch-and-Bound Column Search

  2022cites this paper
• Pattern Generation for Three Dimensional Cutting Stock Problem

  2022cites this paper
• An introduction to the two-dimensional rectangular cutting and packing problem

  2022cites this paper
• A cutting plane method and a parallel algorithm for packing rectangles in a circular container

  2022cites this paper
• Application of Metaheuristics to Packing Formation Support Systems of Pre-Cut Lumber Factory

  2022cites this paper
• The Floating-Cuts model: a general and flexible mixed-integer programming model for non-guillotine and guillotine rectangular cutting problems

  2022cites this paper
• The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches

  2022cites this paper
• Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry

  2022cites this paper
• Framework of algorithm portfolios for strip packing problem

  2022cites this paper
• Strip based compact formulation for two-dimensional guillotine cutting problems

  2022cites this paper
• A Heuristic Approach for Two-Dimensional Rectangular Cutting Stock Problem considering Balance for Material Utilization and Cutting Complexity

  2021cites this paper
• Integer Linear Programming Formulations for the RCPSP considering Multi-Skill, Multi-Mode, and Minimum and Maximum Time Lags

  2021cites this paper
• A heuristic for the problem of one-dimensional steel coil cutting

  2021cites this paper
• Queue-constrained packing: A vehicle ferry case study

  2021cites this paper
• Implementasi metode Greedy Randomized Adaptive Search Procedure dan model Dotted Board pada Cutting Stock Problem Bentuk Reguler

  2021cites this paper
• A Branch-and-Cut and a Parallel Algorithm for Packing Two-Dimensional Rectangles in a Circular Container

  2021cites this paper
• An Approach Based on Demand Prediction with LSTM for Solving Multi-batch 2D Cutting Stock Problems

  2021cites this paper
• Optimising airline maintenance scheduling decisions

  2020cites this paper
• Uma revisão sobre o uso da programação dinâmica na solução do problema de corte

  2020influential citation
• Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm

  2020cites this paper
• Column generation algorithms for mother plate design in steel plants

  2020cites this paper
• Exact solution techniques for two-dimensional cutting and packing

  2020cites this paper
• Column generation algorithms for mother plate design in steel plants

  2020cites this paper
• An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem

  2020cites this paper
• An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem

  2020influential citation
• An Efficient Algorithm to Produce Sponge Packing Particles

  2020cites this paper
• A MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts

  2019cites this paper
• Optimizing the placement of irregular shapes 2D Nesting

  2019cites this paper
• Deterministic model for customized pilot manufacture production with various backplane sizes

  2019cites this paper
• The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation, a Benders decomposition and a CP-based algorithm

  2019cites this paper
• Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem

  2019cites this paper
• Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers

  2019cites this paper
• Efficient Heuristics for Two-Dimensional Cutting and Packing Problems

  2019cites this paper
• Improved state space relaxation for constrained two-dimensional guillotine cutting problems

  2019cites this paper
• Primal Heuristics for Branch and Price: The Assets of Diving Methods

  2019cites this paper
• Grids for cutting and packing problems: a study in the 2D knapsack problem

  2019cites this paper
• Models for the two-dimensional level strip packing problem – a review and a computational evaluation

  2019cites this paper
• Contributions to the two-dimensional guillotine cutting stock problem

  2018cites this paper
• Optimal Guillotine Cutting

  2018cites this paper
• A Practical Application of the Generalized Cutting Stock Algorithm

  2018cites this paper
• Solving the two-dimensional knapsack problem considering cutting-time and emission of particulate matter in the metalworking industry

  2018influential citation
• A Two-Phase Optimization Approach for Reducing the Size of the Cutting Problem in the Box-Production Industry: A Case Study

  2018cites this paper
• 2D Optimal Cutting Problem

  2018cites this paper
• Subtraction of Two 2D Polygons with Some Matching Vertices

  2018cites this paper
• A general heuristic for two-dimensional nesting problems with limited-size containers

  2018cites this paper
• ONE-DIMENSIONAL CUTTING STOCK OPTIMIZATION : A CASE OF CZECH DISTRIBUTION COMPANY

  2018cites this paper
• A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem

  2018cites this paper
• A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem

  2018cites this paper
• Novel Methods Generated by Genetic Programming for the Guillotine-Cutting Problem

  2018cites this paper
• Minimizing loss in LCD glass manufacturing by cutting pattern optimization based on integer programming

  2017cites this paper
• Analyses and Boolean Operation of 2D Polygons

  2017cites this paper
• Heuristic and Exact Algorithms for the 2 D Knapsack Problem with Relations Between Items

  2017cites this paper
• A column generation-based algorithm for two-stage, two-dimensional bin packing problem with a variant variable sized constraint

  2017cites this paper
• Triple-solution approach for the strip packing problem with two-staged patterns

  2017cites this paper
• Heuristic Algorithm for 2D Cutting Stock Problem

  2017cites this paper
• Avances en investigación de operaciones y ciencias administrativas

  2017cites this paper
• A New Linear Programming Approach for TDGCS Layout Problem

  2017cites this paper
• Solving 2D strip packing problem using fruit fly optimization algorithm

  2017cites this paper
• A COLUMN GENERATION TECHNIQUE WITH MULTIPLE SUB-PROBLEMS FOR 2-DIMENSIONAL CUTTING STOCK PROBLEM

  2017influential citation
• Optimization of the Production Planning and Supplier-Material Selection Problems in Carton Box Production Industries

  2017cites this paper
• Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem

  2016influential citation
• Column Generation at Strip Level for the k-Staged Two-Dimensional Cutting Stock Problem

  2016cites this paper
• Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns

  2016cites this paper
• A Branch-and-Bound Approach for the Constrained k-Staged 2-Dimensional Cutting Stock Problem

  2016cites this paper
• Two-stage two-dimensional guillotine cutting stock problems with usable leftover

  2016cites this paper
• Two Dimensional Knapsack problem using industrial Robots

  2016cites this paper
• Triple-solution approach for the strip packing problem with two-staged patterns

  2016influential citation
• Crowdsourcing solutions to 2D irregular strip packing problems from Internet workers

  2016cites this paper
• A Scalable Approach for the K-Staged Two-Dimensional Cutting Stock Problem with Variable Sheet Size

  2015cites this paper
• An arc flow-based optimization approach for the two-stage guillotine strip cutting problem

  2015cites this paper
• Cutting and Packing Problems with Placement Constraints

  2015cites this paper
• Width-Packing Heuristic for Grouping in Two-Dimensional Irregular Shapes Cutting Stock Problem

  2015cites this paper
• An exact algorithm for the N-sheet two dimensional single stock-size cutting stock problem

  2015cites this paper
• On the $$L$$L-approach for generating unconstrained two-dimensional non-guillotine cutting patterns

  2015influential citation
• A linear approximation algorithm for the BPP with the best possible absolute approximation ratio

  2015cites this paper
• A Scalable Approach for the K-Staged Two-Dimensional Cutting Stock Problem

  2015cites this paper
• A new heuristic algorithm for two-dimensional defective stock guillotine cutting stock problem with multiple stock sizes

  2015cites this paper
• Solving the 3-Staged 2-Dimensional Cutting Stock Problem by Dynamic Programming and Variable Neighborhood Search

  2015cites this paper
• A Value-Correction Construction Heuristic for the Two-Dimensional Cutting Stock Problem with Variable Sheet Size

  2015cites this paper
• Width-Packing Heuristic for Grouping in Two-Dimensional Irregular Shapes Cutting Stock Problem

  2015cites this paper
• Approaches to real world two-dimensional cutting problems

  2014cites this paper
• A Variable Neighborhood Search Using Very Large Neighborhood Structures for the 3-Staged 2-Dimensional Cutting Stock Problem

  2014cites this paper
• A Hybrid Heuristic Based on Column Generation for Two- and Three- Stage Bin Packing Problems

  2014cites this paper
• A note on “Reducing the number of binary variables in cutting stock problems”

  2014cites this paper