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.