Originally posted by: __foo_

Hi IBM,

This issue's been bugging me for quite a while. I'm working on a variant of the bin packing problem, which can be described as below:

Problem description:
Given a number of identical items; item size is presented by a 4-dimensional vector. Given a number of bins of different sizes; bin size is presented by a 4-dimensional vector. Due to allocation constraints, an item can only be assigned to some specific pre-defined bins. An item must not exceed the remaining size of the bin and can be allocated to at most one bin. Try to put items into bins so that the number of allocated items is maximum.

Approach&Challenge:
I'm using CP Optimizer with Python to solve this problem. With 8 items and 35 bins, the program worked just fine and fast, optimal solution achieved. However, with 32 items and 85 bins, the program was running forever. I could find an optimal solution in this case if I use Mathematical Programming (MP) instead of Constraint Programming (CP) Modeling. The reason I'm using CP is that later on, I will add a non-linear objective, which MP doesn't support.

Question:
Does someone know why CP optimizer taking so long and still not able to find an optimal solution even for this seemingly small-scale scenario? I suspected that CP might not be the right tool for this problem.

Source code&data:
My Python program and sample data (sample data set 1: 32 items/85 bins; set 2: 8 items/35 bins) can be found here https://github.com/PhuLai/sample-cp-optimizer

Your help is very appreciated. Thanks very much,
Foo

Originally posted by: Petr Vilím

Hello,

I was not able to run your example, there seems to be decimal numbers (such as 0.5) in set1-items.txt file and the program expects integers.

Anyway, looking at the way the model is created, it is a MIP-style model. I.e. there is a boolean variable saying "is this item assigned to this container". In CP the usual way is to have a integer variable saying "into what container this item belongs". It quite reduces the number of variables. If some items may remain unassigned then there could be an auxiliary bin that is big enough to contain everything.

CP Optimizer has a constraint specifically designed for bin packing, it is called pack:

http://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html#docplex.cp.modeler.pack

Since pack has a global view on the problem it can propagate more then many simple arithmetic constraints. Your bins are 4-dimensional therefore you will need a pack constraint for each dimension.

I hope it hels, Petr

Originally posted by: __foo_

Thanks Petr, that helped a lot. Very appreciate it!

Using pack constraint speeded up the model significantly. However, it found no solution although there was an optimal solution. I have updated the source code (bin-packing-variant-v1.py), any ideas what went wrong with my implementation?

Thanks

Originally posted by: Petr Vilím

Hello,

it seems that you're trying to compute the "load" parameter of pack constraint yourself and in a wrong way. The pack constraint computes it for you, you just have to provide variables that should be filled with the computed load (or constants if you require the load to be a constant value). I.e. lets assume pack(load, where, size) then this pack constraint is an equivalent of the following set of constraints:

load[0] == (where[0]==0)*size[0] + (where[1]==0)*size[1] + (where[2]==0)*size[2] + ...

load[1] == (where[0]==1)*size[0] + (where[1]==1)*size[1] + (where[2] ==1)*size[2] + ...

load[2] == (where[0]==2)*size[0] + (where[1]==2)*size[1] + (where[2]==2)*size[2] + ...

It seems that you are doing this computation yourself in the loads_d and constrain each load_d by bin.size. Instead you can just create variables with range 0..bin.size and pass them directly to pack constraint. The pack constraint will make sure that value of each variable will be equal to the load computed as above.

Here is a documentation for pack constraint in cpo file format manual that could help you: there is an example of a model that does the same thing as pack constraint does (without actually using pack). Similar to what I wrote above.

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.8.0/ilog.odms.cpo.help/CP_Optimizer/reffileformatcpo/functions/pack.html

Best regards, Petr

Originally posted by: __foo_

Understood, thanks a lot. My model is now working!

However, it's still being very slow (try with set 1 or 2, has 32 items and 97 bins). Looking at the search log, there was no improvement after the first few attempts. How can I terminate the search early and still guarantee an optimal solution?

EDIT: I tried setting OptimalityTolerance to 0.5 but the program was still running nonstop.

Originally posted by: Petr Vilím

I think the problem is in the objective function. It is:

(whereItem0==0) + (whereItem0==1) + (whereItem0==2) + ...

+ (whereItem1==0) + (whereItem1==1) + (whereItem1==2) + ...

+ (whereItem2 == 0) + (whereItem2==1) + (whereItem2==2) + ...

Try to replace that by:

(whereItem0 != nb_bins)

+ (whereItem1 !=nb_bins)

+ ...

I.e. change:

nb_allocated_items = mdl.sum([(wheres[int(item.id)] == int(bin.id)) for bin in bins[0:nb_bins] for item in items])

 to:

nb_allocated_items = mdl.sum([(wheres[int(item.id)] != nb_bins) for item in items])

Best regards, Petr

Originally posted by: __foo_

Brilliant! The model is lighting fast now. Thanks very much for your help, I really appreciate it.

Originally posted by: __foo_

It's me again.

So the first objective was to maximize the number of allocated items. Now I'm adding the second objective: maximize the product of the number of items assigned to each bin:

               maximize x_1 * x_2 + ... * x_n   where x is the number of items assigned to bin 1, 2, ..., n

I have some issues with different size of data:

- 32 or 64 items: the model was running non-stop. Any idea why?
- 128, 256, or 512 items: the model run quite fast but the second objective value was off (1.79769e+308 for all of those 3 data sizes). I guess it has something to do with how CP Optimizer handles big integer. Is that the case, and how can I handle it?

I tested the model on a small dataset (8 items) and the results looked correct.

Thanks a lot for your help.

(Sample data and source code updated on Github)

Originally posted by: PhilippeLaborie

- if the model is not stopping it means that it is still trying to improve the solution or prove the optimality of the current solution. you should set a limit (typically a TimeLimit) to make sure that the engine stops at some point and provides the best solution found so far (even if it could not prove it is an optimal one)

- instead of minimizing the product which may indeed result in huge numbers exceeding the capacity of the integer representation, I would suggest to minimize a numerical expression that is the sum of the log of the number of items.

Philippe

Originally posted by: __foo_

Thanks for the reply.

- I need to find the optimal solution so terminating the search early won't be applicable in my problem. It's strange that smaller data size tends to take longer.

- Sum of the log of the number of items was what I was trying to do initially, but it was not stopping as well (I thought because the log makes things complicated) so I had to try maximizing the product. 

Integers are unlimited in size and have no maximum value in native Python since they use an arbitrary length integer implementation. I guess this isn't the case for CP Optimizer then, I somehow believe there must be a way to handle it in CPO.

Thanks a ton.