The importance of redundant constraints: Modeling a Bin-Packing

What makes CP really fun is that modeling is an art and you have to understand (or at least have a good feeling) of how the propagation will behave when you write a model.
Detractors of CP will say it's a weakness, Pascal Van Hentenryck will say that "CP is a smart tool for smart people" ;-)
When I wrote 5 years ago my second CP model (first one was n-queens) it was the Balanced Academic Curriculum Problem (BACP).
I started to read the paper "Modelling a balanced academic curriculum problem" (CPAIOR2002) by Brahim Hnich , Zeynep Kiziltan and Toby Walsh. The experiments in this paper show that the problem is really difficult (they cannot prove optimality with an hybridization of CP and MIP).
In reality this problem is not difficult for CP but like many problems, it has bin-packing component and you have to model it correctly. I understood this when I read the very good paper of Paul Shaw: "A Constraint for Bin Packing" (CP2004).

A bin packing constraint implies some sized items that you must place into some capacitated bins. So you have one variable for each item that tells you in which bin you place the item and one variable for each bin telling you how loaded is the bin. A ground instance is bin-packing([1,2,1,3],[3,4,1,5],[4,4,5]) with 5 items placed in bins [1,2,1,3] with sizes [3,4,1,5] so that the load of bins 1,2,3 are [4,4,5].

A model for this constraint in google cp-solver is the following:

def BinPacking(cp, binvars, weights, loadvars):
'''post the load constraint on bins.

constraints forall j: loadvars[j] == sum_i (binvars[i] == j) * weights[i])
'''
for j in range(len(loadvars)):
  b = [cp.IsEqualCstVar(binvars[i], j) for i in range(len(binvars))]
  cp.Add(cp.ScalProd(b, weights) == loadvars[j])
cp.Add(cp.SumEquality(loadvars, sum(weights)))

For all bins j, you say that the load is equal to the sum of the weights of items placed into that bin j. This is enough to model the semantic of the constraint but not enough for the pruning. It is very important to add the redundant constraints that the sum of the load variables is equal to the sum of the total size of the items. If you don't do that, there is not communication between the bins in the cp store. Consider this example to realize this:

You have 5 items with size (6,5,5,4,4,4,2) to place into three bins with capacity 10. There is clearly a solution: (5,5) in bin one, (4,4,2) in bin two and (6,4) in the third one. Assume now that you have a partial solution where one item of 5 and one item of 4 is placed into bin one. Clearly this partial solution cannot lead to a final solution since you know that the bins must be completely packed at the end (30 units to place and three bins with capa 10). Unfortunately you can see that the first bin cannot be packed completely with this partial solution. Interestingly this inconsistency can only be detected with the redundant constraint "the sum of the load variables = sum of the total size". Indeed, the load of bin 1 is at most 9, and the load of bins 2 and 3 is at most 10 so at most the total load will sum to 29, which is smaller than 30 => fail!

Now if you want to experiment (like the authors of the first BACP model) how difficult BACP is without this redundant constraint, you can comment the redundant constraint in the google-solver cp model available here

If you don't forget the redundant constraint, you'll solve the problem in 68ms and 1000 failures with a default first fail heuristic. In conclusion this problem is trivial for CP and I hope if you read this that you will never forget to post this redundant constraint to model a bin-packing like me 5 years ago ;-)

Note that this problem has been generalized to be more realistic here. I think this new problem is now challenging for CP.