整数線形計画法の調整
オプションを変更して解を求めるプロセスを改善する
メモ
通常,milpの定式を変更して容易に問題を解けるようにすることができます。定式を変更する方法の詳細は,威廉姆斯[1]を参照してください。
intlinprog
を一度実行した後,一部のオプションを変更して再実行を試みたい場合もあるかもしれません。期待される変化には,次のようなものがあります。
実行時間を下げる
最終目的関数値を下げる(より良い解)
最終ギャップを小さくする
実行可能点を増やすまたは変更する
解法プロセスに最も役立可能性のあるオプションの変更に関する一般的推奨事項を以下に示します。この順序で推奨事項を試してください。
より速くより正確な解を求めるには,
CutMaxIterations
オプションを既定の10
から25
などのより高い数値に増やします。これにより解が速くなる可能性がありますが,遅くなる場合もあります。より速くより正確な解を求めるには,
CutGeneration
オプションを“中间”
または“高级”
に変更します。これにより解が速くなる可能性がありますが,大量のメモリを使用し遅くなる場合もあります。より速くより正確な解を求めるには,
IntegerPreprocess
オプションを“高级”
に変更します。これにより解法プロセスに大きな影響(有益な影響またはそうでない影響)を与える場合があります。より速くより正確な解を求めるには,
RootLPAlgorithm
オプションを“primal-simplex”
に変更します。通常この変更は有益ではありませんが,有益な影響をもたらす場合もあります。より多くのより良い実行可能点を検出するには,
HeuristicsMaxNodes
オプションを既定の50
からOne hundred.
などのより高い数値に増やします。より多くのより良い実行可能点を検出するには,
启发式
オプションを“中间”
または“高级”
のいずれかに変更します。より多くのより良い実行可能点を検出するには,
BranchRule
オプションを“strongpscost”
に変更します。その選択によって解を改善できない場合は,“maxpscost”
に変更します。より迅速に解を得るには,
ObjectiveImprovementThreshold
オプションを既定の0から1的军医
などの正の値に増やします。ただし,この変更により,intlinprog
の整数実行可能点の検出数が減ったり,あまり正確でない解が検出されたりすることがあります。ソルバ,をよりすばやく停止するには,
RelativeGapTolerance
オプションを既定の1的军医
より高い値に変更します。同様に,より正確な解を得るには,RelativeGapTolerance
オプションをより低い値に変更します。これらの変更によって必ずしも結果が改善されるとは限りません。
一部の“整数”解は整数ではない
通常、解x (intcon)
の整数値と推定される要素は厳密に整数ではありません。intlinprog
では整数のIntegerTolerance
内の解の値はすべて整数と見なされます。
整数と推定されるすべての数値を厳密に整数に丸めるには,関数轮
を使用します。
X (intcon) = round(X (intcon));
注意
丸めによって解が実行不可能になる場合があります。丸めを行った後に実行可能性をチェックします。
max(A*x - b)%看条目是不是太正,所以有小的不可行性max(Aeq*x - beq))查看条目是否足够接近零Max (x - ub)%正的条目违反了边界最大(lb - x)%正的条目违反了边界
大きな要素は整数値ではない
intlinprog
は,絶対値が2.1 e9
を超える場合,解の要素に整数値を適用しません。このような要素が解に含まれる場合,intlinprog
は警告を表示します。この警告が表示された場合は,解をチェックして,解の整数値と推定される要素が整数に近いかどうかを確認します。
大きな係数は許可されない
intlinprog
では,f
、一个
または乌兰巴托
の係数など,問題の要素が絶対値の1 e15
を超えることはできません。このような問題をもintlinprog
を実行しようとすると,intlinprog
でエラ,が発生します。
このエラーが発生した場合は,以下のように問題をスケーリングしてより小さな係数をもつようにすることができます。
f
の係数が大きすぎる場合,f
に小さな正のスケ,リング係数を乗算してみます。制約係数が大きすぎる場合,すべての範囲および制約行列に同じ小さな正のスケーリング係数を乗算してみます。
参照
威廉姆斯,H.保罗。数学编程中的模型构建,第5版。威利,2013年。