使用 or-tools 进行 2d 装箱：AddNoOverlap2D 和 OnlyEnforceIf 给出 MODEL_INVALID

Question

我正在玩二维装箱模型。我尝试使用：

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)])

这里的目的是仅在项目 i 和 j 分配到同一个 bin 时才强制执行无重叠约束。 AddNoOverlap2D 和 OnlyEnforceIf 的组合似乎给出了状态：

MODEL_INVALID

如果我删除 OnlyEnforceIf(b2[(i,j)])（现在不正确的）模型可以很好地求解。

我得出的结论是 or-tools 不支持（还）吗？

我想我可以重新制定更类似于 MIP 的方法。

下面是一个可重现的例子。我用的是 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())

备注：

正如答案中所指出的，这是不受支持的。
显示了此 2d 装箱问题的不同公式 here。这似乎工作得很好。
进一步指出，成对 NoOverlap2D 公式可能不是一件好事。

Answer 1

如果您设置 solver.parameters.log_search_progress = True，您将看到：

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 }
...

是的，它不受支持，也许您可以按照记录打开功能请求 here。

但我认为如果您使用布尔值对 bin 编号进行编码，您也可以使用 OptionalIntervalVar 来解决它。

使用 or-tools 进行 2d 装箱：AddNoOverlap2D 和 OnlyEnforceIf 给出 MODEL_INVALID

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

or-tools