使用分支定界的节点最佳匹配
Best matches of nodes using branch and bound
这个问题的想法是探索无向图的所有节点及其所有邻居。
每个联合都有一个关联的权重。
这个想法是使 最大可能配对 与 最小权重 。
考虑到一旦配对，你不能加入更多。
要使用分支定界实现此算法，我必须找到上限和下限。
我的想法是有一个解决方案列表和一个部分列表，其中我介绍了所有可能的邻居对。
然后比较成本是否少，添加到解决方案列表中。
问题是我不知道用于实现这些界限的启发式方法
有伪代码的想法吗？
此致
编辑
对不起，我留下了如此悬而未决的问题。
让我用一张图来解释这个问题。
在图像中，观察到三个联合。 (1,3), (2,5), (6,4).
这些是最佳联合。
最优解必须满足一对(x,y)的并集的权值最小且"x"和"y"永远不会再匹配
我认为的一个条件是：
return 列表解决方案，如果满足以下条件则包含所有匹配项：
len (G.nodes ()) / 2 == len (solutions)
我使用 贪心算法。
遍历所有节点，加入没有访问过且权重最小的邻居。
但是这样，我不能保证最优。
正如 Abdallah Sobehy 在给您的评论中所写的那样，这更像是一个公开的讨论，而不是一个问题，并且可能（以当前形式）不适合 SE。但是，我会试一试，post 由于它的长度，它在这里而不是在评论中。
对于这个讨论，我们将完整的无向图表示为 G(N, E)，具有节点集和边集 E。我们还假设 G 中的节点数是偶数。
无论如何，在分支定界 (BAB) 的上下文中，你的上限自然是你最好的（最便宜的）现有的（到目前为止）可行的解决方案。这样的解决方案可以在初始化时很容易地启发式构建，例如
i. let G' = G and E'=E
ii. Choose a node, say i, randomly from G'.
iii. With i fixed, pick the edge in (i,j) in E' that minimises cost,
i.e., the cheapest edge from node i to any other node j in G'.
iv. Remove nodes i and j from G', and remove all edges associated
with nodes i and j from E'.
v. Is G' non-empty? Go to ii. Otherwise, terminate.
或者以上的一些更巧妙的变体。得到的可行解就是我们的初始上限，比如UB。
现在，在 BAB 的背景下，人们通常会着眼于原始问题的一种松弛，一种可以轻松求解到最优的问题；与一些整数线性程序 (ILP) 的连续松弛进行比较，以获得使用单纯形法很容易求解到最优的线性程序 (LP)——BAB 的常见用法。
出于我们的目的，我们需要指定一种方法将您的问题放松为易于解决的形式，这种放松形式的最优解的成本低于原始问题的成本；因此为后者提供了一个下限，比如 LB。如果我们用数学术语形式化问题，这会变得容易得多。我们引入二进制变量 x_ij（取值 0 或 1），
x_ij := 1, if pairing between nodes i and j is used, i!=j
0, otherwise
c_ij := cost (or weight) of using edge (i, j), i!=j
其中 i, j = 1, ..., |N|，其中 i!=j。从现在开始，让 n 表示 |N|，即 n=|N|。
有了这个，我们可以将下面的二进制线性规划，比如 (BLP1) 表述为
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ {0, 1}. (c)
“/2”考虑到这一点——采用 objective 函数求和的形式——每对将与两个非零 x_ij 变量相关联（即, 计数两次);如果例如节点 1 和 4 是成对的，x_(1,4)=x_(4,1)=1。 n 个约束 (b) 确保每个节点将与另一个节点完全配对。
这个程序可以通过用它的连续松弛替换二元约束（c）来放宽，即将（c）替换为：
x_ij ∈ [0, 1], (c')
产生以下线性程序，比如 (LP1)，
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1]. (c')
(BLP1) 的解 space 显然是 (LP1) 的子space，因此 (LP1) 的最优解产生 (BLP1) 最优解的下界).由于 (LP1) 是线性程序，因此可以使用您喜欢的任何最喜欢的优化库，通过单纯形法轻松求解。
现在，对于 BAB 过程，求解 (LP1) 并在其最优解中，选择一些分数 x_ij，即一些 x_ij ∈ (0, 1)，我们将- -- 在 (LP1) 的分支子项中 --- 强制执行（上切）或排除（下切）。让我们将此变量表示为 x_ab。在这个 x_ab 变量上分支，w.r.t。图匹配问题，可以描述为："enforce using edge (a,b) with it's full weight (x_ab=1) in subsequent subproblems, or enforce full exclusion of edge (a,b) (x_ab=0) in subsequent subproblems".
x_ab 上的分支产生---从 (LP1)---两个子问题，比如 (LP1down) 和 (LP1up)，形式如下
(LP1down)
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1], (c')
x_ab = 0, (d1)
(LP1up)
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1], (c')
x_ab = 1, (d2)
只需重新解决这些线性规划问题 (LP1down) 和 (LP1up)，并迭代地重复 branch/solve 过程，直到子问题可以被 p运行ed，方法是：
bound: the optimal (linear programming) solution of some sub-problem
is larger than the UB of the original problem (BLP1). This mean
proceeding along such a branch will never give a better (BLP1)
solution than the best incumbent one.
optimality: optimal (linear programming) solution of some sub-problem
is binary valued -> feasible in (BLP1).
-> update UB with new best incumbent solution.
infeasibility: some sub-problem is infeasible; branching upon it will
still yield an infeasible problem.
如果你 运行 你的 BAB 过程直到终止，你将保证最优性（大问题的问题是相当容易处理）。注意，如果节点数为奇数，(BLP1)将不可行。
如果您不想求助于线性规划技术，请尝试构建您自己的方法，将您的原始问题放松为具有以下属性的问题
- 您的原始问题的解决方案 space 是您放松问题的解决方案 space 的子集。
- 您轻松的问题很容易通过某种方式解决，例如启发式。
- 确定 "branching" 在您的上下文中的含义：我建议修复包含或排除节点对。
然后简单地重新使用上面简要介绍的一般 BAB 方法。如果您更深入地研究 BAB，可以通过选择如何选择首先处理哪些子问题 ("node picking") 或选择哪些变量（在正式处理中）分支 ("branching rules") 来改进框架.
这个问题的想法是探索无向图的所有节点及其所有邻居。
每个联合都有一个关联的权重。 这个想法是使 最大可能配对 与 最小权重 。
考虑到一旦配对，你不能加入更多。 要使用分支定界实现此算法，我必须找到上限和下限。
我的想法是有一个解决方案列表和一个部分列表，其中我介绍了所有可能的邻居对。
然后比较成本是否少，添加到解决方案列表中。
问题是我不知道用于实现这些界限的启发式方法
有伪代码的想法吗？
此致
编辑
对不起，我留下了如此悬而未决的问题。 让我用一张图来解释这个问题。
在图像中，观察到三个联合。 (1,3), (2,5), (6,4).
这些是最佳联合。
最优解必须满足一对(x,y)的并集的权值最小且"x"和"y"永远不会再匹配
我认为的一个条件是： return 列表解决方案，如果满足以下条件则包含所有匹配项：
len (G.nodes ()) / 2 == len (solutions)
我使用 贪心算法。
遍历所有节点，加入没有访问过且权重最小的邻居。
但是这样，我不能保证最优。
正如 Abdallah Sobehy 在给您的评论中所写的那样，这更像是一个公开的讨论，而不是一个问题，并且可能（以当前形式）不适合 SE。但是，我会试一试，post 由于它的长度，它在这里而不是在评论中。
对于这个讨论，我们将完整的无向图表示为 G(N, E)，具有节点集和边集 E。我们还假设 G 中的节点数是偶数。
无论如何，在分支定界 (BAB) 的上下文中，你的上限自然是你最好的（最便宜的）现有的（到目前为止）可行的解决方案。这样的解决方案可以在初始化时很容易地启发式构建，例如
i. let G' = G and E'=E
ii. Choose a node, say i, randomly from G'.
iii. With i fixed, pick the edge in (i,j) in E' that minimises cost,
i.e., the cheapest edge from node i to any other node j in G'.
iv. Remove nodes i and j from G', and remove all edges associated
with nodes i and j from E'.
v. Is G' non-empty? Go to ii. Otherwise, terminate.
或者以上的一些更巧妙的变体。得到的可行解就是我们的初始上限，比如UB。
现在，在 BAB 的背景下，人们通常会着眼于原始问题的一种松弛，一种可以轻松求解到最优的问题；与一些整数线性程序 (ILP) 的连续松弛进行比较，以获得使用单纯形法很容易求解到最优的线性程序 (LP)——BAB 的常见用法。
出于我们的目的，我们需要指定一种方法将您的问题放松为易于解决的形式，这种放松形式的最优解的成本低于原始问题的成本；因此为后者提供了一个下限，比如 LB。如果我们用数学术语形式化问题，这会变得容易得多。我们引入二进制变量 x_ij（取值 0 或 1），
x_ij := 1, if pairing between nodes i and j is used, i!=j
0, otherwise
c_ij := cost (or weight) of using edge (i, j), i!=j
其中 i, j = 1, ..., |N|，其中 i!=j。从现在开始，让 n 表示 |N|，即 n=|N|。
有了这个，我们可以将下面的二进制线性规划，比如 (BLP1) 表述为
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ {0, 1}. (c)
“/2”考虑到这一点——采用 objective 函数求和的形式——每对将与两个非零 x_ij 变量相关联（即, 计数两次);如果例如节点 1 和 4 是成对的，x_(1,4)=x_(4,1)=1。 n 个约束 (b) 确保每个节点将与另一个节点完全配对。
这个程序可以通过用它的连续松弛替换二元约束（c）来放宽，即将（c）替换为：
x_ij ∈ [0, 1], (c')
产生以下线性程序，比如 (LP1)，
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1]. (c')
(BLP1) 的解 space 显然是 (LP1) 的子space，因此 (LP1) 的最优解产生 (BLP1) 最优解的下界).由于 (LP1) 是线性程序，因此可以使用您喜欢的任何最喜欢的优化库，通过单纯形法轻松求解。
现在，对于 BAB 过程，求解 (LP1) 并在其最优解中，选择一些分数 x_ij，即一些 x_ij ∈ (0, 1)，我们将- -- 在 (LP1) 的分支子项中 --- 强制执行（上切）或排除（下切）。让我们将此变量表示为 x_ab。在这个 x_ab 变量上分支，w.r.t。图匹配问题，可以描述为："enforce using edge (a,b) with it's full weight (x_ab=1) in subsequent subproblems, or enforce full exclusion of edge (a,b) (x_ab=0) in subsequent subproblems".
x_ab 上的分支产生---从 (LP1)---两个子问题，比如 (LP1down) 和 (LP1up)，形式如下
(LP1down)
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1], (c')
x_ab = 0, (d1)
(LP1up)
minimize ∑{i = 1 to n} ∑_{j 1 to n, j!= i} (c_ij * x_ij)/2, (a)
subject to ∑{j != i} x_ij = 1, for i = 1, ..., n, (b)
x_ij ∈ [0, 1], (c')
x_ab = 1, (d2)
只需重新解决这些线性规划问题 (LP1down) 和 (LP1up)，并迭代地重复 branch/solve 过程，直到子问题可以被 p运行ed，方法是：
bound: the optimal (linear programming) solution of some sub-problem
is larger than the UB of the original problem (BLP1). This mean
proceeding along such a branch will never give a better (BLP1)
solution than the best incumbent one.
optimality: optimal (linear programming) solution of some sub-problem
is binary valued -> feasible in (BLP1).
-> update UB with new best incumbent solution.
infeasibility: some sub-problem is infeasible; branching upon it will
still yield an infeasible problem.
如果你 运行 你的 BAB 过程直到终止，你将保证最优性（大问题的问题是相当容易处理）。注意，如果节点数为奇数，(BLP1)将不可行。
如果您不想求助于线性规划技术，请尝试构建您自己的方法，将您的原始问题放松为具有以下属性的问题
- 您的原始问题的解决方案 space 是您放松问题的解决方案 space 的子集。
- 您轻松的问题很容易通过某种方式解决，例如启发式。
- 确定 "branching" 在您的上下文中的含义：我建议修复包含或排除节点对。
然后简单地重新使用上面简要介绍的一般 BAB 方法。如果您更深入地研究 BAB，可以通过选择如何选择首先处理哪些子问题 ("node picking") 或选择哪些变量（在正式处理中）分支 ("branching rules") 来改进框架.