加速单纯形算法

Question

我正在使用我在这里找到的一个很棒的单纯形算法：https://github.com/JWally/jsLPSolver/

我创建了一个 jsfiddle，我在其中设置了一个模型，并使用上面的算法解决了问题。 http://jsfiddle.net/Guill84/qds73u0f/

该模型基本上是一长串变量和约束。您可以将其视为试图在不同的枢纽（国家）之间寻找最便宜的乘客运输方式，其中每个国家对乘客的需求最低，乘客的最大供应，并且每个连接都有一个价格。我不在乎乘客去哪里，我只想找到最便宜的方式来分配他们。为此，我使用以下最小化 objective:

model = {
        "optimize": "cost",
            "opType": "min",
            "constraints": { \etc...

我对算法提供的模型和答案感到满意...但是后者需要很长时间才能运行（> 15秒...）有什么可能的方法我可以加快计算速度？

谨致问候，谢谢。 G.

Answer 1

听起来好像您有 Zealint 的 minimum-cost flow problem. There's a reasonable-looking TopCoder tutorial on min-cost flow，他介绍了循环取消算法，这将是我的第一个推荐（假设没有可以为您的 LP 求解器完成的快速优化）。如果那仍然太慢，那里有完整的文献。

由于您决定使用 LP 求解器解决此问题，我的建议是编写一个更简单的求解器，该求解器快速且贪婪但次优，并通过将 LP 表示为将其用作 LP 的起点与起点的差异。

Answer 2

@Noobster，我很高兴除我之外的其他人正在使用我的单纯形库。我经历了，看着它，并且得到了与你相同的运行时间（10 - 20 秒）。有一段代码不必要地转置数组以将 RHS 从二维数组转换为一维数组。对于您的问题，每次发生时都会消耗 60 毫秒的性能（对于您的问题，137 次）。

我已在存储库中更正此问题，发现运行时间约为 2 秒。可能需要进行大量这样的代码清理优化，但我构建这个 (http://mathfood.com) 的问题集太小了，我从来不知道这是一个问题。谢谢！

为了它的价值，我从大学教科书中取出了单纯形算法并将其转化为代码； MILP 的文章来自维基百科。

Answer 3

想通了。代码中最昂贵的部分是旋转操作；事实证明，通过添加 0 来更新矩阵需要做很多工作。预先做一些逻辑来防止这将我的运行-节点上的时间从 ~12 秒减少到 ~0.5。

    for (i = 0; i < length; i++) {
        if (i !== row) {
            pivot_row = tbl[i][col];
            for (j = 0; j < width; j++) {


                // No point in doing math if you're just adding
                // Zero to the thing


                if (pivot_row !== 0 && tbl[row][j] !== 0) {
                    tbl[i][j] += -pivot_row * tbl[row][j];
                }
            }
        }
    }

加速单纯形算法

Speed up simplex algorithm

javascript

arrays

algorithm

mathematical-optimization

simplex