整数规划算法 [英] Integer Programming Algorithm

问题描述

寻找vb中最快的算法来解决以下问题：



set1 [] = {299,104,4,38,60，-2,2 }

set2 [] = {f（1），f（2），f（3），f（4），f（5），f（6），f（7）}

找到sumproduct（set1，set2）= 93

其中f（n）在{-1,0,1}



我用Excel的求解器（单纯形式）解决了这个问题，但它很慢，我在循环几十个类似的问题。

Looking for the fastest algorithm in vb to solve the following:

set1[ ] = {299, 104, 4, 38, 60, -2, 2}
set2[ ] = {f(1), f(2), f(3), f(4), f(5), f(6), f(7)}
find sumproduct(set1, set2) = 93
where f(n) in {-1, 0, 1}

I've solved this using Excel's solver (simplex), but it's slow and I'm looping through dozens of similar problems.

推荐答案

其实有没有太多的线性编程算法（LP）。整数编程（IP）实际上是一个子集，使用单纯形或其他通用方法是一种选择，但可能不是最好的。尽管如此，Excel甚至不是一个强大的LP / IP工作的好工具。有几种工具可供选择（参见一个好的列表： http://en.wikipedia.org/wiki/List_of_optimization_software [ ^ ]） - 一些免费的（如这个 [ ^ ]），一些商业广告（如此 [ ^ ]）。现在，如果你真的不必，不要试图自己实现它 - 特别是在VB中。 图书馆 [ ^ ]你最终可以使用。

但我建议你使用一个或另一个现有软件。



更新：你发布的问题很特殊，因为你不想优化，你只想为线性方程找到一种特殊的解决方案。例如，您可以使用一些heuristik违约和绑定方法。

甚至更简单：你只有3 ^ 7 = 2187种可能性来检查，这根本不是很多。您需要一个简单的级联计数器算法来生成所有组合。

Actually there are not too many algorithms for linear programming (LP). Integer programming (IP) is actually a subset, and using simplex or other general method is one option, but might not be the best. Still, Excel is even less a good tool for an intensive LP/IP job. There are several tools out there meant for this (see a good list: http://en.wikipedia.org/wiki/List_of_optimization_software[^]) - some free (like this[^]), some commercial (like this[^]). Now, if you don't really have to, don't try to implement it on your own - especially not in VB. There are libraries[^] you could eventually use.
But I suggest you use one or the other existing software.

Update: the problem you posted is special, since yo don't want to optimize, you just want to find a special kind of solution for a linear equation. You could use some heuristik breach-and-bound method for example.
Or even simpler: you have only 3^7=2187 possibilities to check, that is not much at all. You need a simple cascading counter algorithm to generate all combinations.

这篇关于整数规划算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！