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, 0, 1, 1, 1, 2, 2, 0, 2, 1]
Solution 2: [0, 0, 1, 1, 1, 2, 2, 1, 2, 0]
Solution 3: [0, 0, 1, 2, 1, 1, 2, 2, 1, 0]
Solution 4: [0, 0, 1, 2, 1, 1, 2, 0, 1, 2]
Solution 5: [0, 0, 1, 2, 2, 2, 1, 0, 1, 1]
Solution 6: [0, 0, 1, 2, 2, 2, 1, 1, 1, 0]
Solution 7: [0, 0, 2, 1, 2, 2, 1, 1, 2, 0]
Solution 8: [0, 0, 2, 1, 2, 2, 1, 0, 2, 1]
Solution 9: [0, 0, 2, 2, 2, 1, 1, 2, 1, 0]
Solution 10: [0, 0, 2, 2, 2, 1, 1, 0, 1, 2]
Solution 11: [0, 0, 2, 1, 1, 1, 2, 0, 2, 2]
Solution 12: [0, 0, 2, 1, 1, 1, 2, 2, 2, 0]
Solution 13: [0, 2, 0, 1, 1, 1, 2, 0, 2, 0]
Solution 14: [0, 2, 0, 1, 1, 1, 0, 2, 2, 2]
Solution 15: [0, 2, 1, 1, 1, 0, 2, 0, 2, 1]
Solution 16: [0, 2, 1, 1, 1, 0, 2, 1, 2, 0]
Solution 17: [0, 2, 2, 1, 2, 0, 1, 1, 2, 0]
Solution 18: [0, 2, 2, 1, 2, 0, 1, 0, 2, 1]
Solution 19: [2, 0, 0, 1, 2, 0, 1, 0, 2, 1]
Solution 20: [2, 0, 0, 1, 2, 0, 1, 1, 2, 0]
Solution 21: [1, 0, 1, 2, 2, 2, 1, 0, 0, 0]
Solution 22: [0, 1, 0, 2, 2, 2, 1, 0, 1, 0]
Solution 23: [2, 1, 0, 0, 0, 2, 1, 2, 1, 0]
Solution 24: [2, 1, 2, 0, 0, 0, 1, 2, 1, 2]
Solution 25: [2, 1, 0, 0, 0, 2, 1, 0, 1, 2]
Solution 26: [2, 0, 0, 1, 0, 2, 1, 1, 0, 2]
Solution 27: [2, 0, 0, 1, 0, 2, 1, 2, 0, 1]
Solution 28: [2, 0, 1, 0, 0, 2, 1, 2, 1, 1]
Solution 29: [2, 0, 1, 0, 0, 2, 1, 1, 1, 2]
Solution 30: [2, 0, 2, 0, 0, 1, 1, 2, 1, 2]
Solution 31: [2, 2, 0, 0, 0, 1, 1, 0, 1, 2]
Solution 32: [2, 2, 0, 0, 0, 1, 1, 2, 1, 0]
Solution 33: [2, 2, 1, 0, 0, 0, 1, 2, 1, 1]
Solution 34: [2, 2, 1, 0, 0, 0, 1, 1, 1, 2]
Solution 35: [1, 2, 1, 0, 0, 0, 2, 1, 2, 1]
Solution 36: [1, 2, 0, 0, 0, 1, 2, 1, 2, 0]
Solution 37: [1, 2, 0, 0, 0, 1, 2, 0, 2, 1]
Solution 38: [1, 0, 2, 0, 0, 1, 2, 2, 2, 1]
Solution 39: [1, 0, 2, 0, 0, 1, 2, 1, 2, 2]
Solution 40: [2, 0, 2, 0, 0, 1, 2, 1, 1, 1]
Solution 41: [2, 1, 2, 0, 0, 0, 2, 1, 1, 1]
Solution 42: [2, 2, 0, 1, 0, 0, 1, 2, 0, 1]
Solution 43: [1, 1, 0, 2, 0, 0, 2, 2, 0, 1]
Solution 44: [1, 1, 2, 0, 0, 0, 2, 2, 2, 1]
Solution 45: [1, 0, 0, 2, 0, 1, 2, 2, 0, 1]
Solution 46: [0, 1, 1, 2, 0, 1, 2, 2, 0, 1]
Solution 47: [1, 1, 0, 0, 0, 2, 2, 0, 2, 1]
Solution 48: [1, 0, 1, 0, 0, 2, 2, 1, 2, 1]
Solution 49: [1, 0, 1, 0, 0, 2, 1, 2, 2, 2]
Solution 50: [1, 0, 1, 2, 2, 2, 0, 1, 0, 1]
Solution 51: [2, 0, 1, 1, 1, 2, 0, 1, 0, 2]
Solution 52: [2, 0, 1, 1, 1, 2, 0, 2, 0, 1]
Solution 53: [2, 0, 2, 1, 1, 1, 0, 2, 0, 2]
Solution 54: [2, 0, 2, 1, 1, 1, 2, 0, 0, 0]
Solution 55: [1, 0, 0, 2, 0, 1, 2, 1, 0, 2]
Solution 56: [1, 0, 2, 2, 2, 1, 0, 1, 0, 2]
Solution 57: [1, 0, 2, 2, 2, 1, 0, 2, 0, 1]
Solution 58: [1, 1, 2, 2, 2, 0, 0, 2, 0, 1]
Solution 59: [1, 1, 2, 2, 2, 0, 0, 1, 0, 2]
Solution 60: [1, 1, 0, 2, 2, 2, 0, 1, 0, 0]
Solution 61: [1, 1, 0, 2, 2, 2, 0, 0, 0, 1]
Solution 62: [1, 2, 1, 2, 2, 0, 0, 1, 0, 1]
Solution 63: [1, 2, 1, 2, 2, 0, 1, 0, 0, 0]
Solution 64: [1, 2, 0, 2, 2, 1, 0, 1, 0, 0]
Solution 65: [1, 1, 0, 2, 0, 0, 2, 1, 0, 2]
Solution 66: [0, 1, 1, 2, 0, 1, 2, 1, 0, 2]
Solution 67: [0, 2, 0, 2, 2, 1, 0, 1, 1, 1]
Solution 68: [0, 2, 1, 2, 2, 0, 1, 1, 1, 0]
Solution 69: [0, 1, 0, 2, 2, 2, 0, 1, 1, 1]
Solution 70: [1, 1, 2, 0, 2, 2, 0, 1, 2, 0]
Solution 71: [1, 1, 2, 0, 2, 2, 0, 0, 2, 1]
Solution 72: [1, 1, 2, 0, 0, 0, 2, 1, 2, 2]
Solution 73: [1, 2, 2, 0, 1, 2, 0, 0, 1, 2]
Solution 74: [1, 2, 2, 0, 1, 2, 0, 2, 1, 0]
Solution 75: [1, 2, 2, 0, 2, 1, 0, 1, 2, 0]
Solution 76: [1, 2, 2, 0, 2, 1, 0, 0, 2, 1]
Solution 77: [0, 2, 2, 1, 0, 2, 1, 2, 0, 1]
Solution 78: [0, 2, 2, 1, 0, 2, 1, 1, 0, 2]
Solution 79: [0, 1, 2, 2, 2, 0, 1, 0, 1, 2]
Solution 80: [0, 1, 2, 2, 2, 0, 1, 2, 1, 0]
Solution 81: [2, 1, 2, 1, 1, 0, 0, 2, 0, 2]
Solution 82: [0, 1, 2, 1, 1, 0, 2, 2, 2, 0]
Solution 83: [0, 1, 0, 1, 1, 2, 2, 0, 2, 0]
Solution 84: [0, 1, 1, 2, 1, 0, 2, 2, 1, 0]
Solution 85: [0, 2, 0, 2, 2, 1, 1, 0, 1, 0]
Solution 86: [0, 1, 0, 1, 1, 2, 0, 2, 2, 2]
Solution 87: [1, 1, 0, 0, 0, 2, 2, 1, 2, 0]
Solution 88: [2, 1, 0, 1, 1, 2, 0, 0, 0, 2]
Solution 89: [2, 1, 0, 1, 1, 2, 0, 2, 0, 0]
Solution 90: [2, 2, 0, 1, 0, 0, 1, 1, 0, 2]
Solution 91: [2, 2, 0, 1, 1, 1, 0, 0, 0, 2]
Solution 92: [2, 2, 0, 1, 1, 1, 0, 2, 0, 0]
Solution 93: [2, 2, 1, 1, 1, 0, 0, 2, 0, 1]
Solution 94: [2, 2, 1, 1, 1, 0, 0, 1, 0, 2]
Solution 95: [2, 1, 1, 0, 2, 1, 0, 1, 2, 0]
Solution 96: [2, 1, 1, 0, 2, 1, 0, 0, 2, 1]
Solution 97: [2, 1, 1, 0, 1, 2, 0, 0, 1, 2]
Solution 98: [2, 2, 1, 0, 1, 1, 0, 0, 1, 2]
Solution 99: [2, 2, 1, 0, 1, 1, 0, 2, 1, 0]
Solution 100: [2, 1, 1, 0, 1, 2, 0, 2, 1, 0]
Solution 101: [1, 2, 0, 2, 2, 1, 0, 0, 0, 1]
Solution 102: [0, 2, 1, 2, 2, 0, 1, 0, 1, 1]
Solution 103: [0, 1, 1, 2, 1, 0, 2, 0, 1, 2]
Solution 104: [0, 1, 2, 1, 1, 0, 2, 0, 2, 2]
Solution 105: [1, 2, 1, 0, 0, 0, 1, 2, 2, 2]
Solution 106: [1, 0, 0, 2, 1, 0, 2, 0, 1, 2]
Solution 107: [1, 0, 0, 2, 1, 0, 2, 2, 1, 0]
Solution 108: [2, 1, 2, 1, 1, 0, 2, 0, 0, 0]
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, 1, 7] and occupied size 21
Bin 1 with items [2, 3, 4, 9] and occupied size 21
Bin 2 with items [5, 6, 8] and occupied size 21
Solution 2:
Bin 0 with items [0, 1, 9] and occupied size 21
Bin 1 with items [2, 3, 4, 7] and occupied size 21
Bin 2 with items [5, 6, 8] and occupied size 21
Solution 3:
Bin 0 with items [0, 1, 9] and occupied size 21
Bin 1 with items [2, 4, 5, 8] and occupied size 21
Bin 2 with items [3, 6, 7] and occupied size 21
Solution 4:
Bin 0 with items [0, 1, 7] and occupied size 21
Bin 1 with items [2, 4, 5, 8] and occupied size 21
Bin 2 with items [3, 6, 9] and occupied size 21
Solution 5:
Bin 0 with items [0, 1, 7] and occupied size 21
Bin 1 with items [2, 6, 8, 9] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 6:
Bin 0 with items [0, 1, 9] and occupied size 21
Bin 1 with items [2, 6, 7, 8] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 7:
Bin 0 with items [0, 1, 9] and occupied size 21
Bin 1 with items [3, 6, 7] and occupied size 21
Bin 2 with items [2, 4, 5, 8] and occupied size 21
Solution 8:
Bin 0 with items [0, 1, 7] and occupied size 21
Bin 1 with items [3, 6, 9] and occupied size 21
Bin 2 with items [2, 4, 5, 8] and occupied size 21
Solution 9:
Bin 0 with items [0, 1, 9] and occupied size 21
Bin 1 with items [5, 6, 8] and occupied size 21
Bin 2 with items [2, 3, 4, 7] and occupied size 21
Solution 10:
Bin 0 with items [0, 1, 7] and occupied size 21
Bin 1 with items [5, 6, 8] and occupied size 21
Bin 2 with items [2, 3, 4, 9] and occupied size 21
Solution 11:
Bin 0 with items [0, 1, 7] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [2, 6, 8, 9] and occupied size 21
Solution 12:
Bin 0 with items [0, 1, 9] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [2, 6, 7, 8] and occupied size 21
Solution 13:
Bin 0 with items [0, 2, 7, 9] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [1, 6, 8] and occupied size 21
Solution 14:
Bin 0 with items [0, 2, 6] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [1, 7, 8, 9] and occupied size 21
Solution 15:
Bin 0 with items [0, 5, 7] and occupied size 21
Bin 1 with items [2, 3, 4, 9] and occupied size 21
Bin 2 with items [1, 6, 8] and occupied size 21
Solution 16:
Bin 0 with items [0, 5, 9] and occupied size 21
Bin 1 with items [2, 3, 4, 7] and occupied size 21
Bin 2 with items [1, 6, 8] and occupied size 21
Solution 17:
Bin 0 with items [0, 5, 9] and occupied size 21
Bin 1 with items [3, 6, 7] and occupied size 21
Bin 2 with items [1, 2, 4, 8] and occupied size 21
Solution 18:
Bin 0 with items [0, 5, 7] and occupied size 21
Bin 1 with items [3, 6, 9] and occupied size 21
Bin 2 with items [1, 2, 4, 8] and occupied size 21
Solution 19:
Bin 0 with items [1, 2, 5, 7] and occupied size 21
Bin 1 with items [3, 6, 9] and occupied size 21
Bin 2 with items [0, 4, 8] and occupied size 21
Solution 20:
Bin 0 with items [1, 2, 5, 9] and occupied size 21
Bin 1 with items [3, 6, 7] and occupied size 21
Bin 2 with items [0, 4, 8] and occupied size 21
Solution 21:
Bin 0 with items [1, 7, 8, 9] and occupied size 21
Bin 1 with items [0, 2, 6] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 22:
Bin 0 with items [0, 2, 7, 9] and occupied size 21
Bin 1 with items [1, 6, 8] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 23:
Bin 0 with items [2, 3, 4, 9] and occupied size 21
Bin 1 with items [1, 6, 8] and occupied size 21
Bin 2 with items [0, 5, 7] and occupied size 21
Solution 24:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [1, 6, 8] and occupied size 21
Bin 2 with items [0, 2, 7, 9] and occupied size 21
Solution 25:
Bin 0 with items [2, 3, 4, 7] and occupied size 21
Bin 1 with items [1, 6, 8] and occupied size 21
Bin 2 with items [0, 5, 9] and occupied size 21
Solution 26:
Bin 0 with items [1, 2, 4, 8] and occupied size 21
Bin 1 with items [3, 6, 7] and occupied size 21
Bin 2 with items [0, 5, 9] and occupied size 21
Solution 27:
Bin 0 with items [1, 2, 4, 8] and occupied size 21
Bin 1 with items [3, 6, 9] and occupied size 21
Bin 2 with items [0, 5, 7] and occupied size 21
Solution 28:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [2, 6, 8, 9] and occupied size 21
Bin 2 with items [0, 5, 7] and occupied size 21
Solution 29:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [2, 6, 7, 8] and occupied size 21
Bin 2 with items [0, 5, 9] and occupied size 21
Solution 30:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [5, 6, 8] and occupied size 21
Bin 2 with items [0, 2, 7, 9] and occupied size 21
Solution 31:
Bin 0 with items [2, 3, 4, 7] and occupied size 21
Bin 1 with items [5, 6, 8] and occupied size 21
Bin 2 with items [0, 1, 9] and occupied size 21
Solution 32:
Bin 0 with items [2, 3, 4, 9] and occupied size 21
Bin 1 with items [5, 6, 8] and occupied size 21
Bin 2 with items [0, 1, 7] and occupied size 21
Solution 33:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [2, 6, 8, 9] and occupied size 21
Bin 2 with items [0, 1, 7] and occupied size 21
Solution 34:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [2, 6, 7, 8] and occupied size 21
Bin 2 with items [0, 1, 9] and occupied size 21
Solution 35:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [0, 2, 7, 9] and occupied size 21
Bin 2 with items [1, 6, 8] and occupied size 21
Solution 36:
Bin 0 with items [2, 3, 4, 9] and occupied size 21
Bin 1 with items [0, 5, 7] and occupied size 21
Bin 2 with items [1, 6, 8] and occupied size 21
Solution 37:
Bin 0 with items [2, 3, 4, 7] and occupied size 21
Bin 1 with items [0, 5, 9] and occupied size 21
Bin 2 with items [1, 6, 8] and occupied size 21
Solution 38:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [0, 5, 9] and occupied size 21
Bin 2 with items [2, 6, 7, 8] and occupied size 21
Solution 39:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [0, 5, 7] and occupied size 21
Bin 2 with items [2, 6, 8, 9] and occupied size 21
Solution 40:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [5, 7, 8, 9] and occupied size 21
Bin 2 with items [0, 2, 6] and occupied size 21
Solution 41:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [1, 7, 8, 9] and occupied size 21
Bin 2 with items [0, 2, 6] and occupied size 21
Solution 42:
Bin 0 with items [2, 4, 5, 8] and occupied size 21
Bin 1 with items [3, 6, 9] and occupied size 21
Bin 2 with items [0, 1, 7] and occupied size 21
Solution 43:
Bin 0 with items [2, 4, 5, 8] and occupied size 21
Bin 1 with items [0, 1, 9] and occupied size 21
Bin 2 with items [3, 6, 7] and occupied size 21
Solution 44:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [0, 1, 9] and occupied size 21
Bin 2 with items [2, 6, 7, 8] and occupied size 21
Solution 45:
Bin 0 with items [1, 2, 4, 8] and occupied size 21
Bin 1 with items [0, 5, 9] and occupied size 21
Bin 2 with items [3, 6, 7] and occupied size 21
Solution 46:
Bin 0 with items [0, 4, 8] and occupied size 21
Bin 1 with items [1, 2, 5, 9] and occupied size 21
Bin 2 with items [3, 6, 7] and occupied size 21
Solution 47:
Bin 0 with items [2, 3, 4, 7] and occupied size 21
Bin 1 with items [0, 1, 9] and occupied size 21
Bin 2 with items [5, 6, 8] and occupied size 21
Solution 48:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [0, 2, 7, 9] and occupied size 21
Bin 2 with items [5, 6, 8] and occupied size 21
Solution 49:
Bin 0 with items [1, 3, 4] and occupied size 21
Bin 1 with items [0, 2, 6] and occupied size 21
Bin 2 with items [5, 7, 8, 9] and occupied size 21
Solution 50:
Bin 0 with items [1, 6, 8] and occupied size 21
Bin 1 with items [0, 2, 7, 9] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 51:
Bin 0 with items [1, 6, 8] and occupied size 21
Bin 1 with items [2, 3, 4, 7] and occupied size 21
Bin 2 with items [0, 5, 9] and occupied size 21
Solution 52:
Bin 0 with items [1, 6, 8] and occupied size 21
Bin 1 with items [2, 3, 4, 9] and occupied size 21
Bin 2 with items [0, 5, 7] and occupied size 21
Solution 53:
Bin 0 with items [1, 6, 8] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [0, 2, 7, 9] and occupied size 21
Solution 54:
Bin 0 with items [1, 7, 8, 9] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [0, 2, 6] and occupied size 21
Solution 55:
Bin 0 with items [1, 2, 4, 8] and occupied size 21
Bin 1 with items [0, 5, 7] and occupied size 21
Bin 2 with items [3, 6, 9] and occupied size 21
Solution 56:
Bin 0 with items [1, 6, 8] and occupied size 21
Bin 1 with items [0, 5, 7] and occupied size 21
Bin 2 with items [2, 3, 4, 9] and occupied size 21
Solution 57:
Bin 0 with items [1, 6, 8] and occupied size 21
Bin 1 with items [0, 5, 9] and occupied size 21
Bin 2 with items [2, 3, 4, 7] and occupied size 21
Solution 58:
Bin 0 with items [5, 6, 8] and occupied size 21
Bin 1 with items [0, 1, 9] and occupied size 21
Bin 2 with items [2, 3, 4, 7] and occupied size 21
Solution 59:
Bin 0 with items [5, 6, 8] and occupied size 21
Bin 1 with items [0, 1, 7] and occupied size 21
Bin 2 with items [2, 3, 4, 9] and occupied size 21
Solution 60:
Bin 0 with items [2, 6, 8, 9] and occupied size 21
Bin 1 with items [0, 1, 7] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 61:
Bin 0 with items [2, 6, 7, 8] and occupied size 21
Bin 1 with items [0, 1, 9] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 62:
Bin 0 with items [5, 6, 8] and occupied size 21
Bin 1 with items [0, 2, 7, 9] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 63:
Bin 0 with items [5, 7, 8, 9] and occupied size 21
Bin 1 with items [0, 2, 6] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 64:
Bin 0 with items [2, 6, 8, 9] and occupied size 21
Bin 1 with items [0, 5, 7] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 65:
Bin 0 with items [2, 4, 5, 8] and occupied size 21
Bin 1 with items [0, 1, 7] and occupied size 21
Bin 2 with items [3, 6, 9] and occupied size 21
Solution 66:
Bin 0 with items [0, 4, 8] and occupied size 21
Bin 1 with items [1, 2, 5, 7] and occupied size 21
Bin 2 with items [3, 6, 9] and occupied size 21
Solution 67:
Bin 0 with items [0, 2, 6] and occupied size 21
Bin 1 with items [5, 7, 8, 9] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 68:
Bin 0 with items [0, 5, 9] and occupied size 21
Bin 1 with items [2, 6, 7, 8] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 69:
Bin 0 with items [0, 2, 6] and occupied size 21
Bin 1 with items [1, 7, 8, 9] and occupied size 21
Bin 2 with items [3, 4, 5] and occupied size 21
Solution 70:
Bin 0 with items [3, 6, 9] and occupied size 21
Bin 1 with items [0, 1, 7] and occupied size 21
Bin 2 with items [2, 4, 5, 8] and occupied size 21
Solution 71:
Bin 0 with items [3, 6, 7] and occupied size 21
Bin 1 with items [0, 1, 9] and occupied size 21
Bin 2 with items [2, 4, 5, 8] and occupied size 21
Solution 72:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [0, 1, 7] and occupied size 21
Bin 2 with items [2, 6, 8, 9] and occupied size 21
Solution 73:
Bin 0 with items [3, 6, 7] and occupied size 21
Bin 1 with items [0, 4, 8] and occupied size 21
Bin 2 with items [1, 2, 5, 9] and occupied size 21
Solution 74:
Bin 0 with items [3, 6, 9] and occupied size 21
Bin 1 with items [0, 4, 8] and occupied size 21
Bin 2 with items [1, 2, 5, 7] and occupied size 21
Solution 75:
Bin 0 with items [3, 6, 9] and occupied size 21
Bin 1 with items [0, 5, 7] and occupied size 21
Bin 2 with items [1, 2, 4, 8] and occupied size 21
Solution 76:
Bin 0 with items [3, 6, 7] and occupied size 21
Bin 1 with items [0, 5, 9] and occupied size 21
Bin 2 with items [1, 2, 4, 8] and occupied size 21
Solution 77:
Bin 0 with items [0, 4, 8] and occupied size 21
Bin 1 with items [3, 6, 9] and occupied size 21
Bin 2 with items [1, 2, 5, 7] and occupied size 21
Solution 78:
Bin 0 with items [0, 4, 8] and occupied size 21
Bin 1 with items [3, 6, 7] and occupied size 21
Bin 2 with items [1, 2, 5, 9] and occupied size 21
Solution 79:
Bin 0 with items [0, 5, 7] and occupied size 21
Bin 1 with items [1, 6, 8] and occupied size 21
Bin 2 with items [2, 3, 4, 9] and occupied size 21
Solution 80:
Bin 0 with items [0, 5, 9] and occupied size 21
Bin 1 with items [1, 6, 8] and occupied size 21
Bin 2 with items [2, 3, 4, 7] and occupied size 21
Solution 81:
Bin 0 with items [5, 6, 8] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [0, 2, 7, 9] and occupied size 21
Solution 82:
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 83:
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 84:
Bin 0 with items [0, 5, 9] and occupied size 21
Bin 1 with items [1, 2, 4, 8] and occupied size 21
Bin 2 with items [3, 6, 7] and occupied size 21
Solution 85:
Bin 0 with items [0, 2, 7, 9] and occupied size 21
Bin 1 with items [5, 6, 8] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 86:
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
Solution 87:
Bin 0 with items [2, 3, 4, 9] and occupied size 21
Bin 1 with items [0, 1, 7] and occupied size 21
Bin 2 with items [5, 6, 8] and occupied size 21
Solution 88:
Bin 0 with items [2, 6, 7, 8] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [0, 5, 9] and occupied size 21
Solution 89:
Bin 0 with items [2, 6, 8, 9] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [0, 5, 7] and occupied size 21
Solution 90:
Bin 0 with items [2, 4, 5, 8] and occupied size 21
Bin 1 with items [3, 6, 7] and occupied size 21
Bin 2 with items [0, 1, 9] and occupied size 21
Solution 91:
Bin 0 with items [2, 6, 7, 8] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [0, 1, 9] and occupied size 21
Solution 92:
Bin 0 with items [2, 6, 8, 9] and occupied size 21
Bin 1 with items [3, 4, 5] and occupied size 21
Bin 2 with items [0, 1, 7] and occupied size 21
Solution 93:
Bin 0 with items [5, 6, 8] and occupied size 21
Bin 1 with items [2, 3, 4, 9] and occupied size 21
Bin 2 with items [0, 1, 7] and occupied size 21
Solution 94:
Bin 0 with items [5, 6, 8] and occupied size 21
Bin 1 with items [2, 3, 4, 7] and occupied size 21
Bin 2 with items [0, 1, 9] and occupied size 21
Solution 95:
Bin 0 with items [3, 6, 9] and occupied size 21
Bin 1 with items [1, 2, 5, 7] and occupied size 21
Bin 2 with items [0, 4, 8] and occupied size 21
Solution 96:
Bin 0 with items [3, 6, 7] and occupied size 21
Bin 1 with items [1, 2, 5, 9] and occupied size 21
Bin 2 with items [0, 4, 8] and occupied size 21
Solution 97:
Bin 0 with items [3, 6, 7] and occupied size 21
Bin 1 with items [1, 2, 4, 8] and occupied size 21
Bin 2 with items [0, 5, 9] and occupied size 21
Solution 98:
Bin 0 with items [3, 6, 7] and occupied size 21
Bin 1 with items [2, 4, 5, 8] and occupied size 21
Bin 2 with items [0, 1, 9] and occupied size 21
Solution 99:
Bin 0 with items [3, 6, 9] and occupied size 21
Bin 1 with items [2, 4, 5, 8] and occupied size 21
Bin 2 with items [0, 1, 7] and occupied size 21
Solution 100:
Bin 0 with items [3, 6, 9] and occupied size 21
Bin 1 with items [1, 2, 4, 8] and occupied size 21
Bin 2 with items [0, 5, 7] and occupied size 21
Solution 101:
Bin 0 with items [2, 6, 7, 8] and occupied size 21
Bin 1 with items [0, 5, 9] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 102:
Bin 0 with items [0, 5, 7] and occupied size 21
Bin 1 with items [2, 6, 8, 9] and occupied size 21
Bin 2 with items [1, 3, 4] and occupied size 21
Solution 103:
Bin 0 with items [0, 5, 7] and occupied size 21
Bin 1 with items [1, 2, 4, 8] and occupied size 21
Bin 2 with items [3, 6, 9] and occupied size 21
Solution 104:
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 105:
Bin 0 with items [3, 4, 5] and occupied size 21
Bin 1 with items [0, 2, 6] and occupied size 21
Bin 2 with items [1, 7, 8, 9] and occupied size 21
Solution 106:
Bin 0 with items [1, 2, 5, 7] and occupied size 21
Bin 1 with items [0, 4, 8] and occupied size 21
Bin 2 with items [3, 6, 9] and occupied size 21
Solution 107:
Bin 0 with items [1, 2, 5, 9] and occupied size 21
Bin 1 with items [0, 4, 8] and occupied size 21
Bin 2 with items [3, 6, 7] and occupied size 21
Solution 108:
Bin 0 with items [5, 7, 8, 9] and occupied size 21
Bin 1 with items [1, 3, 4] and occupied size 21
Bin 2 with items [0, 2, 6] 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 286
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, 1, 4] and occupied size (load) 22
Bin 1 with items [2, 3, 6] and occupied size (load) 20
Bin 2 with items [5, 7, 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()}")
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])}")
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).