整数計画法で最小化を行うことは非常に複雑な問題であることを理解しています。しかし、何がこの問題をそれほど難しくしているのでしょうか？
それを解決するためのアルゴリズムを（試みて）書くとしたら、何を考慮に入れる必要がありますか？私はそれを解決するための分枝限定法に精通しているだけであり、この技術をプログラムで適用しようとすると、どのような障害に直面するのだろうかと思っています。
4 に答える
4
この手法をプログラムで適用しようとすると、どのような障害に直面するのでしょうか。
特にありません（多くのトリックがなく、かなり単純な実装を想定しています）。アルゴリズムは複雑ではありません-それらは複雑です、それは根本的な違いです。
分枝限定法や分枝限定法などの手法では、検索ツリーを整理して、実行時間を短縮しようとします。しかし、それでも問題ツリー全体は指数関数的に大きいため、問題が発生します。
于 2011-09-05T12:46:29.113 に答える
2
他の人が言ったように、それらの問題は非常に難しく、すべてのクラスの問題に適用される単純な解決策も単純なアルゴリズムもありません。
これらの問題を解決する「古典的な」方法は、質問で言うように、分枝限定法を実行し、各ノードでシンプレックスアルゴリズムを適用することです。ただし、専門家でない場合は、これを自分で実装することはお勧めしません。
多くの数値解法に関しては、それを正しくすることは非常に困難であり（適切なパラメーター値、適切な最適化）、多くのことが行われています（CPLEX、COIN_ORなどを参照）。
それができないわけではありません。分枝限定法はかなり単純ですが、すべてのトリックがないと、プログラムは非常に遅くなります。
また、シンプレックスの実装が必要になりますが、これは自分でやりたいことではありません。とにかく、サードパーティのlibを使用する必要があります。
おそらく、
- データセットがそれほど大きくなく（試してみてください！）、それを本当に速く解決することに興味がない場合は、デフォルトのメソッドでCOIN-ORやlp_solveなどを使用してください。
- データセットが非常に大きい場合（および/または毎回迅速に解決策を見つける必要がある場合）、この分野の専門家と協力する必要があります。
私の主なポイントは、経験豊富な人々だけが、どのアルゴリズムが問題に対してより優れたパフォーマンスを発揮するか、どの形式のモデルが最も簡単に解決できるか、どの方法を適用するか、どのような最適化を試すことができるかを知っているということです。
これらの問題に興味がある場合は、このすべての背後にある数学の紹介としてこの本をお勧めします（多くの例があります）。それは信じられないほど広大なので、購入する代わりに図書館に行きたいと思うかもしれません：ネムハウザーとウォルシー。
于 2011-09-06T09:09:53.080 に答える
0
数理最適化問題を解く前に最初に行うことは、それを分類することです。特別な場合を除いて、ほとんどの場合、整数計画問題はnp困難になります。したがって、「アルゴリズム」を使用する代わりに、「ヒューリスティック」を使用します。あなたが見つける最終的な解決策は、保証された最適ではありませんが、それは実際の問題のためのかなり良い解決策になるでしょう。
あなたの主な障害はあなたのプログラミングスキルになります。ヒューリスティックプログラミングには、プログラミングを十分に理解している必要があります。したがって、独自のヒューリスティックをプログラミングする代わりに、よく知られたパッケージ（COIN-OR、無料など）を使用する方が適切です。このようにして、ヒューリスティックではなく問題に集中できます。
于 2011-09-05T13:51:44.560 に答える