Bin packing in OR-Tools with only one bin

Question

I've been trying to adapt the bin-packing problem often seen in OR-Tools to optimize space used instead of optimizing number of bins, but I don't seem to be able to sort out how to do it.

So what I want to do is something like:

Given a set of 2D boxes of various sizes, and an arbitrarily long 2D container of fixed width, how tightly can we pack all the boxes?

At first glance, it seems like a decent solution to this problem would be to define variables like:

x1 = [model.NewIntVar(0,L-l[i],f'x1{i}') for i in range(n)]
x2 = [model.NewIntVar(l[i],L,f'x2{i}') for i in range(n)]

Where L is the maximum container length and l[i] is the length of the ith box, for n boxes.

Then do something similar with the heights, with H as the container height and h[i] as the height of the box.

Then I can get the area of each box with:

a = [model.NewConstant(h[i]*w[i]) for i in range(n)]

Define some intervals for the lengths and widths:

xinv = [model.NewIntervalVar(x1[i],w[i],x2[i],f'xinv{i}') for i in range(n)]
yinv = [model.NewIntervalVar(y1[i],h[i],y2[i],f'yinv{i}') for i in range(n)]

And a restriction that the boxes can't overlap:

model.AddNoOverlap2D(xinv,yinv)

At first glance, it looks like I should be able to use a strategy like:

• Get the x-coordinate of the box that's furthest from the back of the container
• Use that to define a square containing all boxes placed so far (the other sides of the square are the top, bottom, and back of the container)
• Add up the area of all the boxes
• Subtract that from the square
• That result is the area of the empty space not filled by boxes
• Set an objective to minimize that empty space

The square can be defined by using model.AddMaxEquality to set a variable to the maximum distance that a box reaches. However, I'm stuck on the "add up the areas of all the placed boxes" part. There doesn't seem to be a way to look back and get the coordinates of previously placed boxes, even though it's possible to determine where those boxes were placed to enforce the AddNoOverlap2D constraint.

How do I calculate a total of the area of boxes currently in the container?

Answer 1

1. use FixedSizeIntervalVar.
2. you know all objects packed, the total area is fixed. You just need to minimize the max end coordinate.
3. for inspiration, you can have a look at https://github.com/google/or-tools/blob/stable/examples/cpp/binpacking_2d_sat.cc

The idea is to have one large box with one dimension fixed, and a variable one (whose length is the objective).

Then you add to all rectangles on that dimension:

rectangle_end <= objective

And finally

model.minimize(objective)