Exact solutions to two-dimensional bin packing problems

This is a partial replication of Côté, Haouari, Iori (2019): A Primal Decomposition Algorithm for the Two-dimensional Bin Packing Problem. arXiv:1909.06835 [math.OC] resp. Côté, Haouari, Iori (2021): Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem. INFORMS Journal on Computing, with components from - Côté, J. F., & Iori, M. (2018). The meet-in-the-middle principle for cutting and packing problems. INFORMS Journal on Computing, 30(4), 646-661. - Soh, T., Inoue, K., Tamura, N., Banbara, M., & Nabeshima, H. (2010). A SAT-based method for solving the two-dimensional strip packing problem. Fundamenta Informaticae, 102(3-4), 467-487 - Clautiaux, F., Carlier, J., & Moukrim, A. (2007). A new exact method for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 183(3), 1196-1211. - Clautiaux, F., Jouglet, A., Carlier, J., & Moukrim, A. (2008). A new constraint programming approach for the orthogonal packing problem. Computers & Operations Research, 35(3), 944-959.

In contrast to the original paper, this implementation uses constraint programming to solve subproblems and generate initial solutions, instead of mixed-integer programms (MIPs) or specialized heuristics. Not all preprocessing routines and lower bounding procedures are implemented.

Algorithmic outline

The two-dimensional bin packing problem (2D-BPP) is decomposed into a master problem and several subproblems. The master problem is a (one-dimensional) BPP, which assigns items to bins. Feasibility of each bin assignment is then checked in a separate two-dimensional orthogonal packing/knapsack (2D-OPP/2D-KP) subproblem.

The master problem is modeled as a MIP and solved using Gurobi. Callbacks are set at integer nodes, where the subproblems are generated and solved by constraint programming (CP) using google or-tools. When an infeasible subproblem is found, a cut of the form

is added to exclude the infeasible assignment of items to bins .

• Start solutions are generated by a solving a 2D-BPP problem via CP. Several models are implemented, a simple variant of one of the models can be found here.
• Preprocessing routines for the 2D-BPP include: filtering of large items, determining incompatible items, fixing and restricting item assignment through a conflict graph based on item incompatibility, different bin-specific placement point pattern strategies.
• The 2D-OPP subproblem is solved via CP, similar to CJCM08 (or-tools has most of the described propagations). But, the performance observed in CJCM08 of the most basic variant (Table 1 therein, without subset-sum improvements) cannot be replicated even with current hardware, cp. experiments/ComparisonCJCM.py. A 1D relaxation (the basic idea described in CCM07 and CJCM08) is also implemented and solved by branch-and-check with or-tools CP Solver.
• Preprocessing routines for the 2D-OPP include: removing large items, filter frame configurations, enlarge items by solving partial OPP instances (also called procedure) according to CCM07.
• Available placement point patterns are unit discretization, normal patterns, and meet-in-the-middle according to CI18. Additionally, we apply domain reductions of SIT+10, which are compatible with unit discretization, normal patterns, and with meet-in-the-middle (still need to prove the latter).
• Improvements to the decomposition approach include: cut strengthening by finding reduced infeasible sets (decrease lhs and rhs of infeasibility cuts), cut lifting by finding valid item displacements for infeasible sets (increasing lhs while keeping rhs constant).

Usage

There are three entry points for - branch-and-cut in packingSolver/BranchAndCut.py, - standalone 2D-BPP in packingSolver/BinPacking.py, and - standalone 2D-OPP in packingSolver/OrthogonalPacking.py.

Reading, writing and displaying data is handled by BinPackingData.py. For the 2D-BPP, the benchmark sets of J. O. Berkey and P. Y. Wang, “Two-Dimensional Finite Bin-Packing Algorithms,” J. Oper. Res. Soc., vol. 38, no. 5, p. 423, May 1987 and Martello and D. Vigo, “Exact Solution of the Two-Dimensional Finite Bin Packing Problem,” Manage. Sci., vol. 44, no. April 2015, pp. 388–399, 1998 are located in /data/input/BPP/CLASS/. For the 2D-OPP, the benchmark sets of CCM07 can be found in /data/input/OPP/CJCM08 and hard subproblems that arise when solving the BPP by branch-and-cut in /data/input/OPP/BPP-Subproblems.

The high-level branch-and-cut algorithm is implemented in the BinPackingBranchAndCutSolver class. ``` items, binHeight, binWidth = ReadBenchmarkData(instance)

solver = BinPackingBranchAndCutSolver() rectangles = solver.Run(items, binHeight, bindWidth) ```

Algorithmic features can be parametrized. ``` def SetCallbackData(self): self.Model.EnableLifting = False self.Model.EnableCutStrengthening = True self.Model._InfeasibleSuproblemCutThreshold = 1

self.Model._EnablePreprocessLifting = False
self.Model._PlacementPointStrategy = PlacementPointStrategy.NormalPatterns

```

Results

The output indicates whether the solution is optimal and if the solution was found during the constructive phase by constraint programming (solving a 2D-BPP with google's CP-SAT solver) or by branch-and-cut. Instance 1: Optimal solution = 8 found by CP (#items = 20) Instance 2: Optimal solution = 5 found by CP (#items = 20) Instance 3: Optimal solution = 9 found by CP (#items = 20) Instance 4: Optimal solution = 6 found by CP (#items = 20) Instance 5: Optimal solution = 6 found by CP (#items = 20) Instance 6: Optimal solution = 9 found by CP (#items = 20) Instance 7: Optimal solution = 6 found by CP (#items = 20) Instance 8: Optimal solution = 6 found by CP (#items = 20) Instance 9: Optimal solution = 8 found by CP (#items = 20) Instance 10: Optimal solution = 8 found by CP (#items = 20) Instance 11: Optimal solution = 10 found by B&C (#items = 40)

Evaluation

The algorithm produces optimal solutions for the majority of the 500 benchmark instances in less than 20 minutes. It has difficulty in proving feasibility/infeasibility of 2D-OPP subproblems for instances with many small items. For example, google's CP-SAT solver takes more than 300 seconds to solve single 2D-OPP subproblems, and some cannot be solved even with far greater time limit, see /data/input/OPP/BPP-Subproblems and https://github.com/google/or-tools/discussions/3177.

The most impactful algorithmic components are - symmetry breaking constraints (24) and (25) of the original paper (arXiv version), - removing large items and fixing conflicting items to bins (27) in accordance with (24) and (25), - and excluding pairwise incompatible items from bins with fixed items (26), - no-good cuts of type (4), - strong constraint programming formulations for the start solution (2D-BPP) and subproblems (2D-Knapsack) by reducing decision variable domains as much as possible, i.e., reducing available placement points through the techniques mentioned above and placement point patterns such as the meet-in-the-middle patterns. Although, the impact of placement patterns has diminished with more recent updates of or-tools.

Future research

The benefit of producing no-good cuts (29) from reduced feasible sets is only marginal. The benefit of lifting these cuts (30) is also only marginal, mainly due to the numerous 2D-KPs that must be solved. Hence, speeding up the solution of the 2D-KP of Algorithm 2 (currently solved as 2D-KP with google's CP-SAT and a time limit of 1 second) might increase the impact of lifting.

Components with the greatest potential to improve solution times: - an efficient algorithm to prove feasibility/infeasibility of problematic 2D-OPP subproblems with numerous small items using ideas from - Fekete, S. P., Schepers, J., & Van der Veen, J. C. (2007). An exact algorithm for higher-dimensional orthogonal packing. Operations Research, 55(3), 569-587. and subsequent improvements described in section 7.2 of Iori, M., de Lima, V. L., Martello, S., Miyazawa, F. K., & Monaci, M. (2021). Exact solution techniques for two-dimensional cutting and packing. European Journal of Operational Research, 289(2), 399-415. - Joncour, C., Pêcher, A., & Valicov, P. (2012). MPQ-trees for the orthogonal packing problem. Journal of Mathematical Modelling and Algorithms, 11(1), 3-22. - Joncour, C., & Pêcher, A. (2012). Consecutive ones matrices for multi-dimensional orthogonal packing problems. Journal of Mathematical Modelling and Algorithms, 11(1), 23-44. - Belov, G., Kartak, V., & Scheithauer, G. (2008). Lower-dimensional relaxations of higher-dimensional orthogonal packing. - Belov, G., & Rohling, H. (2009). A branch-and-price graph-theoretical algorithm for orthogonal-packing feasibility. Technical report, Preprint MATH-NM-10-2009, Technische Universität Dresden, which has similar performance as CJCM08 - Mesyagutov, M., Scheithauer, G., & Belov, G. (2012). LP bounds in various constraint programming approaches for orthogonal packing. Computers & operations research, 39(10), 2425-2438. - Belov, G., & Rohling, H. (2013). LP bounds in an interval-graph algorithm for orthogonal-packing feasibility. Operations Research, 61(2), 483-497. - CCM07 - Korf, R. E., Moffitt, M. D., & Pollack, M. E. (2010). Optimal rectangle packing. Annals of Operations Research, 179(1), 261-295. - Kartak, V. M., & Ripatti, A. V. (2018). The minimum raster set problem and its application to the d-dimensional orthogonal packing problem. European Journal of Operational Research, 271(1), 33-39. - a heuristic algorithm to find feasible 2D-OPP solutions fast - a variant of the BKRS lower bound (23)

To be efficient, these improvements require a more powerful programming language. We have implemented the two-step branching procedure of CCM07 in C++, but unfortunately, without being able to solve many of the hard 2D-OPP instances in /data/input/OPP/BPP-Subproblems. Please do get in touch if you can replicate the performance of CJCM08.