問題タブ [integer-programming]

(充足可能な) (線形) 整数充足可能性問題があります。この問題には、とりわけ、ブーリアン値の変数が多数含まれており、それらを x ₁ ...x _nと呼びます。制約の 1 つは、sum(x ₁ ...x _n ) = C です。これらの変数の固定値と、これらの変数の固定値 (すべての可能なソリューションで、これらの変数のどれが特定の値 (0 または 1、これらはブール値であるため) を取るかなど)。

私は実用的な解決策を持っていますが、それはただ遅いです（穏やかに言えば）：

1. _{x 1} == 0という制約を追加します
2. 問題が解決可能かどうかを確認する
3. 手順 1 で追加した制約を削除します。
4. x ₁ == 1という制約を追加します
5. 問題が解決可能かどうかを確認する
6. 手順 4 で追加した制約を削除します
7. 2 と 5 の少なくとも 1 つが成功したことをアサートします。
8. 両方が成功した場合、変数は固定されません。それ以外の場合、変数は、問題がまだ満足できる制約に固定されます。
9. _{x 2} ...x _nに対して 1...8 を繰り返す

これの問題は、遅いことです。特に、問題を O(n) 回、つまり 2*n 回解く必要があります。（ソルバーをウォームスタートするために以前のソリューションを渡していますが、ソルバーを開始するだけでほとんど時間がかかります。）

もっと速い方法はありますか？特に、ソルバーの呼び出し回数を減らす必要があるものは?

_{私が考えていたことは、残念ながらそのままでは機能しません}が、それを ILP 問題に変えて 2 回解決すること_です。同じものを最小化し、どの変数が変化するかをチェックします。残念ながら、これは一般的には機能しません。(カウンター) の例: ブール変数and 、 where . どちらの変数も固定されていなくても、最大化と最小化を行っても同じ結果が得られます。xyx+y=1

混合整数非線形計画問題 (MINLP) を解くために SCIAMPL を使用しています。ほとんどの場合、うまく機能していますが、ソルバーが実行不可能性を誤って検出する例を見つけました。

ソルバーは、事前解決フェーズで実行不可能性を検出しています。ただし、x と y を 4 と 12 に固定する 2 つの制約のコメントを外すと、ソルバーが機能し、正しい v と z の値が出力されます。

なぜこれが起こっているのか、そしてそれを回避するために別の方法で問題を定式化できるかどうかに興味があります. 私が得た 1 つの提案は、通常、非凸の問題では実行不可能性の検出があまりうまくいかないというものでした。

編集: これは単なる SCIP の問題ではないことに注意してください。SCIP は、この特定のセット K で問題を解決するだけです。たとえば、別のグローバル MINLP ソルバーである bonmin を使用すると、この特定の K の問題を解決できますが、K を 15 まで拡張すると、bonmin は実行不可能性を検出します。問題は実行可能のままです。その K については、実際に機能するソルバーをまだ見つけていません。FILTER に基づく minlp ソルバーも試しました。BARON は GAMS 入力のみを使用するため、まだ試していません。

整数線形計画法モデルの目的関数の考案に取り組んでいます。目標は、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.

Python 用の混合整数線形計画法 (MILP) ソルバーはありますか?

GLPK python は MILP 問題を解決できますか? 混合整数問題を解決できると読みました。
私は線形計画問題に非常に慣れていません。したがって、混合整数計画法が混合整数線形計画法(MILP)と異なる場合、私はかなり混乱しており、実際に区別することはできません。

CPLEX呼び出し可能ライブラリ（VS2010）を使用してlpを解決しました。lp は次のとおりです。

コードを以下に示します。今、私はそれを MIP (x の追加の完全性制約) にしたいと思います。に変えてみstatus = CPXlpopt (env, lp);ましstatus = CPXmipopt (env, lp);た。これは機能せず、エラーが発生します3003: not a mixed-integer problem。ここで何が欠けているか知っている人はいますか？

御時間ありがとうございます。

私は線形プログラムを持っていますが、制約の形式をどのように表現できるか、またそれが可能であったとしてもわかりません。ここにいる誰かが解決策を知っているかもしれません。

ある会社は、a = b = c の 3 つの成分 a、b、c で​​構成される混合物を組み立てて販売しています。
各成分は、f1 と f2 の 2 つの工場から取得できます。
各食材の価格は一日中変動しており、工場ごとに異なります。
各工場は、対のリストの形式で各材料のコストを提供します: (cost, availableAmount)。

(既存の目的関数に影響を与えずに) 表現したい制約は、その方法がわかりません:
販売価格よりも大きい製造コストを選択することは避けてください。

たとえば、時間 t でのコストは次のようになります。

maximumAllowedQuantity と maximumAllowedCost の 2 つの入力定数の最適な再分割を取得したいと考えています。
しかし、現在、私は maximumAllowedQuantity のみを処理しており、 maximumAllowedCost も処理したいと考えています(これが私の質問の目的です)。

各コストの金額で構成される結果のソリューションは、出力変数になります。

たとえば、提供されたサンプルデータを使用し、入力 maximumAllowedQuantity = 15 に対して ( maximumAllowedCost 制約がないため、それを定式化する方法がわからないため、これが私が尋ねるものです)、現時点のいくつかの目的に基づいています (例: 私が好む)同じ総コストで工場間で金額を公平に分割し、1 つの工場を優先しないようにするため)、
次のようになります。

コスト面で要約できるのは次のとおりです。

得られた混合物をコストで分解すると、次のようになります。

ここでの最大費用は 65$ です。
しかし、私の販売価格が 60$ の場合、お金を失うのを避けるために:
どうすれば maximumAllowedCost = 60$ という制約を追加できますか?

注意: 単純に前の結果を (maximumAllowedCost 制約なしで) 取り、コスト > 60$ の金額を削除することはできません。総量が小さい場合、私の目的関数はコスト <= 60 の数量に対して別の再分割を与えるためです: ここでは 9.5 (15 - 0.5 - 3.0 - 2.0) 以前の 15 ではなく。
...

ありがとう

私はツリーの問題に取り組んでいます。ILP の定式化を書こうとしています。木 T=(V,E) V は頂点 E は辺です。私の制約の 1 つは接続性に関するものであり、次のステートメントを作成したいと考えています。X[parent_i,i] = 1. X はバイナリ変数で、ソリューション内にあるノードを選択することを示します。

前もって感謝します。

Python 2.7.8、Windows 32 ビットで PuLP プログラミング ライブラリを実行しています。混合整数線形計画問題のソルバーとして GLPK を使用しています。ソルバーは約に収束します。最適解の 1% を迅速に計算しますが、正確な最適解を計算するには時間がかかります。PuLP を使用して GLPK ソルバーのパーセント許容誤差を指定する方法はありますか? https://pythonhosted.org/PuLP/solvers.htmlを検索しましたが、GLPK ソルバーに関する回答はありません。