問題タブ [pulp]

整数線形計画法モデルの目的関数の考案に取り組んでいます。目標は、2 つの遺伝子のコピー数と、遺伝子変換イベントが発生したかどうかを判断することです (一方のコピーが他方によって上書きされ、一方が削除されたように見えますが、正味のコピー数は変化していません)。

P_Aこの問題には、との 2 つのデータ ベクトルが含まれますP_B。ベクトルには、各位置で作成されたコピー数の尺度に対応するゼロより大きい連続値が含まれています。位置は各コピーに固有であるため (ゲノム内の絶対位置にマッピングできるため)、P_{A,i}必ずしも遺伝子全体で同じスポットであるとは限りません。P_{B,i}

これを考慮して、私の計画は、決定変数と異なるゲノム ウィンドウで測定されたデータとの差を最小限に抑えることを試み、同じ領域に対応する 2 つのデータ ベクトルの異なるスライスを提供することでした。

決定変数:

目標は、以下の方程式の左辺と右辺の差を最小限に抑えることです。

次のようないくつかの制約があります。2 <- A_w + B_w <= 4

しかし、これを最小化する関数に定式化する方法がわかりません。実際には関数ではない 2 つの方程式があり、決定変数には係数がありません。

の負の値を処理する方法もわかりませんC_w。

また、結果を元に戻す方法もわかりません。各ウィンドウで LP を解いた後、それを 1 つの遺伝子全体の呼び出しにマージする必要があります (理想的には、どのウィンドウがC_w.

COIN-OR の CBC ソルバーを使用して、いくつかの数値最適化問題を解決しています。PuLP を介して Python で最適化問題を構築しています。

GUROBI や CPLEX などのソルバーがログ ファイルを作成することに気付きましたが、(オプティマイザーの進行状況を画面に出力するのではなく) CBC にログ ファイルを作成させる方法がわかりません。

ログファイルを設定するCBCのオプションを知っている人はいますか? すべての stdout をファイルにリダイレクトしてもうまくいきません。これは、多数の問題を並行して解決していて、それらのログ ファイルを分けておきたいからです。

ソルバーを呼び出す方法の例を次に示します。これはうまく機能し、進行状況を端末に出力します。

これは、ソリューションをどのように構成する必要があると私が考えるかです (ただし、明らかにLogFileNameは有効な CBC オプションではありません)。

これに関するヘルプは大歓迎です。私はこれを理解しようとして、インターネット、ドキュメント、および CBC のインタラクティブ セッションを何時間も調べてきました。

PuLP を使用しようとしていますが、4000 個の制約 (67 個の変数) を追加するのに50 秒かかります。問題の解決にはほんの一瞬しかかかりません。

PuLP を使用して、多数の問題セットで複数のソルバーを簡単にテストしたいと考えています。

PuLP にこれほど時間がかかるのでしょうか。PyGLPK を直接使用すると、セットアップと解決の両方を含めてほんの数秒しかかからないので、そうならないことを願っています。PuLP でのこのステップの効率を改善するにはどうすればよいですか?

アップデート

私の制約行列は非常にまばらで、非ゼロの係数のみを含めることで、この特定の問題のセットアップ時間を 4 ～ 5 秒に短縮できました。独自の .lp または .mps 形式のファイルを作成し、cbc または glpsol サブプロセスで問題を解決し、PuLP よりもはるかに効率的にソリューションを解析できます。これは、PuLP の場合に入力ファイルを数ミリ秒で書き込むことができるためです。数秒かかります。これがなぜなのかはまだわかりません。

Python PuLP では、線形計画法の制約を弾性部分問題に変えることができます。

http://www.coin-or.org/PuLP/pulp.html?highlight=lpsum#elastic-constraints

部分問題を解くと、目標値からの距離が最適化されます。

もちろん、ターゲット値はこのサブ問題に対する最適なソリューションですが、弾性化の全体的なポイントは、このソリューションが実行不可能である可能性があると考えていることです。

サブ問題を全体の問題にどのように組み込むことができますか? 制約を追加する方法で問題に追加しようとしましたが、これにより型エラーがスローされました。目的関数に入れてみましたが、これもうまくいきませんでした。

上記のドキュメントまたはここでホストされている例には何も見つかりません。

https://code.google.com/p/pulp-or/wiki/OptimisationWithPuLP?tm=6

これが私が定式化した副問題です：

LP目標に組み込む必要があると私が考える最も近いものは次のとおりです。

...

私はこの問題に何日も取り組んできましたが、まだ解決策がありません。簡単な例で説明しましょう。

長さ 8 の整数の配列があるとします。すべてのセルは特定の値を取ることができます。最初の 4 つのセルは 0 または 1 を取ることができ、残りの半分は 0、1 または 2 を取ることができます。これらの 3 つの配列はいくつかの例です。

ただし、次のように、配列を構築するためのいくつかの制約があります。

理解を深めるために;

問題は、これらの制約から推論された t タプル (t-長さ)の数を見つける必要があるということです。たとえば、どの制約にも違反しない生成された配列の 1 つが と呼ばれるとしmyArrayます。を見ると、が 0 のconstraint1場合は 1 でなければならないことがわかります。したがって;myArray[0]myArray[1]myArray[1]constraint1

ここで を見ると、が 1のconstraint2場合は0 にはならないことが示されています。私たちのケースでは、すでに1を選択しているので、は 0 になります。myArray[1]myArray[2]myArray[1]myArray[2]

これらの含意が組み合わされると、もう 1 つの制約が次のように形成されます。

これは問題を説明するためだけの非常に単純な例であることを強調したいと思います。私の場合、配列の長さは 50 ～ 200 の間で変化しています。数値の制約は、0 から 500 の間 (場合によってはそれ以上) の任意の値にすることができます。また、必要なのは推論された制約の数だけであり、それらを見つける必要がないことも強調したいと思います。

これが私が試したいくつかのアプローチです。

1) 少なくとも 1 つの共通オプションが同じである制約のオプションの真理値表を見つけます。次に、すべての t タプルを探します。スペースが非常に大きいことがわかりました。

2) Mathematica の制約に違反しないすべての解 (充足可能な問題) を見つけ、どの t-タプルが欠落しているかを探します。解決策は 1 つも見つかりません。

問題は、これらのアプローチでは、必要のないスペース全体を生成しようとしたことです。スペース全体を列挙せずに t タプル (制約) の数を見つけるためのより良いアイデアはありますか?

PuLP によって作成された次の LP ファイルがあります。

テスト用にこの問題を 1 つずつ生成するコードを手動で再作成しました (この投稿の下部を参照)。PuLP はこの問題の解決策を未定義として報告しますが、CBC 自体は最適な解決策を生成できることがわかりました。

CBC:

同じソルバーを使用しても、PuLP が同じ答えを見つけられないのはなぜですか? この問題は、視覚的には、最適解があることは明らかです。

LP ファイルを生成するための手動コードは次のとおりです。

コスト関数を最小化する PuLP の線形問題を解こうとしています。コスト関数自体は、コスト関数の最大値の関数です。たとえば、1 日のコストがあり、1 か月のコストを最小化しようとしています。これは、1 日のコストと 1 か月の最大 1 日のコストの合計です。 . 最終的なソリューションで関数の最大値を取得しているとは思いません。この問題のトラブルシューティング方法がわかりません。コードの基本的な概要は次のとおりです。

価格 [0] が価格の最大値ではなく、c_0 と d_0 の両方が 0 であっても、変数 max_revenue は常に c_0 - d_0 + 価格 [0] に等しくなります。動的最大値が問題に挿入されていることを確認する方法を知っている人はいますか? ありがとう！