Exact solution techniques for two-dimensional cutting and packing
From MaRDI portal
Abstract: We survey the main formulations and solution methods for two-dimensional orthogonal cutting and packing problems, where both items and bins are rectangles. We focus on exact methods and relaxations for the four main problems from the literature: finding a packing with minimum height, packing the items into the minimum number of bins, finding a packing of maximum value, and determining the existence of a feasible packing.
Recommendations
- Exact solution of the two-dimensional finite bin packing problem
- Two-dimensional packing problems: a survey
- A new exact method for the two-dimensional orthogonal packing problem
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- An exact algorithm for general, orthogonal, two-dimensional knapsack problems
Cites work
- scientific article; zbMATH DE number 4074379 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 719668 (Why is no real title available?)
- scientific article; zbMATH DE number 2050771 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- 2DCPackGen: a problem generator for two-dimensional rectangular cutting and packing problems
- A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
- A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem
- A New Linear Programming Approach to the Cutting Stock Problem
- A New Placement Heuristic for the Orthogonal Stock-Cutting Problem
- A SAT encoding for multi-dimensional packing problems
- A SAT-based method for solving the two-dimensional strip packing problem
- A Tabu search heuristic for the vehicle routing problem with two‐dimensional loading constraints
- A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem
- A branch and bound algorithm for the strip packing problem
- A branch-and-cut algorithm for the pallet loading problem
- A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
- A branch-and-price algorithm for the two-dimensional level strip packing problem
- A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size
- A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
- A general framework for bounds for higher-dimensional orthogonal packing problems.
- A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
- A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing
- A hybrid evolutionary algorithm for the two-dimensional packing problem
- A hybrid genetic algorithm for the two-dimensional single large object placement problem
- A new constraint programming approach for the orthogonal packing problem
- A new exact method for the two-dimensional orthogonal packing problem
- A new lower bound for online strip packing
- A new upper bound for the online square packing problem in a strip
- A set-covering-based heuristic approach for bin-packing problems
- A skyline heuristic for the 2D rectangular packing and strip packing problems
- A squeaky wheel optimisation methodology for two-dimensional strip packing
- A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem
- A survey of dual-feasible and superadditive functions
- A tabu search algorithm for a two-dimensional non-guillotine cutting problem
- A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems
- A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
- A tutorial in irregular shape packing problems
- A typology of cutting and packing problems
- Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
- Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
- An Algorithm for Two-Dimensional Cutting Problems
- An Exact Algorithm for Higher-Dimensional Orthogonal Packing
- An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
- An analytical model for the container loading problem
- An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem
- An enumeration scheme to generate constrained exact checkerboard patterns
- An exact algorithm for general, orthogonal, two-dimensional knapsack problems
- An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
- 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
- An exact algorithm for the two-dimensional strip-packing problem
- An exact approach to the strip-packing problem
- An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems
- An exact strip packing algorithm based on canonical forms
- An improved typology of cutting and packing problems
- An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock
- An integer programming model for two- and three-stage two-dimensional cutting stock problems
- Approximate strip packing: revisited
- Approximation and online algorithms for multidimensional bin packing: a survey
- Arc-flow model for the two-dimensional guillotine cutting stock problem
- Automatic layouting of personalized newspaper pages
- BPPLIB: a library for bin packing and cutting stock problems
- Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems
- Bidimensional packing by bilinear programming
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Characterization and modelling of guillotine constraints
- Checkerboard pattern: proposals for its generation
- Classification and literature review of integrated lot-sizing and cutting stock problems
- Closing the Gap for Pseudo-Polynomial Strip Packing
- Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
- Combinatorial Benders' cuts for the strip packing problem
- Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem
- Consecutive ones matrices for multi-dimensional orthogonal packing problems
- Conservative scales in packing problems
- Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization
- Constraints in container loading -- a state-of-the-art review
- Discrete-variable extremum problems
- Dual-Optimal Inequalities for Stabilized Column Generation
- Dual-feasible functions for integer programming and combinatorial optimization. Basics, extensions and applications
- Exact algorithms for the two-dimensional guillotine knapsack
- Exact algorithms for the two-dimensional strip packing problem with and without rotations
- Exact solution of bin-packing problems using column generation and branch-and-bound
- Exact solution of the two-dimensional finite bin packing problem
- Exhaustive approaches to 2D rectangular perfect packings
- Generalized Benders decomposition
- Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems
- Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns
- Improved state space relaxation for constrained two-dimensional guillotine cutting problems
- Integer linear programming models for 2-staged two-dimensional knapsack problems
- Introduction to cutting and packing optimization. Problems, modeling approaches, solution methods
- Irregular packing problems: a review of mathematical models
- LP bounds in an interval-graph algorithm for orthogonal-packing feasibility
- LP bounds in various constraint programming approaches for orthogonal packing
- LP models for bin packing and cutting stock problems
- Logic based Benders' decomposition for orthogonal stock cutting problems
- Logic-based Benders decomposition
- Lower bounds and reduction procedures for the bin packing problem
- MPQ-trees for orthogonal packing problem
- Modeling two-dimensional guillotine cutting problems via integer programming
- Models and algorithms for packing rectangles into the smallest square
- Models and algorithms for three-stage two-dimensional bin packing
- Models and bounds for two-dimensional level packing problems
- Models for the two-dimensional two-stage cutting stock problem with multiple stock size
- Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern
- Multistage Cutting Stock Problems of Two and More Dimensions
- New classes of fast lower bounds for bin packing problems
- New lower bound and exact method for the continuous berth allocation problem
- New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation
- New upper bounds for online strip packing
- New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem
- On genetic algorithms for the packing of polygons
- On the extremality of maximal dual feasible functions
- On the two-dimensional knapsack problem
- One-dimensional relaxations and LP bounds for orthogonal packing
- Optimal Scheduling of Tasks on Identical Parallel Processors
- Optimal rectangle packing
- Order and static stability into the strip packing problem
- Orthogonal Packings in Two Dimensions
- Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution
- Partitioning procedures for solving mixed-variables programming problems
- Reactive GRASP for the strip-packing problem
- Recent advances on two-dimensional bin packing problems
- Recursive Computational Procedure for Two-dimensional Stock Cutting
- Review: An annotated bibliography of combined routing and loading problems
- Routing problems with loading constraints
- Scheduling inspired models for two-dimensional packing problems
- Solution approaches to irregular nesting problems
- Staged and constrained two-dimensional guillotine cutting problems: an AND/OR-graph approach
- State-space relaxation procedures for the computation of bounds to routing problems
- TSpack: A unified tabu search code for multi-dimensional bin packing problems
- The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation
- The Meet-in-the-Middle Principle for Cutting and Packing Problems
- The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio
- The geometry of nesting problems: a tutorial
- The pallet loading problem: a review of solution methods and computational experiments
- The two-dimensional bin packing problem with variable bin sizes and costs
- The two-dimensional finite bin packing problem. I: New lower bounds for the oriented case
- The two-dimensional finite bin packing problem. II: New lower and upper bounds
- Theoretical investigations on maximal dual feasible functions
- Triple-solution approach for the strip packing problem with two-staged patterns
- Two-Dimensional Finite Bin-Packing Algorithms
- Two-dimensional bin packing problems
- Two-dimensional packing problems: a survey
- Using Contiguous 2D-Feasible 1D Cutting Patterns for the 2D Strip Packing Problem
- Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
- Using extra dual cuts to accelerate column generation
- Variable Sized Bin Packing
- Vehicle routing problems with loading constraints: state-of-the-art and future directions
Cited in
(68)- Mathematical models and heuristic algorithms for pallet building problems with practical constraints
- Cutting and packing problems with placement constraints
- A survey on the cutting and packing problems
- Conservative scales in packing problems
- An introduction to the two‐dimensional rectangular cutting and packing problem
- Improved dynamic programming algorithms for unconstrained two-dimensional guillotine cutting
- Solving the three-dimensional open-dimension rectangular packing problem: a constraint programming model
- Logic based Benders' decomposition for orthogonal stock cutting problems
- Strip based compact formulation for two-dimensional guillotine cutting problems
- Exact methods for three-dimensional cutting and packing: a comparative study concerning single container problems
- Solving the parallel processor scheduling and bin packing problems with contiguity constraints: mathematical models and computational studies
- 2DPackLib: a two-dimensional cutting and packing library
- Mathematical optimisation in the honeycomb cardboard industry: a model for the two-dimensional variable-sized cutting stock problem
- Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
- Exact approaches for the unconstrained two-dimensional cutting problem with defects
- Grids for cutting and packing problems: a study in the 2D knapsack problem
- Solving the two-dimensional packing problem with m-M calculus
- A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints
- L. V. Kantorovich and cutting-packing problems: new approaches for solving combinatorial problems of linear cutting and rectangular packing
- On the optimal layout of a dining room in the era of COVID‐19 using mathematical optimization
- Knapsack problems -- an overview of recent advances. I: Single knapsack problems
- A new upper bound for unconstrained two-dimensional cutting and packing
- Rectangle packing with a recursive pilot method
- Lower and upper bounding procedures for the bin packing problem with concave loading cost
- Mixed-integer and constraint programming models for the two-dimensional guillotine cutting problem
- Mixed-integer linear programming models for 3D irregular strip packing problems
- Branch-and-repair for the stochastic three-dimensional bin selection problem: a multi-stage stochastic programming application
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Bin packing and related problems: general arc-flow formulation with graph compression
- Solving a large-scale 3D packing problem with robot constraints
- The two-dimensional orthogonal packing problem with item fragmentation: formulation and local search-based algorithms (applications on tank-farm layout planning)
- The maximum diversity assortment selection problem
- Models for two-dimensional bin packing problems with customer order spread
- A new search procedure for the two-dimensional orthogonal packing problem
- An improved typology of cutting and packing problems
- Scheduling inspired models for two-dimensional packing problems
- Two-dimensional packing problems: a survey
- Exact solutions for constrained two-dimensional cutting problems
- Packing by scheduling: using constraint programming to solve a complex 2D cutting stock 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
- Cutting and packing optimization. Problems modeling and solution methods.
- Exact algorithms for energy-constrained scheduling on identical parallel machines
- A new exact method for the two-dimensional bin-packing problem with fixed orientation
- Mixed-Integer programming models for irregular strip packing based on vertical slices and feasibility cuts
- Bidimensional packing by bilinear programming
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- 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
- A cutting plane method and a parallel algorithm for packing rectangles in a circular container
- Learning-based branch-and-price algorithms for the vehicle routing problem with time windows and two-dimensional loading constraints
- Two-dimensional bin packing, cutting stock, and open dimension problems: a survey of practical requirements
- On the multiple optimal solutions and patterns of the pallet loading problem
- An effective evolutionary algorithm for packing rectangles into a fixed size circular container
- Theoretical analysis of integer programming models for the two-dimensional two-staged knapsack problem
- An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints
- A polynomial mixed-integer linear programming model for two-dimensional guillotine strip packing problem
- Integer linear programming formulations and heuristic solution approaches for busy time minimization in temporal bin packing
- Cutting and packing problems under uncertainty: literature review and classification framework
- Using Contiguous 2D-Feasible 1D Cutting Patterns for the 2D Strip Packing Problem
- Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry
- Cargo securing under multi-drop and axle weight constraints
- Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups
- Exact solution of the two-dimensional finite bin packing problem
- A new exact method for the two-dimensional orthogonal packing problem
- Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem
- Enhanced formulation for the Guillotine 2D Cutting knapsack problem
- A new branch-and-cut approach for integrated planning in additive manufacturing
- scientific article; zbMATH DE number 1183280 (Why is no real title available?)
This page was built for publication: Exact solution techniques for two-dimensional cutting and packing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029021)
