On the Use of Equivalence Classes for Optimal and Suboptimal Bin Packing and Bin Covering

摘要

Bin packing and bin covering are important optimization problems in many industrial fields, such as packaging, recycling, and food processing. The problem concerns a set of items, each with its own value, that are to be sorted into bins in such a way that the total value of each bin, as measured by the sum of its item values, is not above (for packing) or below (for covering) a given target value. The optimization problem concerns minimizing, for bin packing, or maximizing, for bin covering, the number of bins. This is a combinatorial NP-hard problem, for which true optimal solutions can only be calculated in specific cases, such as when restricted to a small number of items. To get around this problem, many suboptimal approaches exist. This article describes the formulations of the bin packing and covering problems that allow finding the true optimum, for instance, counting hundreds of items using general-purpose MILP-solvers. Also presented are suboptimal solutions that come within less than 10% of the optimum while taking significantly less time to calculate, even ten to 100 times faster, depending on the required accuracy. Note to Practitioners-A typical case for bin covering is in food processing where food items are automatically sorted into trays of similar weight so that the overweight is minimized. Another application is in recycling, where items such as batteries should be put in crates of similar weight, so that the crates do not exceed a target weight due to later manual handling, but, at the same time, we want as few crates as possible. This is a bin packing problem. On an industrial scale, these tasks are fully automated. Though modern software tool's efficiency to solve bin sorting problems has increased significantly in later years, the problems are inherently tough in the sense that the solution time grows exponentially with the number of items. This limits the problem sizes that can be solved to optimality within a reasonable time. Therefore, much research has focused on heuristic rules that give reasonable solving times while not giving the true optimal number of bins. However, in many cases, the true optimal solution is preferable, and sometimes even necessary, so this is an industrially interesting problem. This article describes an approach to solve the bin packing and covering problems to the true optimum that increases the limit of the number of items that can typically be handled. This is done by observing that items of the same value need not be distinguished. Instead, we can formulate packing/covering problems over item values rather than individual items and sort integer numbers of these values into bins, which allows us to solve to optimum for more than 500 items in a reasonable time. In addition, by redefining what we mean by the same value, we can consider more items to have the same value and achieve even better calculation efficiency.