整数線形計画法の調整

古い形式のオプションを変更して解を求めるプロセスを改善する

メモ

通常、MILP の定式を変更して容易に問題を解けるようにすることができます。定式を変更する方法の詳細については、Williams [1]を参照してください。

'legacy' intlinprog アルゴリズムを一度実行した後に、一部のオプションを変更して再実行する場合があります。期待される変化には、次のようなものがあります。

  • 実行時間を下げる

  • 最終目的関数値を下げる (より良い解)

  • 最終ギャップを小さくする

  • 実行可能点を増やすまたは変更する

解法プロセスに最も役立つ可能性のあるオプションの変更に関する一般的推奨事項を以下に示します。この順序で推奨事項を試してください。

  1. より速くより正確な解を求めるには、CutMaxIterations オプションを既定の 10 から 25 などのより高い数値に増やします。これにより解が速くなる可能性がありますが、遅くなる場合もあります。

  2. より速くより正確な解を求めるには、CutGeneration オプションを 'intermediate' または 'advanced' に変更します。これにより解が速くなる可能性がありますが、大量のメモリを使用し遅くなる場合もあります。

  3. より速くより正確な解を求めるには、IntegerPreprocess オプションを 'advanced' に変更します。これにより解法プロセスに大きな影響 (有益な影響またはそうでない影響) を与える場合があります。

  4. より速くより正確な解を求めるには、RootLPAlgorithm オプションを 'primal-simplex' に変更します。通常この変更は有益ではありませんが、有益な影響をもたらす場合もあります。

  5. より多くのより良い実行可能点を検出するには、HeuristicsMaxNodes オプションを既定の 50 から 100 などのより高い数値に増やします。

  6. より多くのより良い実行可能点を検出するには、Heuristics オプションを 'intermediate' または 'advanced' のいずれかに変更します。

  7. より多くのより良い実行可能点を検出するには、BranchRule オプションを 'strongpscost' に変更します。その選択によって解を改善できない場合は、'maxpscost' に変更します。

  8. より迅速に解を得るには、ObjectiveImprovementThreshold オプションを既定の 0 から 1e-4 などの正の値に増やします。ただし、この変更により、intlinprog の整数実行可能点の検出数が減ったり、あまり正確でない解が検出されたりすることがあります。

  9. ソルバーをよりすばやく停止するには、RelativeGapTolerance オプションを既定の 1e-4 より高い値に変更します。同様に、より正確な解を得るには、RelativeGapTolerance オプションをより低い値に変更します。これらの変更によって必ずしも結果が改善されるとは限りません。

一部の “整数” 解は整数ではない

通常、解 x(intcon) の整数値と推定される要素は厳密に整数ではありません。intlinprog では整数の IntegerTolerance 内の解の値はすべて整数と見なされます。

整数と推定されるすべての数値を厳密に整数に丸めるには、関数 round を使用します。

x(intcon) = round(x(intcon));

注意

丸めによって解が実行不可能になる場合があります。丸めを行った後に実行可能性をチェックします。

max(A*x - b) % see if entries are not too positive, so have small infeasibility
max(abs(Aeq*x - beq)) % see if entries are near enough to zero
max(x - ub) % positive entries are violated bounds
max(lb - x) % positive entries are violated bounds

大きな要素は整数値ではない

intlinprog は、絶対値が 2.1e9 を超える場合、解の要素に整数値を適用しません。このような要素が解に含まれる場合、intlinprog は警告を表示します。この警告が表示された場合は、解をチェックして、解の整数値と推定される要素が整数に近いかどうかを確認します。

大きな係数は許可されない

intlinprog では、絶対値が 1e20 ("legacy" アルゴリズムの場合は 1e25) を超える問題の要素 (f や ub の係数など) は受け入れられません。また、絶対値が 1e15 を超える A や Aeq の要素も受け入れられません。このような問題をもつ intlinprog を実行しようとすると、intlinprog でエラーが発生します。

このエラーが発生した場合は、以下のように問題をスケーリングしてより小さな係数をもつようにすることができます。

  • f の係数が大きすぎる場合、f に小さな正のスケーリング係数を乗算してみます。

  • 制約係数が大きすぎる場合、すべての範囲および制約行列に同じ小さな正のスケーリング係数を乗算してみます。

参照

[1] Williams, H. Paul. Model Building in Mathematical Programming, 5th Edition. Wiley, 2013.