線形計画法 (LP) の問題の凸包をどのように定式化して積分することができますか? これを実行するための一般的な手法はありますか?
2 に答える
3
定式化という意味では、線形計画法は (一般に) 分数の極値点を持つ多面体を生成します。この問題を正確に解決したい場合、多面体で変更/操作するものは何もありません。
(混合) 整数線形計画法 (MIP) を使用している場合は、その整数点の凸包の記述に興味があるかもしれません。一般に、これは高速な解法プロセスに使用できます。後で分岐限定プロセスを実行せずに線形緩和を解くことができるからです。
これは、MIP の線形緩和により、この凸包を含む多面体が得られることを意味し、それ自体は整数の極値を持つ必要はありません。多くの場合、この定式化を整数点の凸包に近づける必要があります。これは、通常のソルバーによって行われます (たとえば、不等式を追加することによって)。目的は常に、前記凸包の定式化を得ることです。ただし、この定式化を見つけることは一般に NP 困難です (したがって、それを簡単に取得するための既知の一般的な手法はありません)。特に、これは、そのような定式化のサイズ (つまり、不等式の量) が指数関数的になり得ることを意味します。
これらは、整数点の (または一般的な多面体からの) 凸包を計算するアルゴリズムですが、単純ではなく、「高速」でもありません。そこに役立つソフトウェアは、おそらくPortaまたはPolymakeです。
多面体/定式化が整数である場合を説明するプロパティがあります。たとえば、これらのうちの 1 つは、完全な (デュアル) ユニモジュール性という名前で呼ばれます。このような方法で問題を定式化したり、このプロパティを特定したりすることは簡単ではなく、そうするための構造的なアプローチを知りません.
これが役立つことを願っています:)
敬具、
マーティン
于 2014-02-26T10:14:27.970 に答える
1
上記のマーティンの回答に少し追加するには（これはコメントするには長すぎると思います）：
私が知っている、Chvátal-Gomorry 手順と呼ばれる一般的な手順があり、Gomorry カットを追加することで凸包を最終的に記述することができます。これは理論的に非常に興味深いものです。
nただし、この手順が2 つの変数と 2 つの制約を持つ問題に対してステップ (LP のパラメーター) を実行するよく知られた例があります。つまり、追加されるカットの数は問題のサイズによって制限されません。完全ユニモジュラー行列は、グラフ理論で発生する問題では一般的ですが、それは確かに「一般的な」方法では
Aありません。TU 行列では、行列の係数が 0、1、または -1 でなければならないという定義だけで、自分自身を納得させることができます。もちろん、これは通常 ILP には当てはまりません。
もちろん、LP を解くことは多項式であり、ILP を解くことは NP 完全であるため、ILP を LP にほぼ還元するため、期待どおりの一般的な効率的な方法があるとは期待できません。
しかし、特定の問題を研究している場合、特に構造が単純な場合は、上記の 2 つの方法のいずれかが有効な「特殊なケース」の 1 つになる可能性があります。
興味があれば、週末に追加のリファレンスを提供できます。
于 2014-02-27T08:26:39.650 に答える