不等式のシステムを解決するには？

Question

問題（テーブルレイアウトアルゴリズム）を次の問題に減らしました：

N個の変数X ₁ 、X ₂ 、...、X _N があるとします。また、次のような（未定の）不等式がいくつかあります。

X ₁ ＆gt; = 2
x ₂ + X ₃ ＆gt; = 13
など。

各不等式は1つ以上の変数の合計であり、＆gt; =演算子を使用して常に定数と比較されます。毎回どのくらいの不等式を持つかを事前に言うことはできませんが、すべての変数は非負でなければならないので、それはすでに変数ごとに1つです。

変数の値が可能な限り小さくなるようにこのシステムを解決する方法？

追加：ウィキペディアの記事を読んで、変数が整数でなければならないことを忘れていたことに気付きました。これがNP困難になると思いますか？

Answer 1

xiが線形制約を満たすx1 + x2 + ...の最小化は、線形計画法と呼ばれます。詳細については、 Wikipedia

で詳しく説明しています。

Answer 2

あなたが持っているものは、かなり基本的な線形プログラミングの問題です。方程式 X_1 + ... + X_n を最大化する

X_1 >= 2
X_2 + X_3 >= 13
etc.

この種の問題を解決するアルゴリズムは数多くあります。最もよく知られているのは、シンプレックスアルゴリズムです。シンプレックスアルゴリズムが解決するために指数関数的に多くのステップを必要とするLP問題が存在しますが、平均的なケースです（問題サイズで）。

LPソルバーのさまざまな実装が存在します。たとえば、 LP_Solve は、ほとんどの要件を満たす必要があります

Answer 3

線形モデルをNEOSプラットフォームに直接投稿することもできます（ http：/ /neos.mcs.anl.gov/neos/solvers/index.html ）。最初に行う必要があるのは、AMPLなどの代数言語でモデルを書くことです。 NEOSはモデルを解決し、結果を電子メールで返します。

Answer 4

線形プログラミング