摘要：集合划分问题（Set Partitioning Problem）是一种组合优化问题，其中给定一个集合S和其若干个不同的子集S1，S2，...，Sn后，需要找到子集的有效组合，使得集合S的每个元素正好出现在一个子集中，并且所选择的子集的组合成本最小。这个问题可以被建模为一个0-1整数线性规划问题，其中引入了一个0-1变量向量，用于表示是否选择子集。通过对变量和约束条件的定义，可以找到最优的子集划分方案，以最小化成本。集合划分问题在学术研究中被广泛应用于制定调度计划、运输计划、生产计划等领域，以解决实际问题并优化资源利用。

集合划分问题是一个NP-hard问题。使用传统的计算机算法来解决这个问题时，所需的时间将随着问题规模变大呈指数级增长。因此，对于大规模的问题，需要使用更高效的算法、近似算法或其他有效的工具来解决。

在场景应用上，如许多组织中的人员调度和排班、计划时刻表，除了启发式算法外，近年来集合划分优化方法变得更加流行。由于在实际情况中生成的优化模型非常大，因此开发了多种计算技术来有效地制定解决方案。例如生成具有超过650个约束和200,000个二进制变量的集合划分模型，这些技术经常用于解决航空公司应用程序中产生的多种问题。

同时，它在分析多智能体系统中的合作方面也发挥着重要作用。例如为了优化社会福利，找到一个将主体划分为联盟（联盟结构）的方法，使分区中联盟的价值总和最大化。通过组建联盟，自主传感器可以改善对某些区域的监管；绿色能源发电机可以减少其预期能源输出的不确定性；认知无线电网络可以增加其吞吐量；买家可以通过批量采购获得更便宜的价格......

问题描述

集合划分问题是组合优化中的一类经典问题，该问题是指已知一个集合和其若干子集，如何选择子集，使原集合的每个元素出现且仅出现在一个子集中（这些子集恰好构成原集合的一个划分），并且所选择的子集的成本之和最小。

首先给出集合划分的整数规划模型

其中xj为0/1变量，表示是否选择子集j，cj是选择子集j的成本，aij系数表示元素i是否出现在子集j中。

建模思路

我们可以将该模型直接转化为如下QUBO形式。

我们用下面的例子来进一步分析。

该案例可以转为如下数学模型：

s.t.

对于这样的问题，我们一般需要引入惩罚系数𝑃构建二次惩罚项并将其添加到原始目标函数中，以建立QUBO模型，则模型可以调整为式（5）。

我们取P=10，同时根据x2=x（x为0/1变量）的特性，我们可以化简式子得到式（6）

舍去常数项后，我们得到QUBO模型的矩阵表达：

其中Q矩阵为：

求解这个QUBO模型，我们可以得到最优解x1=x5=1，x2=x3=x4=x6=0，得到y=6。即选择子集1（{1,4}）和子集5（{2,3}），集合划分最小成本为6。

问题拓展

集合划分问题是组合优化中的一个经典问题，和该问题类似的还包括集合覆盖问题（Set Covering Problem）和集合包装问题（Set Packing Problem）。需要区别的是，集合覆盖问题和集合包装问题的在式（1）中的约束为不等式约束，集合覆盖问题为“≥”，集合包装问题为“≤”。集合划分问题在数学、计算机科学、物理学等领域都有应用，其应用包括图像处理、数据挖掘、网络优化等。

参考文献

[1] Glover, Fred, Kochenberger, Gary, Du, Yu. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models[J]. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies,2019,17(4):335-371. DOI:10.1007/s10288-019-00424-y.

[2] Garfinkel R S, Nemhauser G L. The set-partitioning problem: set covering with equality constraints[J]. Operations Research, 1969, 17(5): 848-856.

[3] Lewis M, Kochenberger G, Alidaee B. A new modeling and solution approach for the set-partitioning problem[J]. Computers & Operations Research, 2008, 35(3): 807-813.

 

 

摘要：集合划分问题（Set Partitioning Problem）是一种组合优化问题，其中给定一个集合S和其若干个不同的子集S1，S2，...，Sn后，需要找到子集的有效组合，使得集合S的每个元素正好出现在一个子集中，并且所选择的子集的组合成本最小。这个问题可以被建模为一个0-1整数线性规划问题，其中引入了一个0-1变量向量，用于表示是否选择子集。通过对变量和约束条件的定义，可以找到最优的子集划分方案，以最小化成本。集合划分问题在学术研究中被广泛应用于制定调度计划、运输计划、生产计划等领域，以解决实际问题并优化资源利用。

集合划分问题是一个NP-hard问题。使用传统的计算机算法来解决这个问题时，所需的时间将随着问题规模变大呈指数级增长。因此，对于大规模的问题，需要使用更高效的算法、近似算法或其他有效的工具来解决。

在场景应用上，如许多组织中的人员调度和排班、计划时刻表，除了启发式算法外，近年来集合划分优化方法变得更加流行。由于在实际情况中生成的优化模型非常大，因此开发了多种计算技术来有效地制定解决方案。例如生成具有超过650个约束和200,000个二进制变量的集合划分模型，这些技术经常用于解决航空公司应用程序中产生的多种问题。

同时，它在分析多智能体系统中的合作方面也发挥着重要作用。例如为了优化社会福利，找到一个将主体划分为联盟（联盟结构）的方法，使分区中联盟的价值总和最大化。通过组建联盟，自主传感器可以改善对某些区域的监管；绿色能源发电机可以减少其预期能源输出的不确定性；认知无线电网络可以增加其吞吐量；买家可以通过批量采购获得更便宜的价格......

问题描述

集合划分问题是组合优化中的一类经典问题，该问题是指已知一个集合和其若干子集，如何选择子集，使原集合的每个元素出现且仅出现在一个子集中（这些子集恰好构成原集合的一个划分），并且所选择的子集的成本之和最小。

首先给出集合划分的整数规划模型

其中xj为0/1变量，表示是否选择子集j，cj是选择子集j的成本，aij系数表示元素i是否出现在子集j中。

建模思路

我们可以将该模型直接转化为如下QUBO形式。

我们用下面的例子来进一步分析。

该案例可以转为如下数学模型：

s.t.

对于这样的问题，我们一般需要引入惩罚系数𝑃构建二次惩罚项并将其添加到原始目标函数中，以建立QUBO模型，则模型可以调整为式（5）。

我们取P=10，同时根据x2=x（x为0/1变量）的特性，我们可以化简式子得到式（6）

舍去常数项后，我们得到QUBO模型的矩阵表达：

其中Q矩阵为：

求解这个QUBO模型，我们可以得到最优解x1=x5=1，x2=x3=x4=x6=0，得到y=6。即选择子集1（{1,4}）和子集5（{2,3}），集合划分最小成本为6。

问题拓展

集合划分问题是组合优化中的一个经典问题，和该问题类似的还包括集合覆盖问题（Set Covering Problem）和集合包装问题（Set Packing Problem）。需要区别的是，集合覆盖问题和集合包装问题的在式（1）中的约束为不等式约束，集合覆盖问题为“≥”，集合包装问题为“≤”。集合划分问题在数学、计算机科学、物理学等领域都有应用，其应用包括图像处理、数据挖掘、网络优化等。

参考文献

[1] Glover, Fred, Kochenberger, Gary, Du, Yu. Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models[J]. 4OR: Quarterly Journal of the Belgian, French and Italian Operations Research Societies,2019,17(4):335-371. DOI:10.1007/s10288-019-00424-y.

[2] Garfinkel R S, Nemhauser G L. The set-partitioning problem: set covering with equality constraints[J]. Operations Research, 1969, 17(5): 848-856.

[3] Lewis M, Kochenberger G, Alidaee B. A new modeling and solution approach for the set-partitioning problem[J]. Computers & Operations Research, 2008, 35(3): 807-813.