整型线性规划
更改选项以改进解决方案过程
请注意
通常,您可以更改MILP的配方,使其更容易解决。有关如何改变配方的建议,请参阅Williams[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年。