Bin Packing Problem

bins


In this tutorial we show you how to solve the bin packing operations research problem, using XLOPTIM, the fastest and most reliable solver for Microsoft Excel.

1. Data

To download the data for this XLOPTIM use case, please click the link below:

Download data for load Bin Packing problem

2. The Problem

In the bin packing problem, a number of items of known size have to be assigned to bins of uniform capacity. The goal is to minimize the number of bins used so that all items are placed. This is a typical example of an NP-hard problem.

The bin packing problem can be applied, for example, to the storage of files on a computer support, to the cutting of cables or to the filling of trucks or containers (constraint on the size or volume of the items).

The capacity of the bins here is 1000. For each of the 30 items, we know their size given in the table below:

table1

We seek to provide a linear modeling of this bin packing problem, as well as a decision support tool in XLOPTIM®.

3. Modeling

We propose a modeling according to the following 5 steps:

Step #1: What are the dimensions / clues of the problem?

  • i : 1.. 30: the items
  • j : 1 .. 30: the bins

Step #2: What are the data of the problem?

  • The size of each item i:

$$P_{i}$$

  • The maximum capacity:

$$K$$

Step #3: What are the decision variables?

  • Do I position item i in bin j or not (boolean):

$$X_{ij}$$

  • Do I open bin j or not (boolean):

$$Y_{j}$$

Step #4: What are the constraints?

  • Each item appears in a bin:

$$\forall \,\ i \in [1;30], \sum_{j=1}^{30}{X_{ij}=1}$$

  • Each size of a bin does not exceed the capacity K:

$$\forall \,\ j \in [1;30], \sum_{i=1}^{30}{X_{ij}.P_i \leqslant Y_j.K}$$

Step #5: What is the objective of the problem?

$$Min\sum_{j=1}^{30}{Y_j}$$

4. Translation into XLOPTIM®

xloptim1

Definition of the 2 main Boolean decision variables:

xloptim2 xloptim3

Addition of the constraint “each item is in a bin”:

xloptim4

Addition of the constraint on the size of each bin:

xloptim5

Setting the objective (minimize the number of bins used):

xloptim6

Calculation of the optimum:

xloptim7

which gives a value of the following optimal objective function:

xloptim8

5. Conclusion

The assignment of objects to the bins allowed us to open only 15 bins for 30 initial objects or 2 objects per bin. The displayed solution is achievable and obtained after 2 seconds

This case study gives you an example of a bin filling problem. They are frequent in the industrial problems of filling trucks, loading, cutting cables. You can change the size of the problem and the assumptions to vary the problem and therefore the solutions. Do not hesitate to contact us if you have any questions following the use of our XLOPTIM® solver.

To download the 14-day free trial version of the software, go to: Download the trial version