Exact Solution of the Two-Dimensional Finite Bin Packing Problem

DOI10.1287/MNSC.44.3.388zbMath0989.90114OpenAlexW2074821977MaRDI QIDQ2783932

Silvano Martello, Daniele Vigo

Publication date: 17 April 2002

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.44.3.388

zbMATH Keywords

branch-and-boundworst-case analysiscutting and packing

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Complexity and performance of numerical algorithms (65Y20)

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

Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem ⋮ An introduction to the two‐dimensional rectangular cutting and packing problem ⋮ Using heuristic algorithms for capacity leasing and task allocation issues in telecommunication networks under fuzzy quality of service constraints ⋮ New Lower Bound and Exact Method for the Continuous Berth Allocation Problem ⋮ Improved filtering for the bin-packing with cardinality constraint ⋮ 2DCPackGen: a problem generator for two-dimensional rectangular cutting and packing problems ⋮ A hybrid heuristic algorithm for the 2D variable-sized bin packing problem ⋮ A block-based layer building approach for the 2D guillotine strip packing problem ⋮ Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem ⋮ A heuristic for solving large bin packing problems in two and three dimensions ⋮ Constrained order packing: comparison of heuristic approaches for a new bin packing problem ⋮ A hybrid algorithm for constrained order packing ⋮ 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 ⋮ Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search ⋮ A guided tabu search for the vehicle routing problem with two-dimensional loading constraints ⋮ A lower bound for the non-oriented two-dimensional bin packing problem ⋮ Provider selection and task allocation in telecommunications with QoS degradation policy ⋮ A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem ⋮ An improved typology of cutting and packing problems ⋮ A GRASP/path relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems ⋮ PackLib\(^{2}\): an integrated library of multi-dimensional packing problems ⋮ A hybrid genetic algorithm for the two-dimensional single large object placement problem ⋮ A new exact method for the two-dimensional orthogonal packing problem ⋮ Models and algorithms for three-stage two-dimensional bin packing ⋮ 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 ⋮ Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts ⋮ An exact strip packing algorithm based on canonical forms ⋮ The load-balanced multi-dimensional bin-packing problem ⋮ Packing into the smallest square: worst-case analysis of lower bounds ⋮ New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation ⋮ A hybrid demon algorithm for the two-dimensional orthogonal strip packing problem ⋮ A three-dimensional bin-packing model: exact multicriteria solution and computational complexity ⋮ Combinatorial Benders' Cuts for the Strip Packing Problem ⋮ Two- and three-dimensional parametric packing ⋮ Single batch machine scheduling with dual setup times for autoclave molding manufacturing ⋮ A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem ⋮ The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview ⋮ Capping methods for the automatic configuration of optimization algorithms ⋮ Space defragmentation for packing problems ⋮ A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing ⋮ Generalized hyper-heuristics for solving 2D regular and irregular packing problems ⋮ Routing problems with loading constraints ⋮ A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints ⋮ The off-line group seat reservation problem ⋮ Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques ⋮ Solving a large cutting problem in the glass manufacturing industry ⋮ Algorithms for nesting with defects ⋮ A squeaky wheel optimisation methodology for two-dimensional strip packing ⋮ An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem ⋮ On solving multiobjective bin packing problems using evolutionary particle swarm optimization ⋮ A skyline heuristic for the 2D rectangular packing and strip packing problems ⋮ A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts ⋮ Metaheuristics for truck loading in the car production industry ⋮ On the two-dimensional knapsack problem ⋮ Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds ⋮ A new constraint programming approach for the orthogonal packing problem ⋮ Packing of one-dimensional bins with contiguous selection of identical items: an exact method of optimal solution ⋮ HEURISTICS WITH STOCHASTIC NEIGHBORHOOD STRUCTURES FOR TWO-DIMENSIONAL BIN PACKING AND CUTTING STOCK PROBLEMS ⋮ Relations between capacity utilization, minimal bin size and bin number ⋮ Reactive GRASP for the strip-packing problem ⋮ Product packing and stacking under uncertainty: a robust approach ⋮ A sequential value correction heuristic for a bi-objective two-dimensional bin-packing ⋮ A new exact method for the two-dimensional bin-packing problem with fixed orientation ⋮ A new lower bound for the non-oriented two-dimensional bin-packing problem ⋮ Ant colony optimization for the two-dimensional loading vehicle routing problem ⋮ New resolution algorithm and pretreatments for the two-dimensional bin-packing problem ⋮ A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint ⋮ Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts ⋮ Recent advances on two-dimensional bin packing problems ⋮ Lower bounds for three-dimensional multiple-bin-size bin packing problems ⋮ A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces ⋮ New lower bounds for bin packing problems with conflicts ⋮ Unnamed Item ⋮ An exact algorithm for the type-constrained and variable sized bin packing problem ⋮ Bidirectional best-fit heuristic for orthogonal rectangular strip packing ⋮ Vehicle routing problems with loading constraints: state-of-the-art and future directions ⋮ The Two Dimensional Bin Packing Problem with Side Constraints ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ Queue-constrained packing: a vehicle ferry case study ⋮ The minimum raster set problem and its application to the \(d\)-dimensional orthogonal packing problem ⋮ Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows ⋮ Partial enumeration algorithms for two-dimensional bin packing problem with guillotine constraints ⋮ An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem ⋮ SLOPPGEN: a problem generator for the two-dimensional rectangular single large object placement problem with defects ⋮ The maximum diversity assortment selection problem ⋮ A model to design recreational boat mooring fields ⋮ Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers ⋮ An agent-based approach to the two-dimensional guillotine bin packing problem ⋮ Approximation algorithm for the oriented two-dimensional bin packing problem ⋮ Bidimensional packing by bilinear programming ⋮ A branch and bound algorithm for the strip packing problem ⋮ One-dimensional relaxations and LP bounds for orthogonal packing ⋮ A hybrid metaheuristic for the two-dimensional strip packing problem ⋮ New lower bounds for the three-dimensional finite bin packing problem ⋮ Local search of orthogonal packings using the lower bounds ⋮ New data-dependent dual-feasible functions and lower bounds for a two-dimensional bin-packing problem ⋮ Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles

Uses Software

• OR-Library

This page was built for publication: Exact Solution of the Two-Dimensional Finite Bin Packing Problem