2

私はここで見つけた素晴らしいシンプレックス アルゴリズムをいじっています: https://github.com/JWally/jsLPSolver/

モデルを設定したjsfiddleを作成し、上記のアルゴリズムを使用して問題を解決しました。http://jsfiddle.net/Guill84/qds73u0f/

モデルは基本的に、変数と制約の長い配列です。これは、異なるハブ (国) 間の乗客の最も安い輸送手段を見つけようとするものと考えることができます。ここで、各国には乗客の最小需要、乗客の最大供給があり、各接続には価格があります。乗客がどこに行くかは気にしません。ただ、乗客を最も安く配布する方法を見つけたいだけです。これを達成するために、次の最小化目標を使用します。

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

モデルとアルゴリズムによって提供される答えに満足しています...しかし、後者は実行に非常に長い時間がかかります(> 15秒...)計算を高速化する方法はありますか?

よろしくお願いします。G.

4

3 に答える 3

3

@Noobster、私以外の誰かが私のシンプレックスライブラリを利用していることを嬉しく思います。私はそれを見て、あなたと同じランタイム（10〜20秒）を過ごしていました。RHS を 2 次元配列から 1 次元配列に変換するために配列を不必要に転置するコードがありました。あなたの問題では、これが発生するたびにパフォーマンスが60ミリ秒消費されました（あなたの問題では、137回）。

私はレポでこれを修正し、約 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 に答える