# Constraint *BinPacking*

The constraint *BinPacking* ensures that a list of items, whose sizes are given, are put in different bins in such a way that a condition in term of capacity is respected for each bin.

Below, we illustrate three representative forms (use cases) of the constraint *BinPacking*.

## Case 1: *BinPacking* with the same condition on each bin

The first form of the constraint *BinPacking* corresponds to considering the same condition of capacity for each bin. It means that the capacity is assumed to be the same for all bins. When the operator `<=`

is used, this corresponds to not exceeding the capacity of each bin (this is the usual case).

In PyCSP$^3$, we must call the function *BinPacking()* that allows us to pass the variables either in sequence (individually) or under the form of a list. The named parameter *sizes* is required: it gives the size of each item. The object obtained when calling *BinPacking()*, under this form, represents the maximum accumulated size in a bin and must be restricted by a condition (typically, defined by a relational operator and a limit).

To see how this constraint works, we need first to import the library PyCSP$^3$:

```
from pycsp3 import *
```

For our illustration, we assume that we have 10 items with the following sizes:

```
sizes = [10, 7, 3, 9, 5, 7, 8, 4, 6, 4]
nItems = len(sizes)
```

Next, we introduce an array $x$ of 10 variables, each variable having {0,1, 2} as domain for denoting three different available bins.

```
x = VarArray(size=10, dom={0, 1, 2})
```

We can display (the structure of) the array as well as the domain of the first variable.

```
print("Array of variable x: ", x)
print("Domain of any variable: ", x[0].dom)
```

```
Array of variable x: [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9]]
Domain of any variable: 0 1 2
```

Now, we post a single constraint *BinPacking* while indicating that the capacity of each bin is the same and equal to 21.

```
satisfy(
BinPacking(x, sizes=sizes) <= 21
);
```

By calling the function solve(), we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can compute all solutions (supports) by setting the parameter *sols* to the constant *ALL*. We can also print the values assigned to the variables in the found solutions; we can call the function *values()* that collects the values assigned to a specified list of variables, while indicating the index of the solution with the parameter *sol*.

```
if solve(sols=ALL) is SAT:
for i in range(n_solutions()):
print(f"Solution {i+1}: {values(x, sol=i)}")
```

```
Solution 1: [0, 1, 2, 1, 1, 0, 2, 0, 2, 2]
Solution 2: [0, 1, 2, 1, 1, 0, 2, 2, 2, 0]
Solution 3: [0, 1, 0, 1, 1, 2, 2, 0, 2, 0]
Solution 4: [0, 1, 0, 1, 1, 2, 0, 2, 2, 2]
```

We can more easily verify that solutions are correct by executing:

```
if solve(sols=ALL) is SAT:
for i in range(n_solutions()):
print(f"Solution {i+1}:")
for j in (0,1,2):
print(f" Bin {j} with items {[k for k in range(nItems) if value(x[k], sol=i) == j]}" +
f" and occupied size {sum(sizes[k] for k in range(nItems) if value(x[k], sol=i) == j)}")
```

```
Solution 1:
Bin 0 with items [0, 5, 7] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [2, 6, 8, 9] and occupied size 21
Solution 2:
Bin 0 with items [0, 5, 9] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [2, 6, 7, 8] and occupied size 21
Solution 3:
Bin 0 with items [0, 2, 7, 9] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [5, 6, 8] and occupied size 21
Solution 4:
Bin 0 with items [0, 2, 6] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [5, 7, 8, 9] and occupied size 21
```

If ever we decrease the size of a single item, the occupied size is no more systematically equal to 21 (and the number of solutions increases a lot).

## Case 2: *BinPacking* with a specific limit expressed for each bin

The second form of the constraint *BinPacking* associates a specific limit (capacity) with each bin. The limits are given either by integer values or by integer variables by means of a parameter *limits*. We give an illustration with integer values.

First, we discard the last posted constraint:

```
unpost()
```

We can check that there are no more constraints:

```
print(posted())
```

```
[]
```

Now, we post a constraint *BinPacking* while indicating some specific limits. The capacities of bins 0, 1 and 2 are 23, 20, and 21, respectively.

```
satisfy(
BinPacking(x, sizes=sizes, limits=[23,20,21])
);
```

Let us compute the number of solutions:

```
if solve(sols=ALL) is SAT:
print(f"number of solutions {n_solutions()}")
```

```
number of solutions 26
```

Once again, we can display detailed information; here, just for the first found solution.

```
if solve() is SAT:
for j in (0,1,2):
print(f" Bin {j} with items {[k for k in range(nItems) if value(x[k]) == j]}" +
f" and occupied size (load) {sum(sizes[k] for k in range(nItems) if value(x[k]) == j)}")
```

```
Bin 0 with items [0, 4, 5] and occupied size (load) 22
Bin 1 with items [1, 3, 7] and occupied size (load) 20
Bin 2 with items [2, 6, 8, 9] and occupied size (load) 21
```

## Case 3: *BinPacking* with a specific load expressed for each bin

The third form of the constraint *BinPacking* associates a specific load with each bin. The loads are given either by integer values or by integer variables by means of a parameter *loads*. We give an illustration with integer variables.

Let us start by discarding the last posted constraint:

```
unpost()
```

Let us check that there are no more constraints:

```
print(posted())
```

```
[]
```

We need to introduce three variables for representing the loads of the bins.

```
y = VarArray(size=3, dom=range(23))
```

Now, we post a constraint *BinPacking* while indicating the specific loads. This plays two roles. The bounds (of the domains) of the load variables constrains packing, and the exact loads are computed.

```
satisfy(
BinPacking(x, sizes=sizes, loads=y)
);
```

Let us compute the number of solutions:

```
if solve(sols=ALL) is SAT:
print(f"number of solutions {n_solutions()}")
```

```
number of solutions 45
```

Once again, we can display detailed information; here, just for the first found solution.

```
if solve() is SAT:
for j in (0,1,2):
print(f" Bin {j} with items {[k for k in range(nItems) if value(x[k]) == j]}" +
f" and load {value(y[j])}")
```

```
Bin 0 with items [0, 1, 2] and load 20
Bin 1 with items [3, 4, 5] and load 21
Bin 2 with items [6, 7, 8, 9] and load 22
```

Finally, note that there exists a fourth general form, where specific conditions of any form can be expressed for bins. See the guide.

Since XCSP$^3$ Specifications 3.1, *BinPacking* belongs to XCSP$^3$-core (notably because solvers not equipped with a specific propagator can handle that constraint easily by posting $b$ constraints *Sum*, one per bin).