Bin packing and related problems: general arc-flow formulation with graph compression
From MaRDI portal
Abstract: We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems --- including multi-constraint variants --- by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model. As opposed to our method, which provides strong models, conventional models are usually highly symmetric and provide very weak lower bounds. Our formulation is equivalent to Gilmore and Gomory's, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern. The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, graph coloring, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, cutting stock with binary patterns, bin packing with conflicts, and cutting stock with binary patterns and forbidden pairs. We report computational results obtained with many benchmark test data sets, all of them showing a large advantage of this formulation with respect to the traditional ones.
Recommendations
- Exact solution of bin-packing problems using column generation and branch-and-bound
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- Solving bin packing problems using VRPSolver models
- LP models for bin packing and cutting stock problems
- Exact solution techniques for two-dimensional cutting and packing
Cites work
- A Linear Programming Approach to the Cutting-Stock Problem
- Algorithm 457: finding all cliques of an undirected graph
- Algorithms for the bin packing problem with conflicts
- An improved typology of cutting and packing problems
- BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem
- CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem
- Exact solution of bin-packing problems using column generation and branch-and-bound
- Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems
- Heuristics for the integer one-dimensional cutting stock problem: A computational study
- scientific article; zbMATH DE number 3573595 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved results for a memory allocation problem
- Integer Rounding for Polymatroid and Branching Optimization Problems
- Lower bounds and algorithms for the 2-dimensional vector packing problem
- LP models for bin packing and cutting stock problems
- Network flows. Theory, algorithms, and applications.
- The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
Cited in
(52)- Exact solution of bin-packing problems using column generation and branch-and-bound
- Improved filtering for the bin-packing with cardinality constraint
- The skiving stock problem and its relation to hypergraph matchings
- BPPLIB: a library for bin packing and cutting stock problems
- A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
- Mathematical models and decomposition methods for the multiple knapsack problem
- Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation
- Bin packing problem with conflicts and item fragmentation
- Multi-warehouse package consolidation for split orders in online retailing
- Solving bin packing problems using VRPSolver models
- On the benchmark instances for the bin packing problem with conflicts
- Packing-based branch-and-bound for discrete malleable task scheduling
- An introduction to stochastic bin packing-based server consolidation with conflicts
- An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem
- A generic exact solver for vehicle routing and related problems
- Arc flow formulations based on dynamic programming: theoretical foundations and applications
- A branch-and-price algorithm for the two-dimensional vector packing problem
- Improved flow-based formulations for the skiving stock problem
- A branch-and-price algorithm for the temporal bin packing problem
- A Bayesian Monte Carlo method for computing the Shapley value: application to weighted voting and bin packing games
- Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
- Multi-period bin packing model and effective constructive heuristics for corridor-based logistics capacity planning
- Arc-flow approach for single batch-processing machine scheduling
- An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs
- Prospective network flow models and algorithms for bin packing problems
- Bin packing and cutting stock problems: mathematical models and exact algorithms
- A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems
- Vector bin packing with heterogeneous bins: application to the machine reassignment problem
- Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation
- The proper relaxation and the proper gap of the skiving stock problem
- The Meet-in-the-Middle Principle for Cutting and Packing Problems
- Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
- Analysis of the simple assembly line balancing problem complexity
- An introduction to the two‐dimensional rectangular cutting and packing problem
- Lower and upper bounding procedures for the bin packing problem with concave loading cost
- Hybrid branch-and-price-and-cut algorithm for the two-dimensional vector packing problem with time windows
- Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model
- A large neighborhood search algorithm and lower bounds for the variable-sized bin packing problem with conflicts
- Algorithms for the bin packing problem with scenarios
- Price-and-branch heuristic for vector bin packing
- Efficient arc-flow formulations for makespan minimisation on parallel machines with a common server
- Arc-flow formulation and branch-and-price-and-cut algorithm for the bin-packing problem with fragile objects
- Classification and evaluation of the algorithms for vector bin packing
- Last fifty years of integer linear programming: a focus on recent practical advances
- Solving the parallel processor scheduling and bin packing problems with contiguity constraints: mathematical models and computational studies
- Mathematical models based on decision hypergraphs for designing a storage cabinet
- Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation
- Fast neighborhood search heuristics for the colored bin packing problem
- Bin packing with thresholds: mathematical models and theoretical results
- Stabilized branch-and-price algorithms for vector packing problems
- Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems
- Integer linear programming formulations and heuristic solution approaches for busy time minimization in temporal bin packing
This page was built for publication: Bin packing and related problems: general arc-flow formulation with graph compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342316)
