目的関数に 2 つの乗算変数があり、モデルを 2 次にする最適化問題があります。
現在、モデルを解析するために zimpl を使用し、それを解決するために glpk を使用しています。二次計画法をサポートしていないため、これを MILP に変換する必要があります。
. 最初の変数は範囲 [0, 1] の実数で、2 番目の変数は範囲 0 から inf の実数です。これは問題なく整数である可能性があります。
目的関数の重要な部分は次のようになります。
max ... + var1 * var2 + ...
制約にも同様の問題がありましたが、簡単に解決できました。
この種の問題を目的関数でどのように解決できますか?
この形式のモデルは、実際には双一次最適化問題と呼ばれます。双一次項を線形化する典型的なアプローチは、マコーミック エンベロープと呼ばれるものを使用するものです。
x*y最大化問題の目的で必要な変数 x と y を検討してください。x と y が と で囲まれていると仮定するとxL <= x <= xU、量の上限である を次の制約で置き換えることができます (ここで導出を確認できyL <= y <= yUます)。x*yw
w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL
これらの制約はすべて決定変数で線形であることに注意してください。マコーミックエンベロープには対応する下限がありますが、最大化しているので、あなたの場合は重要ではありません。
のより厳密な境界が必要な場合x*yは、変数の 1 つ (ここでは x を使用します) の間隔を [xL1, xU1]、[xL2, xU2]、...、[xLn, xUn] の範囲に分割できます。 、補助連続変数{x1、x2、...、xn}および{w1、w2、...、wn}、および補助バイナリ変数{z1、z2、...、zn}を導入します。 x 値の範囲が選択されました。上記の制約は次のように置き換えることができます (ここではインデックス 1 のケースを示しますが、n 個のインデックスすべてに対してこれらが必要になります)。
w1 <= xU1*y + x1*yL - xU1*yL*z1
w1 <= x1*yU + xL1*y - xL1*yU*z1
xL*z1 <= x1 <= xU*z1
基本的に、z1=0 (範囲のこの部分が選択されていない) の場合は常に x1=0 かつ w1 <= 0 になり、z1=1 (範囲のこの部分が選択されている) の場合は通常のマコーミック エンベロープになります。 .
最後のステップは、これらの変数の範囲固有のバージョンから x と w を生成することです。これは次の方法で実行できます。
x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn
n を大きくするほど、双一次項の推定がより正確になります。ただし、n の値が大きいと、モデルを解く際の扱いやすさに影響します。
最後に、変数の 1 つが無制限であることを示していますが、McCormick エンベロープでは両方の変数に境界が必要です。境界を修正して解決する必要があります。最適な値が境界にある場合は、別の境界で再解決する必要があります。