时间戳

首页 > 解决方案 > 检查分配的元素是否满足 OR-Tools 中的条件

or-tools - 检查分配的元素是否满足 OR-Tools 中的条件

问题描述

我有 100 个元素要分配给 10 个位置。

# the elements list holds 100 variables that signify the assignment to a spot
elements = [model.NewIntVar(1, 10) for i in range(100)]

我的每个元素都有特定的大小。现在我想为每个点建模一个（一组）约束，它说：分配给这个点的所有元素的添加大小位于固定范围内。

因此，如果点 1 分配了元素 1、16 和 64，它们的大小是 1521、1732、1431，而我的范围是 (3000, 6000)，那就没问题了。但是如果太多或太大的元素（或太少/太小）被分配到点 1，那就不行了。

类似于以下内容，但不起作用：

for spot in range(10):
    sum_ = sum([get_size(e) for e in elements if e == spot]) # if think if e == spot is what fails
    model.Add(sum_ >= 3000)
    model.Add(sum_ <= 6000)

我怎样才能为这样的东西建模？我已经查看了通道约束，但我无法完全理解它。

标签： or-tools

解决方案

我认为最好将作业建模为布尔值：

from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()

all_spots = range(10)
all_elems = range(100)
elements = {
    (elem, spot): model.NewBoolVar(f"{elem} in spot {spot}")
    for elem in all_elems
    for spot in all_spots
}

# only one spot for element
for elem in all_elems:
    model.Add(sum(elements[elem, spot] for spot in all_spots) == 1)

for spot in all_spots:
    # taking the element id as its size
    sum_ = sum(elements[elem, spot] * elem for elem in all_elems)
    model.Add(sum_ >= 0)
    model.Add(sum_ <= 500)

solver.Solve(model)

for (elem, spot), boolean in elements.items():
    if solver.Value(boolean):
        print(boolean)

看：

推荐阅读