终止 MIP 优化
描述 MIP 优化器的终止条件。
CPLEX 在各种情况下终止 MIP 优化。
首先,CPLEX 声明整数最优性,并在找到整数解法且搜索空间的所有部分都已处理时终止。
此情况下的最优性相对于您已设置的任意容差和最优性条件。 例如,CPLEX 在分支裁剪法过程中处理节点时会考虑任何用户提供的分界值(例如 CutLo
或 CutUp
)以及目标差值参数 (ObjDif
)。
因此,这些设置间接影响终止。
用户可以显式设置的一个重要终止条件是 MIP 间隔容差。 实际上,有两种此类容差:常用的相对 MIP 间隔容差,以及适合于预期最优目标函数的量级非常小的情况的绝对 MIP 间隔容差。 相对 MIP 间隔容差的缺省值为 1e-4;绝对 MIP 间隔容差的缺省值为 1e-6。 这些缺省值指示 CPLEX 在整数可行解法已证明为处于最优性的 0.01% 内时停止。 在具有仅获取大致准确性的输入数据的困难模型上(其中认为在合理的计算时间内无法证明最优),用户可能会选择较大的相对 MIP 间隔以允许提前终止;例如,相对 MIP 间隔为 0.05(对应于 5%)。 相反,在目标函数相当于数十亿美元并且数据准确到值得进一步处理的程度的模型中,更严格的相对 MIP 间隔(甚至为 0.0)可能有利于避免缺少尽可能最佳的解法的任何机率。
CPLEX 在达到已设置的任何限制时也会终止优化。 可以对时间、节点数、树内存的大小和整数解法的数量设置限制。 表 1概括这些参数及其用途。
设置限制的对象 | 使用此参数 | Concert Technology | Callable Library | Interactive Optimizer |
---|---|---|---|---|
耗用时间 | 优化器时间限制(以秒为单位) |
TiLim
|
CPX_PARAM_TILIM
|
timelimit
|
耗用的确定性时间 | 确定性时间限制 |
DetTiLim
|
CPX_PARAM_DETTILIM
|
dettimelimit
|
节点数 | MIP 节点限制 |
NodeLim
|
CPX_PARAM_NODELIM
|
mip limits nodes
|
树大小 | 树内存限制 |
TreLim
|
CPX_PARAM_TRELIM
|
mip limits treememory
|
整数解法的数量 | MIP 整数解法文件开关和前缀 |
IntSolLim
|
CPX_PARAM_INTSOLLIM
|
mip limits solutions
|
相对 MIP 间隔容差 | 相对 MIP 间隔容差 |
EpGap
|
CPX_PARAM_EPGAP
|
mip tolerances mipgap
|
绝对 MIP 间隔容差 | 绝对 MIP 间隔容差 |
EpAGap
|
CPX_PARAM_EPAGAP
|
mip tolerances absmipgap
|
当发生错误(例如 CPLEX 内存不足或子问题无法求解)时,CPLEX 也会终止。 如果由于对子问题求解失败而发生错误,那么在节点日志文件中会显示另一行来指示该失败的原因。 有关克服此类错误的建议,请参阅 MIP 性能问题故障诊断。