追加制約付き線形代入

Question

標準線形代入問題では、ハンガリーアルゴリズムを使用してO（n^3）を実現できます。追加の制約が追加されるとどうなりますか？例：4剤と

"通常" LAPは、制約行列

を有し、ベクトルb = [1 1 1 1]を生じます。

ハンガリーアルゴリズムは、このような問題を解決します。しかし、別の制約は、制約行列は、結果ベクトルb = [1 1 1 1 0]と

なるように添加されたものならば？ある

は、離れて標準の線形和の制約の下で費用関数を最小化することから、私はまた、この合計は、上記添付行列の最後の行を生成

ような制約を考慮しなければなりません。明らかに、結果として生じる制約マトリクスはもはや完全に単峰ではない。もちろん、標準のMILPはこれを解決しますが、NP困難です。私の質問は、多項式時間にこのLAPを解くハンガリーのようなアルゴリズムですか？

Answer 1

一般に、サイド制約のあるネットワークフローの問題はNP-Hardです。例えば、負でないエッジコストを伴う最短経路問題は、多項式で解決可能である。たとえば、Dijkstraの最短経路アルゴリズムを使うことができます。

ただし、使用するエッジの数がある定数より小さくなければならないという制約を1つ追加すると、それに続く制限された最短パスの問題はNPになります（NPが問題になります）。 -ハード。

したがって、問題に多項式アルゴリズムがあることはほとんどありません。