OR-tools物品容器分配：实现强制子集包含约束的技术问询

问题背景 #

需要用OR-Tools实现物品到容器的分配逻辑，三个约束中前两个已完成，第三个约束（容器必须包含预定义子集列表中的至少一个完整子集）需要补充实现，要求直接在CP模型中添加约束，禁止事后过滤解，且需生成所有符合条件的解。

核心实现思路 #

对于每个有义务子集的容器，核心逻辑是必须满足至少一个子集的所有物品都被分配到该容器。通过以下步骤实现：

• 为每个子集创建辅助布尔变量，标记该子集是否被完整包含在容器中；
• 建立辅助变量与物品分配变量的关联：当子集所有物品都在容器时，辅助变量为真；反之则为假；
• 约束容器的所有辅助变量中至少有一个为真，确保满足子集要求。

修改后的完整代码 #

from ortools.sat.python import cp_model


class SolutionPrinter(cp_model.CpSolverSolutionCallback):

    def __init__(self, x, containers, items):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__x = x
        self.containers = containers
        self.items = items

    def on_solution_callback(self):
        print({container: [item for item in self.items if self.BooleanValue(self.__x[container, item])] for container in self.containers})


# 每个容器的物品数量（总和等于总物品数）
sizes = [5, 3, 4]

# 物品可分配的容器列表（item索引对应子列表，子列表中True表示可分配到对应容器）
possibilities = [[False, True, False],
                 [True, False, False],
                 [True, False, True],
                 [True, True, True],
                 [True, False, True],
                 [True, False, False],
                 [True, False, False],
                 [True, True, False],
                 [False, False, True],
                 [False, True, True],
                 [False, False, True],
                 [True, True, True]]


# 容器必须包含的预定义子集列表
obligations = {0: [[1, 2, 3],  # 容器0必须包含(1,2,3)或(5,6,7)的完整子集
                   [5, 6, 7]],
               1: [],          # 容器1无此约束
               2: [[2, 3, 4],
                   [8, 9],
                   [9, 10, 11]]}


num_containers = len(sizes)
num_items = sum(sizes)
model = cp_model.CpModel()

# 定义变量：x[container, item]为True表示物品item分配到容器container
x = {}
for container in range(num_containers):
    for item in range(num_items):
        x[container, item] = model.NewBoolVar(f"x[{container},{item}]") if possibilities[item][container] else False

# 约束1：每个物品必须被分配到恰好一个容器
for item in range(num_items):
    model.AddExactlyOne(x[container, item] for container in range(num_containers))

# 约束2：每个容器的物品数量固定
for container in range(num_containers):
    model.Add(sum(x[container, item] for item in range(num_items)) == sizes[container])


# 约束3：每个容器必须包含至少一个预定义子集
for container, subsets in obligations.items():
    if not subsets:
        continue  # 跳过无约束的容器
    subset_vars = []
    for subset in subsets:
        # 创建辅助变量，标记当前子集是否被完整包含在容器中
        subset_included = model.NewBoolVar(f"subset_{container}_{subset}")
        # 关联辅助变量与物品分配：子集全在容器时，辅助变量为真
        model.Add(sum(x[container, item] for item in subset) == len(subset)).OnlyEnforceIf(subset_included)
        # 辅助变量为假时，子集至少有一个物品不在容器
        model.Add(sum(x[container, item] for item in subset) < len(subset)).OnlyEnforceIf(subset_included.Not())
        subset_vars.append(subset_included)
    # 约束容器至少满足一个子集要求
    model.AddAtLeastOne(subset_vars)


solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(x, range(num_containers), range(num_items))
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, solution_printer)

代码说明 #

1. 辅助变量创建：为每个容器的每个预定义子集生成一个布尔变量，用于标记该子集是否被完整分配到容器；
2. 变量关联约束：通过OnlyEnforceIf实现双向约束，确保辅助变量的取值与子集物品的分配状态严格一致；
3. 子集满足约束：使用AddAtLeastOne确保容器至少满足一个子集的完整包含要求，直接在模型层面限制解的范围，避免事后过滤不符合条件的解。

内容的提问来源于stack exchange，提问作者Betcha