問題タブ [linear-programming]

Linuxで整数プログラムを解決するための優れたツールはありますか？

時間を節約するために計算したい小さな問題があります：D。これは一種の部分和問題です。約20個の整数値のリストがあり、特定の最小値を満たす最小の合計でサブセットを計算したいと思います。あなたは整数計画法でこれを定式化することができます...のようなもの

と

または、これを行う他の良い方法はありますか？

線形計画法モデルを作成する必要があります。私が使用している不等式は次のとおりです（たとえば）：

これらの不等式で表される領域を見つけ、グラフで影を付け、この領域の境界線の頂点を追跡し、境界線を別の色で描画する必要があります。私が探しているものの例については、下のグラフを参照してください。

.

Python 3.2、numpy、matplotlib を使用しています。Python での線形計画法のより良いモジュールはありますか?

これが実際に割り当て/線形プログラミングの問題であるのと同じくらい「色付け」の問題であるかどうかはわかりません。私はどちらの専門知識も持っていません。しかし、この問題は以前にほぼ確実に解決/調査されたにちがいないと感じています。私は正しい方向へのいくつかの指針を得ることを望んでいました。

「問題文」は事実上次のように要約されます。

1. グラフには、ルーターとコアの 2 種類の頂点があります。

2. コアはルーターのみに接続されます。各コアは、SINGLE ルーターにのみ接続されます。そして、それぞれにユーザーが入力/定義した「色」があります。（私の特定の問題では、色は4/5の可能な色の1つに制限されています）。それらの色は変更できません。これは入力パラメーターです。(コアは下の画像の四角です)

3. ルーターは、他のルーターと同様にコアに接続されます。それらには「色」が割り当てられていません。色を割り当てることは、プログラム/アルゴリズムの目的の一部です。(ルーターは、下の画像の円形の頂点です。)

4. プログラムの目的は、異なる色の頂点間の「交差点」/エッジの数が最小限になるように、グラフ内の各ルーターに色を割り当てることです。

(別の見方: 基本的に、いくつかの頂点が色付けされ、他の頂点は色付けされていないグラフが与えられます。目的は、異なる色の頂点間のエッジの数が最小になるように、色付けされていない頂点に色を付けることです。)

これを整数線形プログラムとして定式化することができました（かなり不十分だと思います）、LP-Solveを使用してソリューション/アプローチをセットアップしました。私も独自のヒューリスティックを持っています。これを解決するための「適切な」/既知の/他のアプローチを知りたいですか?!

どうもありがとう！

私は、目的関数がmaxそれぞれの係数を掛けた決定変数から余分な重みを追加する線形計画法を設定しようとしています。

これを念頭に置いて、線形計画法の目的関数内でminまたはmax演算子を使用する方法はありますか？

例：

(c4 * max(c1*x1, c2*x2, c3*x3))それが私が懸念している「余分な重量」の用語であることに注意してください。「余分c4な重み」係数を示します。また、この特定の例では、、、およびは整数x1であることに注意してください。x2x3

上記は線形計画法が提供する範囲外かもしれないと思います。しかし、おそらくこれをハック/再フォーマットして有効な線形計画法にする方法はありますか？

この問題が完全に線形計画法の範囲外である場合、おそらく誰かがこのタイプの問題により適した最適化パラダイムを推奨できますか？（すべての可能な解決策を手動で列挙してチェックすることを回避できるものなら何でも役に立ちます。）

私は集合I={P1、P2、...、Pm}を持ち、次のようにR1、R2、...、Rnで表されるIのn個の有限部分集合を持っています。

R1 = {P1、P2}

R2 = {P2、P4}

R3 = {P2、P3、P4}

R4 = {P1、P2、P4}

...。

ここで、円周率は整数を示します。

Riごとに、そのすべての要素の積を計算したいと思います。私の目的は、Ri（i = 1,2、...、n）間でいくつかの共通部分を共有することにより、乗算と除算をできるだけ少なくすることです。

たとえば、最初にP2 * P4を計算できる場合、この結果はR3とR4のすべての要素の積を計算する際に使用できます。

除算も許可されていることに注意してください。たとえば、最初にA = P1 * P2 * P3 * P4を計算し、次にA / P1を使用してR3のすべての要素の積を計算し、R4にA/P3を使用できます。

最小の乗算と除算を使用して、Iのすべてのサブセットのすべての積を計算したい場合、それは集合被覆問題ですか？NP完全？ところで、ここのようにそれを記述するために整数線形計画法の定式化を与えることができますか？

どんな提案でも大歓迎です！

コミュニティ編集：追加の仮定：

• 乗算と同じコストで、除算が許可されます
• 特定のセットに繰り返される要素はありません。例：R5 = {P1, P1, P1, P2}許可されていません

それぞれn個の要素を持つ3つのセットA、B、Cが与えられます。これらのセットには重複が含まれている可能性があります（セットが正しい用語であるかどうかは不明です）。

今、私はn個の要素（たとえばD1からDn）で集合Dを形成しようとしています。各要素Diには、Aから、Bから、Cからの3つの要素が含まれています。

私の目的は、Diの要素の積の合計を最小化する集合Dを見つけることです。

ここではブルートフォースはかなり悪い考えのようです。n>5の場合でも、アルゴリズムの速度がかなり遅くなるためです。誰かがより良いアプローチを提案できますか？線形計画法はこの問題に適していますか？

次のコードがあります。

どこ：

Demandベクトルでなければならないのに行列のようです。これをベクトルに変換し、同じ要素を同じ「場所」に保持するにはどうすればよいですか?

また、行列連結はこれを行うための最良の方法ですか? データセット全体の最適値x1と値を見つけようとしています。x2

こんにちは私はlinprog最適化のために次のコードを持っています。

ここで、WT_outputとPV_outputは3次元の365x24配列であり、Demandは365x24です。

最適なKとMの組み合わせを見つけるために、Demandの365x24要素のそれぞれと各ディメンションのx1とx2を最適化しようとしています。

ただし、現在のコードでは、「Aの行数はbの要素数と同じである必要があります」というエラーが発生し続けます。

誰か提案はありますか？

こんにちは、linprogを使用した次のコードがあります

ここで、PV = 8760x2、WT = 8760 x 2、x = 2x1 です。このプログラムを実行すると、最適化は終了フラグ 1 で収束しますが、x1 =0 の値と特定の整数に等しい x2 の値のどちらかが得られます。

出力が結果の混合を与えないのはなぜですか (つまり、x1 と x2 の両方の非ゼロ値?

「添え字代入の次元が一致しません。」linprog コーディングを実行するとき。

私のコードは

PV_output は 8760x1x27 で、WT_output は 8760x1x3 です

このコードで 27 と 3 の PV と WT のすべての組み合わせについて、以下の「f」係数を見つけようとしています。「f」にインデックスを付ける方法を知っている人はいますか?

ありがとうございました