BinPacking2D

KO | EN

gitlite — search

#javascript #java #php #python #android #shell #dotfiles #hacktoberfest #c-sharp #web-components #security #html

★ 83 Open GitHub ↗

Exact solutions for two-dimensional bin packing problems by branch-and-cut

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Exact solutions to two-dimensional bin packing problems [![DOI](https://zenodo.org/badge/DOI/10.5281/zenodo.6673912.svg)](https://doi.org/10.5281/zenodo.6673912)

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]](https://arxiv.org/abs/1909.06835) resp. [Côté, Haouari, Iori (2021): Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem. INFORMS Journal on Computing](https://doi.org/10.1287/ijoc.2020.1014), 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.](https://doi.org/10.1287/ijoc.2018.0806) 
- [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](https://doi.org/10.3233/FI-2010-314)
- [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.](https://doi.org/10.1016/j.ejor.2005.12.048)
- [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.](https://doi.org/10.1016/j.cor.2006.05.012)

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](https://www.gurobi.com/). Callbacks are set at integer nodes, where the subproblems are generated and solved by constraint programming (CP) using [google or-tools](https://developers.google.com/optimization/cp/cp_solver). When an infeasible subproblem is found, a cut of the form

is added to exclude the infeasible assignment of items <img src="https://render.githubusercontent.com/render/math?math=j \in \mathcal{C}"> to bins <img src="https://render.githubusercontent.com/render/math?math=i \in \mathcal{B}">.

- 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](http://yetanothermathprogrammingconsultant.blogspot.com/2021/02/2d-bin-packing-with-google-or-tools-cp.html).
- 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](https://doi.org/10.1016/j.cor.2006.05.012) (or-tools has most of the described propagations). But, the performance observed in [CJCM08](https://doi.org/10.1016/j.cor.2006.05.012) 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](https://doi.org/10.1016/j.ejor.2005.12.048) and [CJCM08](https://doi.org/10.1016/j.cor.2006.05.012)) 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 <img src="https://render.githubusercontent.com/render/math?math=v_1^{*}"> procedure) according to [CCM07](https://doi.org/10.1016/j.ejor.2005.12.048).
- Available placement point patterns are unit discretization, normal patterns, and meet-in-the-middle according to [CI18](https://doi.org/10.1287/ijoc.2018.0806). Additionally, we apply domain reductions of [SIT+10](https://doi.org/10.3233/FI-2010-314), 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](https://github.com/Oscar-Oliveira/OR-Datasets/tree/master/Cutting-and-Packing/2D/Datasets/CLASS) are located in `/data/input/BPP/CLASS/`. For the 2D-OPP, the benchmark sets of [CCM07](https://doi.org/10.1016/j.ejor.2005.12.048) 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.](https://doi.org/10.1287/opre.1060.0369) 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.](https://doi.org/10.1016/j.ejor.2020.06.050)
        - [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.](https://doi.org/10.1007/s10852-011-9159-z)
        - [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.](https://doi.org/10.1007/s10852-011-9167-z)
        - [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](https://doi.org/10.1016/j.cor.2006.05.012)
    - [Mesyagutov, M., Scheithauer, G., & Belov, G. (2012). LP bounds in various constraint programming approaches for orthogonal packing. Computers & operations research, 39(10), 2425-2438.](https://doi.org/10.1016/j.cor.2011.12.010)
    - [Belov, G., & Rohling, H. (2013). LP bounds in an interval-graph algorithm for orthogonal-packing feasibility. Operations Research, 61(2), 483-497.](https://doi.org/10.1287/opre.1120.1150)
    - [CCM07](https://doi.org/10.1016/j.ejor.2005.12.048)
    - [Korf, R. E., Moffitt, M. D., & Pollack, M. E. (2010). Optimal rectangle packing. Annals of Operations Research, 179(1), 261-295.](https://doi.org/10.1007/s10479-008-0463-6)
    - [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.](https://doi.org/10.1016/j.ejor.2018.04.046)
- 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](https://github.com/ktnr/TwoStepBranchingProcedure) of [CCM07](https://doi.org/10.1016/j.ejor.2005.12.048) 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](https://doi.org/10.1016/j.cor.2006.05.012).

BinPacking2D

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README