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).