一文教你基于学习的方法决定在哪些分支节点上运行heuristic算法

论文阅读笔记,个人理解,如有错误请指正,感激不尽!该文分类到Machine learning alongside optimization algorithms。

1 混合整数规划求解

混合整数规划问题(MIP)目前比较有效的算法就是branch and bound,branch and cut等。很多商业的或者非商业的MIP solver用的都是这些框架。branch and bound构建MIP的搜索数,通过搜索策略(DFS、BFS等)对分支树进行搜索,通过求解节点的linear relaxation(LP)获得节点的下界(lower bound)。如果LP解满足整数约束(IP),则可认为找到了原问题的一个可行解(feasible solution),branch and bound记录在搜索过程中找到的可行解,并维护一个最优可行解作为全局的上界。当节点的下界比上界还差时,则减掉该支路。最终遍历所有支路,获得最优解。

2 Primal Heuristic

通过branch and bound,branch and cut等求解MIP时,通常需要花费大量的计算时间,因为很多问题的LP模型获得的lower bound非常差。在分支节点上运行heuristic算法对可行解进行搜索,可大大提高搜索的速度。比如在前期通过heuristic找到一个较好的上界,可以使得branch and bound在搜索的过程中减掉很多没用的支路,从而加快优化的速度。

在现在常用的MIP solver中已经集成了很多成熟的heuristic算法,例如在IBM 的CPLEX中对heuristic有这样一段说明:

何为探试?

定义探试,并描述 CPLEX 在 MIP 优化中应用探试的条件。

在 CPLEX 中,探试是一个过程,用于尝试快速生成良好或近似的问题解,但缺少理论保证。在求解 MIP 的上下文中,探试是可以生成一个或多个解的方法,它可满足所有约束和所有整数性条件,但没有关于是否已找到最佳可能解的指示。

这些探试解集成到分支裁剪中,在提供最优性证明方面可实现与分支所生成的任何解相同的优势,在许多情况下,它们可以加快最终最优性证明的速度,或者可以提供次最优但高质量的解,而所需的时间比单单进行分支更短。使用缺省参数设置时,CPLEX 将在探试可能有益时自动调用探试。

CPLEX 提供了探试系列,用于在分支裁剪过程中寻找节点(包括根节点)处的整数解。下列主题对这些探试系列进行阐述。

其中一个比较关键的问题就是:在分支树的哪些节点运行heuristic有可能获得更好的结果?这样就引出了这篇文章的motivation:通过对模型的训练,将机器学习的模型集成到MIP的求解过程中,在分支节点中模型决定是否运行heuristic。模型必须是online的,即训练好以后,在进行预测时只知道当前节点以及分支树的信息,整颗分支树或者剩下节点的信息。

在这篇文章中,作者给这个模型取了一个很有深意的名字,叫oracle,中文翻译过来叫“神谕”,简直是绵羊放山羊屁--既洋气又骚气……

3 数据特征

机器学习是通过输入的数据来给出预测的结果,而应当输入数据的特征应当良好地反映问题当前的状态,这样才能给出准确的结果。这篇论文中使用了49个数据特征:

Global features通过一些"gap"描述了当前搜索的状态;Node LP features使用了节点N的LP解来指示一些节点的特征(括号中的x2表示该特征包含了更细一级的两个特征,下同);Scoring Features for Fractional Variables受启发于大多数diving heuristics中使用的scoring functions,该函数主要用于选取下一个分支的变量。

4 训练数据收集

机器学习的一大关键(亦是难点)就是训练数据的收集。给定一个MIP算例集合,,一个用于搜索过程中的启发式算法,那么关于的数据集可以从每一个算例上获取,最终的训练集为。

作者在每个分支节点上运行,然后收集0-1分类标签值,以及数据特征向量。如果在节点找到了一个可行解,否则为0。但是如果在节点找到了一个更好的可行解,那么有可能会影响到在之后的节点的值。这样收集的数据是有问题的。

因此作者采取的数据收集策略是:在每个节点运行,但是找到的可行解并不替换当前的可行解,这样从分支定界的角度看,就相当于每个节点都不运行了。其次,收集的数据时,其他的启发式算法都采用默认设置(一个solver在求解过程中会调用多种heuristic)。

5 实验

作者修改了开源的SCIP规划求解器,并使用CPLEX作为SCIP的LP solver。机器学习采用框架scikit-learn,使用logistic regression (LR)来学习一个二进制的分类模型。

作者选取了SCIP中10个Heuristic算法进行训练,每个算法训练了一个模型,运行时10个模型都加载进去,策略是Run-When-Successful,即oracle说能成功的时候就运行该heuristic,否则不运行。其他启发式算法则采用默认设置。所提出的框架在MIPLIB2010 Benchmark上的对比结果如下(DEF表示使用SCIP默认设置,ML采用提出的oracle):

其中Primal integral为评判搜索过程中算法好坏的,粗略的介绍如下图,总之就是该指标越小越好:

可以看到,相比默认设置,作者提出的结合oracle在各项指标上均取得不错的效果。其实从训练的结果来看,准确率是非常低的,但是默认的设置下准确率(能找到可行解的比例)更低。因此这个oracle还是有一定的价值的。

参考文献

[1] Khalil E B , Dilkina B , Nemhauser G L , et al． Learning to Run Heuristics in Tree Search[C]// Twenty-sixth International Joint Conference on Artificial Intelligence． 2017．