集合划分问题

集合划分问题决定了如何将一个集合 (S) 中的项目划分为更小的子集。S 中的所有项目必须且只能包含在一个分区中。相关问题包括：

设置打包 - 所有项目必须包含在零个或一个分区中；
集合覆盖 - 所有项目必须至少包含在一个分区中。

在这个案例研究中，婚礼策划师必须为婚礼确定宾客的座位分配。为了建模这个问题，桌子被建模为分区，而被邀请参加婚礼的宾客被建模为集合 S 的元素。婚礼策划师希望最大化所有桌子的总幸福感。

一个集合划分问题可以通过显式枚举每个可能的子集来建模。尽管这种方法在处理大量项目时会变得难以处理（如果不使用列生成），但它有一个优点，即划分目标函数的系数可以是非线性表达式（如幸福感），并且仍然可以使用线性规划来解决这个问题。

首先，我们使用 allcombinations() 来生成所有可能的餐桌座位列表。

# create list of all possible tables
possible_tables = [tuple(c) for c in pulp.allcombinations(guests, max_table_size)]

然后我们创建一个二进制变量，如果表格将在解决方案中，则该变量为1，否则为零。

# create a binary variable to state that a table setting is used
x = pulp.LpVariable.dicts(
    "table", possible_tables, lowBound=0, upBound=1, cat=pulp.LpInteger
)

我们创建 LpProblem 然后制定目标函数。注意，此脚本中使用的幸福函数用其他方式建模将非常困难。

seating_model = pulp.LpProblem("Wedding Seating Model", pulp.LpMinimize)

seating_model += pulp.lpSum([happiness(table) * x[table] for table in possible_tables])

我们指定解决方案中允许的表格总数。

# specify the maximum number of tables
seating_model += (
    pulp.lpSum([x[table] for table in possible_tables]) <= max_tables,
    "Maximum_number_of_tables",
)

这组约束通过确保每位客人恰好被分配到一个桌子来定义集合划分问题。

# A guest must seated at one and only one table
for guest in guests:
    seating_model += (
        pulp.lpSum([x[table] for table in possible_tables if guest in table]) == 1,
        f"Must_seat_{guest}",
    )

完整的文件可以在这里找到 wedding.py

"""
A set partitioning model of a wedding seating problem

Authors: Stuart Mitchell 2009
"""

import pulp

max_tables = 5
max_table_size = 4
guests = "A B C D E F G I J K L M N O P Q R".split()


def happiness(table):
    """
    Find the happiness of the table
    - by calculating the maximum distance between the letters
    """
    return abs(ord(table[0]) - ord(table[-1]))


# create list of all possible tables
possible_tables = [tuple(c) for c in pulp.allcombinations(guests, max_table_size)]

# create a binary variable to state that a table setting is used
x = pulp.LpVariable.dicts(
    "table", possible_tables, lowBound=0, upBound=1, cat=pulp.LpInteger
)

seating_model = pulp.LpProblem("Wedding Seating Model", pulp.LpMinimize)

seating_model += pulp.lpSum([happiness(table) * x[table] for table in possible_tables])

# specify the maximum number of tables
seating_model += (
    pulp.lpSum([x[table] for table in possible_tables]) <= max_tables,
    "Maximum_number_of_tables",
)

# A guest must seated at one and only one table
for guest in guests:
    seating_model += (
        pulp.lpSum([x[table] for table in possible_tables if guest in table]) == 1,
        f"Must_seat_{guest}",
    )

seating_model.solve()

print(f"The chosen tables are out of a total of {len(possible_tables)}:")
for table in possible_tables:
    if x[table].value() == 1.0:
        print(table)