The Meet-in-the-Middle Principle for Cutting and Packing Problems

Jean-François Côté
Jean-François Côté
[email protected]
http://orcid.org/0000-0002-6437-7638
CIRRELT, Université Laval, Québec G1V 0A6, Canada
Search for more papers by this author
,
Manuel Iori
Corresponding Author
Manuel Iori
[email protected]
http://orcid.org/0000-0003-2097-6572
Department of Sciences and Methods for Engineering (DISMI), University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
Search for more papers by this author

CIRRELT, Université Laval, Québec G1V 0A6, Canada

Corresponding Author

Manuel Iori

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

Department of Sciences and Methods for Engineering (DISMI), University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy

Search for more papers by this author

Published Online:2 Nov 2018https://doi.org/10.1287/ijoc.2018.0806

Supplemental Material

ijoc.2018.0806-sm.pdf (64 KB)

Cited by
- Matheuristic approaches for multi-product 3-dimensional container loading problem
  18 March 2026 | Applied Operations and Analytics, Vol. 2, No. 1
- Extending the reflect flow formulation to variable-sized one-dimensional cutting and skiving stock problems
  European Journal of Operational Research, Vol. 334, No. 1
- A branch-and-cut algorithm for vehicle routing problems with three-dimensional loading constraints
  European Journal of Operational Research, Vol. 331, 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
- A combinatorial Benders decomposition approach for the constrained two-dimensional guillotine cutting problem with defects
  3 June 2025 | International Journal of Production Research, Vol. 63, No. 23
- EATKG: An Open-Source Efficient Exact Algorithm for the Two-Dimensional Knapsack Problem with Guillotine Constraints
  European Journal of Operational Research, Vol. 327, No. 3
- Smart Automated Guided Vehicle scheduling with flexible battery management: A new formulation and an exact approach
  Computers & Operations Research, Vol. 183
- Two-dimensional bin packing, cutting stock, and open dimension problems: A survey of practical requirements
  Computers & Operations Research, Vol. 183
- A matheuristic method for the automated guided vehicle scheduling problem with flexible charging and job release
  Applied Soft Computing, Vol. 182
- 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. 0, No. 0
- An adaptive large neighborhood search method for the AGV scheduling problem with a limited number of chargers
  12 February 2025 | International Journal of Production Research, Vol. 63, No. 15
- 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 new branch-and-cut approach for integrated planning in additive manufacturing
  European Journal of Operational Research, Vol. 322, No. 2
- An exact approach for the two-dimensional strip packing problem with defects
  Computers & Industrial Engineering, Vol. 200
- 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
- Exact Algorithms for Two-Dimensional Knapsack Problems: A Unified Framework with New Benchmark Results
  1 January 2025 | SSRN Electronic Journal, Vol. 183
- Combinatorial Benders' decomposition for the constrained two-dimensional non-guillotine cutting problem with defects
  8 April 2024 | International Journal of Production Research, Vol. 62, No. 23
- An Effective Heuristic Algorithm for the Two-Dimensional Orthogonal Packing Problem
- Improved dynamic programming algorithms for unconstrained two-dimensional guillotine cutting
  Computers & Operations Research, Vol. 167
- A variable neighborhood search for the green vehicle routing problem with two-dimensional loading constraints and split delivery
  European Journal of Operational Research, Vol. 316, No. 2
- Exact decomposition approaches for a single container loading problem with stacking constraints and medium-sized weakly heterogeneous items
  Omega, Vol. 125
- Mathematical models and exact algorithms for the Colored Bin Packing Problem
  Computers & Operations Research, Vol. 164
- Exact approaches for the unconstrained two-dimensional cutting problem with defects
  Computers & Operations Research, Vol. 160
- An adaptive large neighborhood search metaheuristic for the Generalized Bin Packing problem with incompatible categories
  Computers & Industrial Engineering, Vol. 185
- An introduction to the two‐dimensional rectangular cutting and packing problem
  17 November 2022 | International Transactions in Operational Research, Vol. 30, No. 6
- Dynamic scheduling of patients in emergency departments
  European Journal of Operational Research, Vol. 310, No. 1
- Mathematical models for the cutting stock with limited open stacks problem
  1 August 2023 | RAIRO - Operations Research, Vol. 57, No. 4
- An exact approach for the constrained two-dimensional guillotine cutting problem with defects
  18 May 2022 | International Journal of Production Research, Vol. 61, No. 9
- Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry
  European Journal of Operational Research, Vol. 306, No. 2
- 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
- Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost
  European Journal of Operational Research, Vol. 304, 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
- 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
- A cutting plane method and a parallel algorithm for packing rectangles in a circular container
  European Journal of Operational Research, Vol. 303, No. 1
- On the optimal layout of a dining room in the era of COVID‐19 using mathematical optimization
  5 April 2022 | International Transactions in Operational Research, Vol. 29, No. 6
- 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
- Arc flow formulations based on dynamic programming: Theoretical foundations and applications
  European Journal of Operational Research, Vol. 296, No. 1
- An exact approach for the green vehicle routing problem with two-dimensional loading constraints and split delivery
  Computers & Operations Research, Vol. 136
- Arc-flow approach for single batch-processing machine scheduling
  Computers & Operations Research, Vol. 134
- An exact framework for the discrete parallel machine scheduling location problem
  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
- Logistic constraints in container loading problems: the impact of complete shipment conditions
  24 July 2020 | TOP, Vol. 29, No. 1
- Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization
  European Journal of Operational Research, Vol. 289, No. 3
- Exact solution techniques for two-dimensional cutting and packing
  European Journal of Operational Research, Vol. 289, No. 2
- New Exact Techniques Applied to a Class of Network Flow Formulations
  5 May 2021
- Simulation model and performance evaluation of battery-powered AGV systems in automated container terminals
  Simulation Modelling Practice and Theory, Vol. 106
- Extending an Integer Formulation for the Guillotine 2D Bin Packing Problem
  Procedia Computer Science, Vol. 195
- Scheduling jobs with release dates on identical parallel machines by minimizing the total weighted completion time
  Computers & Operations Research, Vol. 123
- Grids for cutting and packing problems: a study in the 2D knapsack problem
  24 September 2019 | 4OR, Vol. 18, No. 3
- The exact solutions of several types of container loading problems
  European Journal of Operational Research, Vol. 284, No. 1
- Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization
  3 June 2019 | International Transactions in Operational Research, Vol. 27, No. 2
- Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
  Maxence Delorme,
  Manuel Iori
  18 July 2019 | INFORMS Journal on Computing, Vol. 32, No. 1
- Improved flow-based formulations for the skiving stock problem
  Computers & Operations Research, Vol. 113
- Mathematical models and decomposition methods for the multiple knapsack problem
  European Journal of Operational Research, Vol. 274, No. 3
- Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines
  European Journal of Operational Research, Vol. 275, No. 1
- An Improved Arcflow Model for the Skiving Stock Problem
  30 August 2019

cover image INFORMS Journal on Computing

Volume 30, Issue 4

Fall 2018

Pages 625-786

Article Information

Supplemental Material

Metrics

Information

Received:June 13, 2016
Accepted:January 04, 2018
Published Online:November 02, 2018

Cite as

Jean-François Côté, Manuel Iori (2018) The Meet-in-the-Middle Principle for Cutting and Packing Problems. INFORMS Journal on Computing 30(4):646-661.

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

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Meet-in-the-Middle Principle for Cutting and Packing Problems

Supplemental Material

Volume 30, Issue 4

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News