2

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

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

该模型基本上是一长串变量和约束。你可以把它想象成试图在不同的枢纽（国家）之间寻找最便宜的乘客运输方式，每个国家对乘客的需求最小，乘客的供应最大，每个连接都有价格。我不在乎乘客去哪里，我只想找到最便宜的方式来分配他们。为了实现这一点，我使用以下最小化目标：

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

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

亲切的问候，谢谢。G。

4

3 回答 3

4

听起来好像您遇到了最低成本流量问题。Zealint有一个看起来很合理的关于最小成本流的 TopCoder 教程，他介绍了我的第一个建议的循环取消算法（假设没有可以为您的 LP 求解器进行的快速优化）。如果这仍然太慢，那里有一个完整的文献。

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

于 2015-04-02T13:27:20.717 回答
3

@Noobster，我很高兴我以外的其他人正在使用我的单工库。我经历了，看了看，和你一样的运行时间（10-20秒）。有一段代码不必要地转置数组以将 RHS 从 2d 数组转换为 1d 数组。对于您的问题，这会杀死性能，每次发生时都会消耗 60 毫秒（对于您的问题，137 次）。

我已经在 repo 中更正了这个问题，并且看到运行时间大约为 2 秒。可能需要进行大量这样的代码清理优化，但我构建的问题集（http://mathfood.com）是如此之小，以至于我从来不知道这是一个问题。谢谢！

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

于 2015-04-02T18:08:37.320 回答
2

弄清楚了。代码中最昂贵的部分是旋转操作。事实证明，通过添加 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];
                }
            }
        }
    }
于 2015-04-14T22:18:52.607 回答