ortools cp-sat: 2d bin packing considering items length, width and weight

Question

I'm trying to solve a 2d bin packing problem having a container = (20,10,30) and a list of boxes = [(2,3,4), (4,3,2), ...] where in the first position there is the length, in the second the width and in the third the weight capacity for the container and the weight for the boxes.

I'm using as source the code in cpsat-primer but it only considers the length and width. For convenience I report the variable definition here:

# We have to create the variable for the bottom left corner of the boxes.
# We directly limit their range, such that the boxes are inside the container
x_vars = [
    model.NewIntVar(0, container[0] - box[0], name=f"x1_{i}")
    for i, box in enumerate(boxes)
]
y_vars = [
    model.NewIntVar(0, container[1] - box[1], name=f"y1_{i}")
    for i, box in enumerate(boxes)
]
# Interval variables are actually more like constraint containers, that are then passed to the no overlap constraint
# Note that we could also make size and end variables, but we don't need them here
x_interval_vars = [
    model.NewIntervalVar(
        start=x_vars[i], size=box[0], end=x_vars[i] + box[0], name=f"x_interval_{i}"
    )
    for i, box in enumerate(boxes)
]
y_interval_vars = [
    model.NewIntervalVar(
        start=y_vars[i], size=box[1], end=y_vars[i] + box[1], name=f"y_interval_{i}"
    )
    for i, box in enumerate(boxes)
]
# Enforce that no two rectangles overlap
model.AddNoOverlap2D(x_interval_vars, y_interval_vars)

My goal is to compute the bin packing such that the weight capacity of the vehicle is not exceeded.

What I've tried to do is to define a bool varible for each box, add a constraint to limit the weight, and add an objective function as follows:

z_vars = [model.NewBoolVar(f"z_{i}") for i in range(len(boxes))]
model.Add(sum(z_vars[i] * box[2] for i, box in enumerate(boxes))<= container[2])

box_areas = [box[0]*box[1] for box in boxes]
model.Maximize(sum(z_vars[i] * box_areas[i] for i in range(len(boxes))))

The problem with this approach is that, despite the weight constraint, at each box is already assigned a (x,y) position, resulting in a solution like the one reported in the following image.

What I would like to achieve is that the (x,y) position is assigned to only the boxes that satisfy the weight constraint.

Thank you in advance for your help!

Answer 1

1. you have missed the binpacking part. Each item can only appear in one box. Thus you need optional intervals.

2. Once this is done, for each bin, you can add

    sum(presence_boolean * weight_of_item) <= max_weight

I suggest you look at the complete example: https://github.com/google/or-tools/blob/main/examples/cpp/binpacking_2d_sat.cc