問題タブ [integer-programming]

したがって、すべての変数が整数で、すべて 3 のような数の倍数である最適なソリューションを持つこの IP を作成しようとしています (したがって、ソリューションの変数は 0、3、6 のいずれかである必要があります)。 、9、12など)

私は R でコーディングしており、解が整数 (all.int = TRUE) でなければならないという制約を設定するのは非常に簡単ですが、それを数値の倍数にする方法がわかりません。Ax <= b 式の中でどのような変更を加える必要がありますか? あなたの助けは大歓迎です! 今のところ、実際にそれを行う方法についてかなり迷っています

R がすべての CPU を使用しているわけではないことに気付きました。これを大幅に (100% まで) 増やしたいと考えています。いくつかの関数を並列化するだけにはしたくありません。R に CPU リソースをもっと使ってもらいたい。lp() 関数を使用して純粋な IP セット パッキング プログラムを実行しようとしています。現在、私は Windows を実行しており、コンピューターには 4 つのコアがあります。

Snow、doParallel、および foreach を試してみました (実際に何をしているのかはわかりませんが)。

私のコードではこれを持っています...

R が動かなくなり、lp() を長時間実行します。私の CPU は約 25% ですが、どうすればこれを増やすことができますか?

整数計画法を使用して、パレート最適解を列挙したいと考えています。これを行うために gurobi または同様の単​​目的整数計画法ソルバーを使用するアルゴリズムを実装したいと思いますが、そのようなアルゴリズムは知りません。誰かが効率的なフロンティアを列挙するためのアルゴリズムを提案してくれませんか?

複数の答えを持つ可能性のある MILP を解こうとしています (すべて目的関数に同じ値が与えられます)。分岐限定アルゴリズムはすべての解を見つけることができますか?

MATLAB を使用して (たとえば intlinprog を使用して)、そのような MILP のすべてのソリューションを見つけることは可能ですか?

ありがとうございました。

gurobi と networkx を使用して、これを Python にコーディングしようとしています。

S >= quicksum(N の j の場合は uij) N のすべての i について

私のコードは

問題は、エッジ (1,1) を持っていないので理にかなっている Key Error (1,1) を取得することです

しかし、ノード内のすべての i について合計したいのですが、特定のノード i に接続されているすべての j のすべての uij の合計です。

これは度数の問題ではなく、実際には連結成分を合計しているため、i と j の間に経路がある場合、uij は 1 です。これをクリティカル ノード検出問題としてコーディングしました。

助けてください！ありがとう！

質問：

最小化x1+x2+...+xn

知られているk1*x1+k2*x2+...kn*xn = T

k1,k2,...,knおよびTは既知の整数であり、> 0

k1 > k2 > k3 > ... > kn

すべての x も整数で >= 0

すべての x を見つける

Rglpk と Glpk を使用しようとしていました。しかし、行列が 1 行しかない例が見つかりません。これは整数計画法ですか？そして、それは解決可能ですか？どうもありがとう。

私が書いたいくつかの Ruby コード:

混合整数計画法モデルを構築しており、決定変数の最小値と mzximum を定義したいと考えています。

たとえば、C={19, 20, 30} としましょう

C_early を 19 に、C_late を 30 に定義したいと思います。次に、差を最小限に抑えたいと思います。C_late 部分は補助制約を使用して正常に定義されましたが、min 部分に何かが欠けていると思います。

ここに私のコードがあります:

最後の 3 つの制約は、私の質問に関連しています。

データセットの例:

min 制約に big m メソッドを使用する必要があることはわかっていますが、どうすればよいかわかりません ありがとう、

私は写真を持っており、エッジ エネルギーの特定の割合を同時に保持する最小限の領域でクロップを見つけたいと考えています。

これに対する私の見解は、これを最適化問題として定式化し、scipy の制約付きオプティマイザーに解決させることでした [コードは以下を参照]。これは整数の問題であるため、明らかに問題があります(クロッピングは左上隅と右下隅の整数座標をパラメーターとして受け取ります)。実際fmin_cobyla、実行時間の約 20 秒後に解決策を見つけることができませんが、 「 LSQ サブ問題の特異行列 C (終了モード 6)fmin_slsqp 」で 1 回の反復後に失敗します。

そうでなければ、この問題にどのように取り組むかについてのアイデアはありますか? 画像の最適化問題を処理するライブラリはありますか?