0

私のバイナリプログラミングの問題は次のとおりです。

max: (a1 * x1) + (a2 * x2) + ..... + (an * xn)

対象:

(c1 * x1) + (c2 * x2) + ..... + (cn * xn) < C

n = 10

a1, ... an, c1, ... cn, C are known

x1, ... xn are binary

これは、プロセス タスクの割り当ての問題です。私の場合、バイナリ/整数プログラミングの問題を解決するためのオーバーヘッドは、非常に小さくする必要があります (< 1 ミリ秒)。これを CBC ソルバー / lpsolve で実行すると、2 ミリ秒から 7 ミリ秒の時間がレポートされます。SCIP/Gurobi を持っていません。これをミリ秒未満で解決する方法はありますか? これを 1 ミリ秒未満で解決できると期待するのは理にかなっているように思えますか?

（私はCBCでprintfを無効にしました。しかし、他にスタックしているシステム操作があるかどうかはわかりません....それが書き込んでいるログファイル）

4

1 に答える 1

0

これは、動的計画法を使用して効率的に解くことができる標準的なナップザック問題です。これは、 knapsack wikiで適切に議論されています(また、複数のスタック オーバーフローの投稿でも議論されています。たとえば、ここではDP algo for knapsackおよび here recursive knapsack ) 。

C++ 実装は、私のコア i7 @3Ghz で ~20us を測定します

于 2015-05-02T10:33:32.520 に答える