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

Question

这是我在这些论坛上的第一篇帖子，在此先感谢所有回复。

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

基本上，我想做的是编写最有效的方法来找到具有变量 v1、v2、v3 等的较大集合 N 的最优子集 n。除了取决于某些其他变量的值/分数，这些变量可能包含也可能不包含在子集中。

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

因此，例如，完整集合 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

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

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

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