主要内容

整定整数线性规划

更改选项以改进解决方案流程

请注意

通常,你可以改变MILP的配方,使其更容易解决。有关如何更改配方的建议,请参阅威廉姆斯[1]

在你运行intlinprog有一次,您可能想更改一些选项并重新运行它。您可能希望看到的更改包括:

  • 较低的运行时

  • 降低最终目标函数值(更好的解决方案)

  • 最后小缺口

  • 更多或不同的可行点

以下是对最有可能帮助解决方案过程的选项更改的一般建议。按这个顺序试试这些建议:

  1. 为了更快更准确的解决方案,增加CutMaxIterations选项的默认值10到一个更高的数字,例如25.这可以加速解决方案,但也可以减缓它。

  2. 为了更快更准确的解决方案,改变CutGeneration选项“中间”“高级”.这可以提高解决方案的速度,但会使用更多的内存,并可能降低解决方案的速度。

  3. 为了更快更准确的解决方案,改变IntegerPreprocess选项“高级”.这可能对解决方案的过程有很大的影响,要么有利,要么不利。

  4. 为了更快更准确的解决方案,改变RootLPAlgorithm选项“primal-simplex”.通常这种改变是无益的,但偶尔也会有好处。

  5. 试图找到更多或更好的可行点,增加HeuristicsMaxNodes选项的默认值50到一个更高的数字,例如One hundred.

  6. 试图找到更多或更好的可行点,改变启发式选择,要么“中间”“高级”

  7. 试图找到更多或更好的可行点,改变BranchRule选项“strongpscost”或者,如果这个选择不能改善解决方案,“maxpscost”

  8. 为了更快的解决方案,增加ObjectiveImprovementThreshold选项从其默认值0到一个正值,例如1的军医.然而,这种改变会导致intlinprog求更少的整数可行点或更不精确的解。

  9. 试图更快地停止求解器,改变RelativeGapTolerance选项设置为比默认值高的值1的军医.同样地,为了获得更准确的答案,改变RelativeGapTolerance选择较低的值。这些改变并不总是能改善结果。

一些“整数”解不是整数金宝搏官方网站

通常,解决方案中的一些被认为是整数值的组件x (intcon)不是精确的整数。intlinprog将其中的所有解值视为整数IntegerTolerance的一个整数。

要使所有假定的整数都是精确的整数,可以使用函数。

x (intcon) =圆(x (intcon));

谨慎

四舍五入会导致解决方案变得不可行。金宝搏官方网站四舍五入后检查可行性:

马克斯(A * x - b)%看看条目是不是太积极了,所以有小的不可行性马克斯(abs (Aeq * x - beq))%查看条目是否足够接近于零马克斯(x -乌兰巴托)%正数条目违反界限马克斯(lb - x)%正数条目违反界限

大组件不是整数值

intlinprog当解决方案组件的绝对值超过时,不强制其为整数值吗2.1 e9.当你的解决方案有这样的组件时,intlinprog警告你。如果收到此警告,请检查解,看看解中假定的整数值分量是否接近整数。

大系数不允许

intlinprog不允许问题的分量,如系数在f一个,或乌兰巴托,超过1 e15按绝对价值。如果你想逃跑intlinprog面对这样的问题,intlinprog一个错误的问题。

如果你得到这个误差,有时你可以将问题扩大到更小的系数:

  • 的系数f太大了,试着乘一下f通过一个小的正比例因子。

  • 对于太大的约束系数,请尝试将所有边界和约束矩阵乘以相同的小正比例因子。

参考文献

威廉姆斯,H.保罗。数学规划中的模型构建,第5版。威利,2013年。