整数線形計画法 (ILP) を使用して問題の解決策を実装しようとしています。問題は NP 困難であるため、Simplex Method によって提供されるソリューションが最適かどうか疑問に思っていますか? シンプレックス法を使用したILPの最適性についてコメントしたり、ソースを指摘したりできますか。ILP 問題に最適なソリューションを提供できる他のアルゴリズムはありますか?
編集:ILPのアルゴリズム(シンプレックス法、分岐および境界および切断面)のいずれかによって得られたソリューションの最適性に対するyes/noの答えを探しています。
シンプレックス法は、整数が必要であるという制約を処理しません。結果を単純に丸めるだけでは、最適解が得られるとは限りません。
シンプレックス法を使用して ILP 問題を解くことは、制約行列が完全双対積分の場合に機能します。
ILP (完全な双対積分制約行列に制約されない) を解く一部のアルゴリズムはBranch and Boundです。これは実装が簡単で、コストが合理的に均一である場合に一般的にうまく機能します (非常に不均一なコストにより、有望に見える多くの試みが試行されます)。最初はそうではないことが判明しました)、そして私は正直あまり知りませんが、人々が使用しているのでおそらく良い切断面です。
線形計画問題の解セットは、定義上最適です。
線形計画法は、「制約充足」として知られるアルゴリズムのクラスです。制約を満たせば、問題を解決したことになり、「より良い」解決策はありません。これは、定義上、最良の結果は制約を満たすことであるためです。
ただし、問題を完全にモデル化していない場合は、他のタイプのソリューションの方が明らかに優れている可能性があります。
明確化：上記の「制約を満たす」と書くとき、目的関数の最大化を含めています。切断面アルゴリズムは、本質的にシンプレックス アルゴリズムの拡張です。