具有相互依赖变量的组合优化

Question

这是我第一次 post 在这些论坛上，在此先感谢所有回复。

我正在开发一个 java 应用程序，我在其中遇到了我认为称为“组合优化问题”的问题。我只有基本的数学技能，所以尝试研究这样一个问题的设置到目前为止还没有成果。

基本上，我想做的是编写最有效的方法来找到具有变量 v1、v2、v3 等的较大集合 N 的最优子集 n。变量都有明确的 value/score 除了依赖于某些其他变量的 value/score 之外，这些变量可能包含也可能不包含在子集中。

我有兴趣选择给出最大总数的子集 value/score。

因此，例如，完整集合 N 由以下变量组成，并具有以下确定值以及与其他变量的关系：

v1  8   { v2 ; v8 }
v2  6   { v1 ; v4 }
v3  9   { }
v4  7   { v2 ; v5 ; v8 }
v5  6   { v4 ; v10 }
v6  8   { v7 }
v7  5   { v6 }
v8  9   { v1 ; v4 }
v9  6   { } 
v10 7   { v5 }

与一个或多个其他选定变量有关系意味着总值将有一定的“起飞”——为了这个例子，我们假设每个关系都有一个。因此，选择前五个变量作为子集，总值为 30:

v1  8   { v2 ; v8 }      = 8 - 1 = 7
v2  6   { v1 ; v4 }      = 6 - 2 = 4
v3  9   { }              = 9 - 0 = 9
v4  7   { v2 ; v5 ; v8 } = 7 - 2 = 5
v5  6   { v4 ; v10 }     = 6 - 1 = 5

对于这么小的集合当然不是问题，但是我现在面对的是100K的集合和10K的子集——用现在的算法，我的电脑3天就算出来了！

我不一定需要代码来解决这个问题，而是需要最佳的数学方法（如果有的话！）。请记住，我很难理解基本水平以上的数学符号。

再次感谢所有回复！

Answer 1

您可以将您的集合显示为图表。每个 vX 都是具有相应值的 node/vertice。示例 v1 是一个值为 8 的 node/vertice，v2 是一个值为 6 的 node/vertice，等等。然后它们之间有边。示例 v1 有 2 条边：一条用于 v2，另一条用于 v8。每条边也可以有一个值（在您的情况下为 -1）。

所以如果你使用图，select v1 到 v5：你有 8 + 6 + 9 + 7 + 6（顶点值）-1 -1 -1 -1 -1 -1（边值）。

尝试查看此 http://jgrapht.org/ 看看是否对您有帮助。

另见一些图论：http://www.people.vcu.edu/~gasmerom/MAT131/graphs.html. Observe Longest/Shortest Path algoritms (example: http://www.maxburstein.com/blog/introduction-to-graph-theory-finding-shortest-path/)

Answer 2

不幸的是，这个问题是 NP 难找到最优解。

如果你能有效地解决这个问题，那么你就可以解决 NP-hard maximum independent set problem 通过将每个顶点的值设置为 1，并对每条边设置一个非常大的惩罚。

因此您应该寻找近似解。您可能会发现使用模拟退火或遗传算法可以得到合理的答案。

Answer 3

对于线性程序求解器，输入像

v1  8   { v2 ; v8 }
v2  6   { v1 ; v4 }
v3  9   { }
v4  7   { v2 ; v5 ; v8 }
v5  6   { v4 ; v10 }
v6  8   { v7 }
v7  5   { v6 }
v8  9   { v1 ; v4 }
v9  6   { }
v10 7   { v5 }

并将其转换为整数程序，如

maximize   8*v1 - v1v2 - v1v8
         + 6*v2 - v2v1 - v2v4
         + 9*v3
         + 7*v4 - v4v2 - v4v5 - v4v8
         + 6*v5 - v5v4 - v5v10
         + 8*v6 - v6v7
         + 5*v7 - v7v6
         + 9*v8 - v8v1 - v8v4
         + 6*v9
         + 7*v10 - v10v5

subject to
v1 + v2 - v1v2 <= 1
v1 + v8 - v1v8 <= 1
v2 + v1 - v2v1 <= 1
v2 + v4 - v2v4 <= 1
v4 + v2 - v4v2 <= 1
v4 + v5 - v4v5 <= 1
v4 + v8 - v4v8 <= 1
v5 + v4 - v5v4 <= 1
v5 + v10 - v5v10 <= 1
v6 + v7 - v6v7 <= 1
v7 + v6 - v7v6 <= 1
v8 + v1 - v8v1 <= 1
v8 + v4 - v8v4 <= 1
v10 + v5 - v10v5 <= 1

binary v1, v1v2, v1v8,
       v2, v2v1, v2v4,
       v3,
       v4, v4v2, v4v5, v4v8,
       v5, v5v4, v5v10,
       v6, v6v7,
       v7, v7v6,
       v8, v8v1, v8v4,
       v9,
       v10, v10v5

您的实例大小对于最佳解决方案来说可能太大了，但谁也不知道...

具有相互依赖变量的组合优化

Combinatorial optimization with interdependent variables

java

algorithm

mathematical-optimization

combinatorics