Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems

Maxence Delorme
Corresponding Author
Maxence Delorme
http://orcid.org/0000-0003-3730-0894
School of Mathematics, The University of Edinburgh, Edinburgh EH9 3JZ, United Kingdom;
Search for more papers by this author
,
Manuel Iori
Manuel Iori
http://orcid.org/0000-0003-2097-6572
Dipartimento di Scienze e Metodi dell'Ingegneria (DISMI), Università di Modena e Reggio Emilia, 42122 Reggio Emilia, Italy
Search for more papers by this author

Maxence Delorme

Corresponding Author

Maxence Delorme

http://orcid.org/0000-0003-3730-0894

School of Mathematics, The University of Edinburgh, Edinburgh EH9 3JZ, United Kingdom;

Search for more papers by this author

Manuel Iori

http://orcid.org/0000-0003-2097-6572

Dipartimento di Scienze e Metodi dell'Ingegneria (DISMI), Università di Modena e Reggio Emilia, 42122 Reggio Emilia, Italy

Search for more papers by this author

Published Online:18 Jul 2019https://doi.org/10.1287/ijoc.2018.0880

Supplemental Material

ijoc.2018.0880.sm1.pdf

Cited by
- Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems
  European Journal of Operational Research, Vol. 334, No. 1
- Exact approaches for the pattern minimization problem
  Computers & Industrial Engineering, Vol. 217
- Bin packing with thresholds: mathematical models and theoretical results
  European Journal of Operational Research, Vol. 331, No. 3
- Integer linear programming formulations and heuristic solution approaches for busy time minimization in temporal bin packing
  9 November 2025 | 4OR, Vol. 24, No. 2
- QBD and QBDRL: 3D Bin Packing Novel Approaches for Virtual Machine Placement using Reinforcement Learning for Energy Optimization in Cloud Computing Infrastructures
  15 April 2026 | Journal of Grid Computing, Vol. 24, No. 2
- Pseudo-Polynomial Formulations for the Bin Packing Problem with Minimum Color Fragmentation
  Mathijs Barkel,
  Maxence Delorme,
  Enrico Malaguti,
  Michele Monaci
  19 August 2025 | INFORMS Journal on Computing, Vol. 38, No. 3
- On formulations for the one-dimensional cutting stock with a limited number of open stacks problem
  6 October 2025 | International Journal of Production Research, Vol. 64, No. 4
- The overflowing bin packing problem: theoretical results and compact ILP formulations
  24 February 2026 | Mathematical Methods of Operations Research, Vol. 102, No. 2-3
- Solving Cutting Stock Problems via an Extended Ryan-Foster Branching Scheme and Fast Column Generation
  Renan F. F. da Silva,
  Rafael C. S. Schouery
  23 October 2025 | INFORMS Journal on Computing, Vol. 0, No. 0
- Mathematical formulations for the robust bin packing problem with fragile objects
  24 September 2025 | Optimization Letters, Vol. 10
- Last fifty years of integer linear programming: A focus on recent practical advances
  European Journal of Operational Research, Vol. 324, No. 3
- Integrated cutting stock and multi-period inventory optimization considering raw material–product eligibility for steel-pipe manufacturers
  Applied Mathematical Modelling, Vol. 142
- Solving the parallel processor scheduling and bin packing problems with contiguity constraints: Mathematical models and computational studies
  European Journal of Operational Research, Vol. 323, No. 3
- Mathematical models for the one-dimensional cutting stock problem with setups and open stacks
  5 April 2025 | Journal of Combinatorial Optimization, Vol. 49, No. 3
- A local branching-based solution for the multi-period cutting stock problem with tardiness, earliness, and setup costs
  4 February 2025 | Journal of Heuristics, Vol. 31, No. 1
- Novel mathematical formulations for parallel-batching processing machine scheduling problems
  Computers & Operations Research, Vol. 173
- Arc-flow formulation and branch-and-price-and-cut algorithm for the bin-packing problem with fragile objects
  Computers & Operations Research, Vol. 173
- Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation
  European Journal of Operational Research, Vol. 320, No. 1
- Fast neighborhood search heuristics for the colored bin packing problem
  17 October 2024 | Annals of Operations Research, Vol. 343, No. 1
- Algorithms for the bin packing problem with scenarios
  24 October 2024 | Journal of Combinatorial Optimization, Vol. 48, No. 4
- New Algorithms for Hierarchical Optimization in Kidney Exchange Programs
  Maxence Delorme,
  Sergio García,
  Jacek Gondzio,
  Jörg Kalcsics,
  David Manlove,
  William Pettersson
  25 January 2023 | Operations Research, Vol. 72, No. 4
- A Branch-and-Cut-and-Price Algorithm for Cutting Stock and Related Problems
  28 June 2024 | Revista Eletrônica de Iniciação Científica em Computação, Vol. 22, No. 1
- Mathematical models and exact algorithms for the Colored Bin Packing Problem
  Computers & Operations Research, Vol. 164
- Tool switching problems with tool order constraints
  Discrete Applied Mathematics, Vol. 347
- Heuristic algorithms based on column generation for an online product shipping problem
  Computers & Operations Research, Vol. 161
- Lower and upper bounding procedures for the bin packing problem with concave loading cost
  European Journal of Operational Research, Vol. 312, No. 1
- Solving a real-world large-scale cutting stock problem: A clustering-assignment-based model
  31 October 2022 | IISE Transactions, Vol. 55, No. 11
- An adaptive large neighborhood search metaheuristic for the Generalized Bin Packing problem with incompatible categories
  Computers & Industrial Engineering, Vol. 185
- The transportation problem with packing constraints
  Computers & Operations Research, Vol. 157
- A large neighborhood search algorithm and lower bounds for the variable-Sized bin packing problem with conflicts
  European Journal of Operational Research, Vol. 308, No. 3
- Solving the skiving stock problem by a combination of stabilized column generation and the Reflect Arc-Flow model
  Discrete Applied Mathematics, Vol. 334
- Mathematical models for the cutting stock with limited open stacks problem
  1 August 2023 | RAIRO - Operations Research, Vol. 57, No. 4
- A combinatorial flow-based formulation for temporal bin packing problems
  European Journal of Operational Research, Vol. 307, No. 2
- Half-cycle: A new formulation for modelling kidney exchange problems
  Operations Research Letters, Vol. 51, No. 3
- Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem
  Mathijs Barkel,
  Maxence Delorme
  10 March 2023 | INFORMS Journal on Computing, Vol. 35, No. 2
- Exact solution of network flow models with strong relaxations
  7 March 2022 | Mathematical Programming, Vol. 197, No. 2
- Arc-flow formulations for the one-dimensional cutting stock problem with multiple manufacturing modes
  8 February 2023 | RAIRO - Operations Research, Vol. 57, No. 1
- A method for demand-accurate one-dimensional cutting problems with pattern reduction
  Mathematical Biosciences and Engineering, Vol. 20, No. 4
- Enhanced formulation for the Guillotine 2D Cutting Knapsack Problem
  12 July 2022 | Mathematical Programming Computation, Vol. 14, No. 4
- A Branch-and-Price Algorithm for the Multiple Knapsack Problem
  Olivier Lalonde,
  Jean-François Côté,
  Bernard Gendron
  23 August 2022 | INFORMS Journal on Computing, Vol. 34, No. 6
- Computational Performance Evaluation of Column Generation and Generate-and-Solve Techniques for the One-Dimensional Cutting Stock Problem
  25 October 2022 | Algorithms, Vol. 15, No. 11
- Bin Packing Problem with Time Lags
  Orlando Rivera Letelier,
  François Clautiaux,
  Ruslan Sadykov
  16 March 2022 | INFORMS Journal on Computing, Vol. 34, No. 4
- An introduction to stochastic bin packing-based server consolidation with conflicts
  19 August 2021 | TOP, Vol. 30, No. 2
- Bin packing with lexicographic objectives for loading weight- and volume-constrained trucks in a direct-shipping system
  17 July 2021 | OR Spectrum, Vol. 44, No. 2
- A residual recombination heuristic for one-dimensional cutting stock problems
  14 June 2021 | TOP, Vol. 30, No. 1
- Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation
  Saharnaz Mehrani,
  Carlos Cardonha,
  David Bergman
  17 December 2021 | INFORMS Journal on Computing, Vol. 34, No. 2
- A note on the integrality gap of cutting and skiving stock instances
  23 December 2020 | 4OR, Vol. 20, No. 1
- Variable-sized bin packing problem with conflicts and item fragmentation
  Computers & Industrial Engineering, Vol. 163
- Arc flow formulations based on dynamic programming: Theoretical foundations and applications
  European Journal of Operational Research, Vol. 296, No. 1
- Relay Logistics: A Multi-Variable Generation Approach
  SSRN Electronic Journal, Vol. 53
- Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events
  European Journal of Operational Research, Vol. 295, No. 3
- Mathematical models and approximate solution approaches for the stochastic bin packing problem
  Computers & Operations Research, Vol. 135
- Compact integer linear programming formulations for the temporal bin packing problem with fire-ups
  Computers & Operations Research, Vol. 132
- Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
  Jean-François Côté,
  Mohamed Haouari,
  Manuel Iori
  25 January 2021 | INFORMS Journal on Computing, Vol. 33, No. 3
- Solving Bin Packing Problems Using VRPSolver Models
  8 April 2021 | Operations Research Forum, Vol. 2, No. 2
- The vehicle routing problem with heterogeneous locker boxes
  15 January 2021 | Central European Journal of Operations Research, Vol. 29, No. 1
- Bin Packing Problem with Conflicts and Item Fragmentation
  Computers & Operations Research, Vol. 126
- New Exact Techniques Applied to a Class of Network Flow Formulations
  5 May 2021
- A Mixed-Integer Linear Programming Model for the Cutting Stock Problem in the Steel Industry
  29 September 2021
- On the Use of Equivalence Classes for Optimal and Suboptimal Bin Packing and Bin Covering
  IEEE Transactions on Automation Science and Engineering, Vol. 18, No. 1
- Extending an Integer Formulation for the Guillotine 2D Bin Packing Problem
  Procedia Computer Science, Vol. 195
- A generic exact solver for vehicle routing and related problems
  25 June 2020 | Mathematical Programming, Vol. 183, No. 1-2

cover image INFORMS Journal on Computing

Volume 32, Issue 1

Winter 2020

Pages 1-198, C2

Article Information

Supplemental Material

Metrics

Information

Received:September 22, 2017
Accepted:November 20, 2018
Published Online:July 18, 2019

Cite as

Maxence Delorme, Manuel Iori (2019) Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems. INFORMS Journal on Computing 32(1):101-119.

https://doi.org/10.1287/ijoc.2018.0880

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems

Supplemental Material

Volume 32, Issue 1

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News