基于散列配对的混合整数预解技术对MIP求解器的影响

13原始论文EURO Journal on Computational Optimization（2020）8：205https://doi.org/10.1007/s13675-020-00129-6基于散列配对的两行两列混合整数预解Patrick Gemander1·Wei-Kun Chen2·Dieter Weninger1·利昂娜Gottwald3·安布罗斯Gleixner3·亚历山大·马丁1投稿时间：2019年10月1日/受理时间：2020年7月10日/在线发表时间：2020年8月18日©作者（S）2020摘要在最先进的混合整数规划求解器中，在开始实际的分支和切割阶段之前，应用大量的简化技术来简化问题并加强模型公式化尽管它们在数学上很简单，但这些方法可能对给定问题的可解性产生重大影响然而，成功采用预解决技术的一个关键属性是它们的速度。因此，大多数方法单独检查约束或变量，以保证线性复杂度。在本文中，我们提出了新的基于散列的配对机制，有助于克服已知的性能限制更强大的presolve技术，考虑对行或列。此外，我们开发了一个增强这些presolve技术之一，利用存在的二进制变量的集合包装结构，以加强所产生的减少，而不增加运行时间。我们分析了这些方法对MIPLIB 2017基准集的影响，基于MIP求解器SCIP中的实现。线性规划·混合整数线性规划·优化求解器·预求解数学科目分类90C05· 90C10· 90C11· 65Y051 介绍混合整数规划（MIP）的预解析是一组例程，其去除冗余信息并加强模型公式化，目的是加速随后的主解过程，其通常是分支切割方法。此外，presolve是对branch-and-cut的一个很好的补充，因为它关注的是通常不在branch-and-cut工作空间内的模型简化和重构，例如，最大公约数减少或冗余检测。在文章的最后一页上提供了扩展的作者信息13206P. Gemander等人Presolve可以非常有效，并且它经常使问题变得棘手和可解决（Achterberg andWunderling2013）。考虑到预解无疑是解决MIP问题的重要组成部分，MIP文献中的文章相对较少。只是在过去几年里，关于这一主题的出版物数量才略有增加。最早的贡献之一是Brearley et al.（1975）。后来，Johnson和Suhl（1980年），Guignard和Spielberg（1981年），Crowder et al.（1983），Hoffman和Padberg（1991）研究了0 - 1不等式的预求解技术。Savelsbergh（1994）发表了MIP问题的预处理和探测技术。其中的许多方法现在几乎已经成为每个MIP求解器的标准Presolve 在 线 性 规 划 （ Andersen and Andersen1995 ） ， 特 别 是 内 点 算 法（Gondzio1997）中也起着重要的作用。近年来，预溶作为一个研究课题变得越来越重要（Gamrath et al.2015; Achterberg et al.2014年）的报告。最后，Achterberg et al.（2019）最近的出版物值得特别关注。它不仅提出了许多新的预解方法，而且突出了理论上有趣的细节预解约化和数论的关系。如何实现预解算法经常使有益的和有害的方法之间的区别。通常，为了适当地对预求解方法进行排名，根据运行时行为来权衡缩减的强度是合理的Suhl和Szymanski（1994）、Martin（2001）、Atamtürk和Savelsbergh（2005）以及Achterberg（2007）讨论了各种预解约化的实现细节关于MIP求解器不同功能的性能影响的研究发表在Bixby等人（2004）、Bixby和Rothberg（2007）以及Achterberg和Wunderling（2013）中。这些出版物证实了预解和切割平面技术是迄今为止现代MIP解算器最重要的组成部分。在最简单和通常最快的情况下，单独的行或列被认为是预解决减少。减少之间的一些相互作用可以通过例如，收紧变量边界，但严格地说，这种方法限于局部信息，因此通常产生弱约简。另一方面，可以尝试通过构建全局数据结构（例如收集二进制变量之间相互不兼容性的团表）或通过考虑问题的更大部分甚至整个问题来找到更强的约简，这通常会导致更高的运行时间。因此，重要的是要在有效性和计算开销之间取得良好的平衡。实现这一点的一种方法是同时检查两行或两列。Bixby和Wagner（1987）发表了一个有效的算法来找到约束矩阵的平行行或列。Achterberg等人的研究也涉及多行预解还原（2014），其中他们通过同时检查多个问题约束来改进模型公式最后，一 次 考 虑 多 个 行 或 列 允 许 使 用 更 多 的 技 术 例 如 ， Chang 和 McCormick（1993），Gondzio（1997）以及最近的Achterberg等人（2019）中描述的矩阵稀疏化技术在一次只考虑一行或一列时无法应用两行两列混合整数预求解使用20713◦ ∈{= ≤ ≥}∈M∈<${−∞}∈<${∞}∈I<$NN={}M={}∈在上面提到的许多出版物中，用预解约简求解MIP已经取得了惊人的结果然而，这些结果通常与底层实现的确切细节密切相关。特别是，两行或两列技术立即提出了如何找到有希望的行或列对的问题，因为简单枚举所有组合通常在预求解上下文中计算成本太高。大多数出版物都没有回答这个问题。因此，在这篇文章中，我们开发了两种有效的方法来通过哈希方法确定预解约简的合适对（Knuth1998）。此外，我们描述了新的presolve方法或现有技术的扩展，据我们所知，尚未公布。本文的结构如下。第2节介绍了本文其余部分使用的符号和一些基本概念。第3第3节描述了五种新的预解方法或已发表方法的扩展。前两种方法处理约束矩阵的稀疏化，另外两种方法专注于约束收紧，最后提出的方法是一种导致变量和约束固定的对偶方法。接下来，在第4节中，我们描述了哈希方法，我们使用它来解决为前面提出的预解决方法找到问题的两行或两列的有希望对的问题。随后，Sect。5提供计算结果以评估其性能影响。最后，我们总结了我们的结论在节。六、2 符号和背景本文件建立在以下符号的基础上。 令1，...，n和1、......、M成为索引集。 给定矩阵ARm×n，向量c罗马尼亚bRm，4（R））n，u（R））n，变量xRn与x jZ代表j，关系式我、、、对于A 的所有i，混合整数规划（MIP）可以用以下形式表示：最小cTxS.T.斧头，4j≤xj≤uj，对所有j∈N，xj∈ Z对所有j∈ I.（1）的可行解集定义为：PMIP：={x∈Rn|xj∈Z<$j∈I<$Ax<$b<$4j≤xj≤uj<$j∈N}.（一）此外，我们定义了（1）的线性规划松弛的可行解集，PLP：={x∈Rn|Ax<$b<$4j≤xj≤uj<$j∈N}.208P. Gemander等人13∈∈M·= {∈ M|//===N中国∈我我我我∈N∈NA的单个系数用aij表示，其中i∈M，j∈N。 我们使用符号Ai·i来通过A的i -行来标识行向量given。类似地，A·j是由A的第j列给出的列向量。 设R和V，则ARV表示由限制于行索引i R和列索引j的A的系数组成的矩阵 V.类似地，xV表示限于索引集V的向量x。在某些情况下，我们参考支撑函数，它决定了向量的非零熵的指数。W，它hsupp（Ai·）={j∈N|ai j/=0}表示对Ai·的支持。相应地，supp（A·j）ii j0表示列Aj的支撑。根据矩阵A的系数和变量x的界限，（1）中每行i∈M的最小活动和最大活动由下式给出：在f{Ai·x|4j≤xj≤uj<$j∈N} =.ai j4j+.（2）第一次见面。Jaij>0Jaij0和超{Ai·x|4j≤xj≤uj<$j∈N} =.ai juj+.ai j4j，（3）∈N∈NJaij>0Jaij0分别由于允许变量x有无限个下限或上限，因此可能发生无限个最小或最大活动。为了简化符号，我们写inf（A iVx V）：= inf {A iVx V|4 j≤ x j≤ u j<$j ∈ V}sup（A iVx V）：= sup {A iVx V|4 j≤ x j≤ u j<$j ∈ V}对于行i和可变索引的子集V ，以便引用部分最小和最大活动。这与V的（2）和（3）一致。考虑不等式约束AiVx V+a ijx j≥b i其中ei∈M，j∈N，V=supp（Ai·）\ {j}，且a i j/=0. 在我去之前，xj，一个重要的问题是如何确定边界4V，uV∈R<${−∞，∞}，我我合理的计算工作量，4V≤AiV xV≤uV对于所有的x PMIP成立。为了实现这一点，存在各种可能性，并且单行预解的最简单方法是在边界框上以线性时间进行优化，即4V：= inf（A iVx V），u V：= sup（A iVx V）。两行两列混合整数预求解使用20913（四）210P. Gemander等人13我我我我我我我我我如果uV是有限的，我们可以确定变量xj的界限。根据ij的符号我们区分两种情况。对于ij>0，xj的有效下界由下式给出：xj≥（bi−uV）/ aij（5）因此，我们可以将4j替换为max{4j，（bi−uV）/ai j}.（六）类似地，对于ij<0，xj的有效上限由下式给出：xj≤（bi−uV）/ aij（7）因此，我们可以用mi n{uj，（bi−uV）/ai j}.（八）如果xj是一个整数变量，我们将（6）替换为「类似地，min {u j，（b i− u V）/a ij}]。（十）上述观察结果与（4）一起可用于实现一种称为基于可行性的边界收紧（FBBT）的方法，这是一种迭代范围缩减技术（Davis 1987）。它涉及使用所有约束限制来收紧变量范围只要变量范围保持变化，就重复该过程。FBBT可能无法最终收敛（参见Achterberg et al.（2019））。因此，在实践中，当一次或几次迭代后的改进太小时停止迭代，Belotti等人（2010）描述了处理这种特殊情况的替代方法。而不是平凡地优化边界框，可以计算V =min {A iV x V|x∈ PMIP}，uV=max{AiVxV|x∈PMIP}。4两行两列混合整数预求解使用21113我我然而，这种方法通常非常耗时，因为它相当于用不同的目标函数来解决问题（1一个轻量级的替代解决完整的MIP是只考虑线性规划松弛V=min {A iV x V|x∈ PLP}，uV=max{AiVxV|x∈PLP}。然而，这个过程往往太耗时。4212P. Gemander等人13在计算复杂性和边界的紧密性之间更合理的折衷是仅使用系统的少量约束，而不是我们最大化或最小化的所有约束这可以再次通过求解MIP或LP来完成如果我们只使用一个约束，那么求解相应的LP是特别有趣的，因为这样的问题可以在变量数的线性时间内求解，见Dantzig（1957）和Balas和Zemel（1980）。一个密切相关的过程是所谓的基于优化的约束收紧（OBBT），它首先由Shectman和Sahinman（1998）以及Quesada和Grossmann（1995）应用于全局优化在这里，我们想要最小化和最大化的块只包含一个变量：min{xj|x∈PMIP} ≤xj≤max{xj|x∈PMIP}。同样，代替求解完整MIP，可以求解问题的任何松弛以获得xj的有效边界。Presolve方法可以分为两类：原始和对偶预解决方法。原始预解方法基于可行性参数导出约简相比之下，对偶预解方法通过利用来自目标函数的信息来获得约简，同时确保至少一个最优解被保留，只要问题是可行的。3 两行两列预解方法在本节中，我们将概述五种预解方法，我们在第4节中为这些方法开发了配对机制。首先，第3.1节提出了一种原始预求解方法，通过使用行对和第3.2节中的方法来消除非零系数，从而增加约束矩阵的稀疏性图3.2将此思想扩展到使用列进行非零抵消。接下来的两个原始的预解方法，在教派中概述3.3和3.4，通过行对上的FBBT改进变量边界。虽然这两种方法的工作方式相似，但它们具有不同的优点。简而言之，第3.3节中的方法更容易实现，并且可以应用于单个变量，但不能收紧所涉及约束中存在的所有变量的界限。最后，第3.5节提出了一种重用第3.4节中提出的方法的方法，以改进双预解方法。3.1 两行非零相消这种预解方法试图找到由一个等式和第二个约束组成的对Chang和McCormick（1993）、Gondzio（1997）以及最近的Achterberg等人已经使用了这种方法来减少约束矩阵A（2019年）。更准确地说，假设有两个约束两行两列混合整数预求解使用21313|N|=| |−||||−||≤主播的Vk∈N<$MWj⎣⎦AWjAYkAYkAiU xU+ AiV xV+ AiW xW= bi，ArUx U+A rVx V+A rYx Yrb r，其中i， r∈M，且列索引U，V，W，Y的不相交子集<$N。进一步，假设存在标量λ∈R使得ArU−λAiU=0且Ark−λAik/=0，对于所有k∈V。从约束r中减去λ乘以等式i，AiU xU+AiV xV+ AiW xW= bi，（A rV−λ A iV）x V−λ A iW x W+ A rY x Y<$rb r−λbi。（十一）A的非零个数之差是UW.自从案件U W0似乎没有提供任何优势，只有当非零的数量实际减少时才应用减少在所有情况下，这个过程最多需要O（）时间。对于混合整数规划，减少A的非零数有两个主要优点。首先，MIP解算器中的许多子例程依赖于该数字。特别是，LP求解器受益于稀疏基矩阵。其次，非零抵消可能为其他预求解技术提供可能性，以在公式上执行一个特殊的情况发生，如果W 也就是说，等式约束的支持度是另一约束的支持度的子集。这种情况特别令人感兴趣，因为可能发生分解3.2 两列非零相消这个presolve方法将前面的presolve方法的思想扩展到列上，即，我们现在的目标是基于约束矩阵A的两列的非零消除。为了更精确，考虑问题（1）乌吉亚⎢ ⎥xj+AUk中国（12）其中j、 k和U、V、W、Y是行索引的不相交子集我们首先讨论xj是连续变量的情况 假设存在标量λ ∈ R使得λ A Uj−A Uk= 0，λ A Vj− AVk/= 0。 将（12）改写为吉亚·乌吉·阿吉主播⎢ ⎥(xj+λxk)+AVk−λAVj<$xk，⎣-λAWj214P. Gemander等人13并引入一个新的变量z：=xj+λxk，我们得到212P. Gemander等人13.=z|M|| |||=−∞ =∞⎣-λAWj吉亚·乌吉·阿吉主播简体中文AVk − λ AVj <$x k.（十三）AYk根据z的定义，z的上界和下界是4j+λ4k，对于λ>0，4j+λuk，对于λ0，和uuj+λuk，对于λ>0，uj+λ4k，对于λ0，分别然而，为了保持4j≤xj≤uj的界限，4j≤z−λxk≤uj（14）需要明确地添加到问题（1）中。与3.1节中的稀疏化方法一样，当U W > 0成立时，由（13）组成的新表示是有趣的。与基于行的版本的一个不同之处在于，重构包含将约束（14）添加到问题（1）的额外开销。但是，如果xj是自由变量，即 4 j和u j成立，则约束（14）是冗余的，不需要添加到问题（1）中。当xj的边界由约束和其他变量的边界暗示时，xj也可以被视为自由变量。在这种情况下，我们称之为隐式自由变量。我们现在考虑xj是整数变量的情况为了保持完整性，我们要求xk也是一个整数变量，λ是一个整数标量。这保证了在后处理期间反转变换时，我们可以从xj和新的整数变量z的值获得xk的整数值。请注意，将此预解方法应用于问题（1）可以视为将基于行的版本应用于相关的对偶问题。因此，它的时间线性的约束的数量，即其时间复杂度是O（）。由于约束（14）导致的额外开销，|−|W|通常需要比基于行的方法中的大。|is generally required to be larger thanin the row-based method.3.3 基于LP的两个约束的使用约束矩阵A的两行来确定更严格的变量边界或冗余约束的想法已经在Achterberg等人中描述（2019年）。我们将首先介绍预解方法，然后讨论一个重要的观察，以省略不必要的计算。考虑（1）ArU xU+ ArV xV≥ br，AsU xU+AsW xW≥ bs，.4=zAWj两行两列混合整数预求解使用21313∈M<$N∈M<$ ∈{≤=}其中r，s和U，V，W.注意，对于任何i，对应的约束可以被规范化为上面的形式。连同214P. Gemander等人13≤≤- -∈∈∈−∈∈+≥我们利用这两个约束的特殊形式来建立以下两个LPymax=maxArU xUS.T. AsU xU+AsW xW≥bs4≤x≤u，ymin=minArU xUS.T. AsU xU+AsW xW≥bs4≤ x ≤ u。（十五）如Dantzig（1957）和Balas和Zemel（1980）所示，这些问题中的每一个都可以在线性时间内解决。假设ymax和ymin都是有限值，即上述问题是可行的和有界的，结果可以用于再次在线性时间中导出潜在的更强的变量边界并检测约束R的冗余。变量x j，j的界可以通过（16）计算，其中V 如果条件（17）成立，则约束R是冗余的。注意（16）与（5）和（7）的相似性，其中sup（A rU x U）被ymax代替，以及ymax至少与sup（A rUx U）一样强，并且可能更强。xj≥br−sup（ArVrxVr）−ymax，对于arj>0了rjb−sup A− yR（十六）xj≤（rVrxVr）了rjmax，对于rj<0inf（ArV xV）≥br−ymin（17）注意，行r和行s的角色是可互换的。 如以下引理所示，约束r和s上的界限收紧可能仅改善变量x j，j上的界限 V如果至少存在一个变量x i，iU与ri<0 0<$（19）哪里a<$rs（λ）jLj（λ）：=b<$rs（λ）−sup（a<$rs（λ）N\{j}xN\{j}）。Belotti（2013）证明了这些问题可以通过对λ的一个小的有限值集（即Lj（λ）的所有断点的集合）计算分段线性L j（λ）来解决。下一个命题总结了结果。第3.5集Λ：={λ∈（0，1）|（n∈N：a<$rs（λ）=0<$a<$rs（λ）/=0<$λ/=λ，λ∈（0，1））}包含问题（19）和（20）的所有最优解。注意，问题（19）和（20）可能没有最优解或无界。然而，这些边缘情况（在原始论文（Belotti2013）中进行了更详细的讨论）不会影响这种方法的整体可行性。对于所有变量和每个λ Λ单独计算Lj（λ）将导致运行时间为O（3）的算法。然而，通过对每个λ Λ使用常数时间更新操作而不是单独地重新计算每个Lj（λ），可以在O（2）中同时解决所有变量的优化问题我们将概述基本思想以及核心操作;有关该算法的完整细节，请参见Belotti（2013）。表示eΛ={λ1， . . λΛ|{\fnarialblack\fs12\bord1\shad0\4aH00\fscx90\fscy110}{\fnarialblack\fs12\bord1\shad0\4aH00\fscx90\fscy110}{\fnarialblack\fs12\bord1\shad0\4aH00\fscy110}{\fnarialblack\fs12\bord1\shad0\4aH00\fscx90\fscy110}{\fnarialblack\fs12\bord1\shad0\4aH00\fscy110}{\fnarialblack\fs12\bord1\shad0\4aH00\fscx90\fscy110}{\fnarialblack\fs12\bord1\shad0\4|Λ1且λ ∈（0，λ 1）.<<<||<我们定义Lr：=br−a<$rs（λ）>0Ls：= bs−a<$rs（λ）>0如果不使用λ，可以写成两行两列混合整数预求解使用21713..JJ..arj uj−a<$rs（λ）<0asj uj−a<$rs（λ）<0一个rj4j一个sj4j，Lr=br−asj>0<$（asj= 0<$ar j>0）j∈supp（Ar·）arj uj−asj0ar j0）j∈supp（Ar·）arj4j（21）