Skip to content

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

License

Notifications You must be signed in to change notification settings

eregnier/BinPacking2D

 
 

Repository files navigation

Exact solutions to two-dimensional bin packing problems DOI

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

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-sepcific 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 a 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.

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:

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.

About

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

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages

  • Python 100.0%