2d bin packing using or-tools: AddNoOverlap2D and OnlyEnforceIf gives MODEL_INVALID

Viewed 659

I am playing with a 2d bin packing model. I tried this using:

for j in range(n):
  for i in range(j):
    model.Add(b[i] == b[j]).OnlyEnforceIf(b2[(i,j)])  # not needed?
    model.Add(b[i] != b[j]).OnlyEnforceIf(b2[(i,j)].Not())
    model.AddNoOverlap2D([xival[i],xival[j]],[yival[i],yival[j]]).OnlyEnforceIf(b2[(i,j)])

The purpose here is to only enforce the no-overlap constraint if items i and j are assigned to the same bin. The combination of AddNoOverlap2D and OnlyEnforceIf seems to give the status:

MODEL_INVALID

If I remove OnlyEnforceIf(b2[(i,j)]) the (now incorrect) model solves fine.

Am I correct to conclude this is just not supported in or-tools (yet)?

I guess I can reformulate things to more MIP-like approach.

A reproducible example is below. I used version 8.1.8487.

from ortools.sat.python import cp_model

#---------------------------------------------------
# data 
#---------------------------------------------------


# bin width and height
H = 60
W = 40

# h,w for each item
h = [7,7]
w = [12,12]
n = len(h)  # number of items
m = 2      # number of bins

#---------------------------------------------------
# or-tools model 
#---------------------------------------------------


model = cp_model.CpModel()

#
# variables
#

# x1,x2 and y1,y2 are start and end
x1 = [model.NewIntVar(0,W-w[i],'x1{}'.format(i)) for i in range(n)]
x2 = [model.NewIntVar(w[i],W,'x2{}'.format(i)) for i in range(n)]

y1 = [model.NewIntVar(0,H-h[i],'y1{}'.format(i)) for i in range(n)]
y2 = [model.NewIntVar(h[i],H,'y2{}'.format(i)) for i in range(n)]

# interval variables
xival = [model.NewIntervalVar(x1[i],w[i],x2[i],'xival{}'.format(i)) for i in range(n)]
yival = [model.NewIntervalVar(y1[i],w[i],y2[i],'yival{}'.format(i)) for i in range(n)]

# bin numbers
b = [model.NewIntVar(0,m-1,'b{}'.format(i)) for i in range(n)]

# b2[(i,j)] = true if b[i]=b[j] for i<j
b2 = {(i,j):model.NewBoolVar('b2{}.{}'.format(i,j)) for j in range(n) for i in range(j)}

#
# constraints
#

for j in range(n):
  for i in range(j):
    model.Add(b[i] == b[j]).OnlyEnforceIf(b2[(i,j)])  # not needed?
    model.Add(b[i] != b[j]).OnlyEnforceIf(b2[(i,j)].Not())
    model.AddNoOverlap2D([xival[i],xival[j]],[yival[i],yival[j]]).OnlyEnforceIf(b2[(i,j)])
#    model.AddNoOverlap2D([xival[i],xival[j]],[yival[i],yival[j]])  # this one works


#
# solve model
#
solver = cp_model.CpSolver()
rc = solver.Solve(model)
print(rc)
print(solver.StatusName()) 

Notes:

  • As indicated in the answer, this is just not supported.
  • A different formulation for this 2d bin packing problem is shown here. That seems to work quite well.
  • It is further noted that the pairwise NoOverlap2D formulation may not be a good thing.
1 Answers

If you set solver.parameters.log_search_progress = True you'll see:

Parameters: log_search_progress: true
Enforcement literal not supported in constraint: enforcement_literal: 11 no_overlap_2d { x_intervals: 0 x_intervals: 1 y_intervals: 2 y_intervals: 3 }
...

So yeah, it isn't supported, maybe you can open a feature request as documented here.

But I think you can also solve it using OptionalIntervalVar if you encode the bin number with booleans.

Related