基于机器学习的MIP排序约束松弛预测模型 - 欧洲计算优化杂志11（2023）100061

欧洲计算优化杂志11（2023）100061基于机器学习的混合整数规划排序约束松弛放大图片作者：J.Ernstb，Xiaodong Lia，Yuan Sunca计算技术学院，RMIT大学，124 La Trobe Street，澳大利亚墨尔本b墨尔本莫纳什大学克莱顿校区数学学院澳大利亚c澳大利亚墨尔本拉筹伯大学拉筹伯商学院ARTIcLE IN fO ABSTRA cT保留字：机器学习可编程启发式分解大规模优化求解大规模的混合线性规划（MIP）可以很难没有先进的算法，如分解为基础的技术。即使分解技术可能是适当的，对于任何大的MIP仍然存在许多可能的分解，并且可能不明显哪个将是最有效的分解的质量取决于对偶边界的紧密性，在我们的情况下通过拉格朗日松弛生成，以及产生该边界所需的计算时间。这两个因素都很难预测，从而促使使用机器学习函数来基于结合边界质量和计算时间的分数来预测分解质量。本文提出了一个全面的分析预测能力的ML函数预测质量的MIP分解创建通过约束松弛。在该分析中，探索了实例相似性和ML预测质量的作用，以及ML排名函数对现有启发式函数的基准测试。对于该分析，已经建立了一个新的数据集，该数据集由从MI-PLIB 2017库的24个实例中采样的这些分解是由贪婪松弛算法和* 通讯作者。电子邮件地址：jakeweiner@outlook.com（J. Weiner），andreas. monash.edu（A.T.恩斯特），xiaodong.li @ rmit.edu.au（X。Li），yuan. latrobe.edu.au（Y.Sun）。https://doi.org/10.1016/j.ejco.2023.1000612192-4406/© 2023作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表欧洲计算优化杂志期刊主页：www.elsevier.com/locate/ejco2J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061以及基于群体的多目标算法，该算法先前已被证明产生高质量的分解。在本文中，我们证明了ML排名函数在与现有的启发式排名函数进行基准测试时能够提供最先进的预测。此外，我们证明，通过只考虑一小部分与每个decom- position中的放松约束相关的特征，ML排名函数仍然能够与启发式技术竞争。这样的发现对于未来的约束松弛方法是有希望的，因为这些特征可以用于指导分解创建。最后，我们强调了ML排名函数在分解创建框架中的好处。版权所有2023作者。出版社：Elsevier Ltd欧洲运筹学学会（European Operational ResearchSocieties，EURO）这是CCBY-NC-ND许可证（http：creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着混合线性规划（MIP）问题的规模和复杂性不断增加，需要新的解决方案技术来跟上问题复杂性的这种持续增长反映在流行的MIP基准数据集MIPLIB中，从2003年到2017年，数据集中最大的实例从20多万个变量增加到140多万个变量[1，15]。由于所有的MIP解决方案的方法需要非多项式时间复杂性，在问题大小的这种增加不能解决的计算机处理能力单独的改进。用于解决这些大规模问题的一种流行方法是通过分解，这是一个长期存在且强大的想法，通常使用三种突出的方法- Benders分解（BD）[13]，Dantzig-Wolfe Reformulation（DWR）[7]和拉格朗日松弛（LR）[14]。所有的方法往往能够产生更严格的边界比线性编程为基础的松弛界限，以及可行的解决方案，如果修复启发式使用或如果该方法是嵌入在分支定界算法。因此，这些分解技术尽管已经有几十年的历史，但在今天的研究界仍然很突出。虽然问题分解非常成功，但这种方法只一直适用于文献中的问题类型，其中的问题结构本身是很好的分解数量有限。理想情况下，当从业者试图解决一个新的和以前看不见的MIP而没有已知的可分解结构时，如果可以使用自动分解框架来确定问题是否可以从基于分解的方法中受益以及哪种分解最有希望，那将是有益的。这样的自动分解框架可能会暴露出许多可分解的问题，否则将不会尝试分解方法。与此同时，它将允许从业者尝试分解方法，而无需对问题具有重要的J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）1000613虽然自动分解框架可能非常有益，但直到最近，在这一领域只进行了有限的工作在[5]，[17]和[24]中进行了三项与创建自动分解框架相关的研究（本文是其延续），以及一个名为GCG的自动DWR工具[12]。在[5]中，作者将原始约束矩阵表示为超图，之后运行k路划分算法以尝试创建k个相等大小的独立块。然后在DWR框架内求解分解。此过程所需的唯一用户输入是问题应被分解成的预定块的数量和用于分区平衡目的的虚拟节点的这种方法的一个显著缺点是先验要求知道问题应该分解成的正确块的数量，这是一个可以在实例基础上显著变化的特征在[17]和[24]中，作者解决了这个问题，并提出了自动分解方法，无需任何用户输入。在[17]中，这是通过社区检测算法和唯一定义的分解质量度量来实现的，该度量被标记为Goodness得分。这个分数来自于子问题中的非零百分比和边界中放松约束的比例。作者在[24]中将分解问题视为多目标问题，使用非支配排序遗传算法II（NSGA-II）算法[8]自动创建分解，同时最小化放松的约束数量和最大子问题的大小。这三篇论文可能缺乏的是，它们只考虑了一小部分特征来指导自动分解过程，块的数量，放松约束的数量和子问题的大小主要用作特征。此外，对于基于种群的排序，例如[24]中描述的NSGA-II算法，当多个分解可用时，具有单个目标排序函数变得重要。最近，一个新的工作分支出现了，考虑到许多特点，使用机器学习（ML）方法来识别何时应当尝试分解方法以及在几个候选者中什么分解最有希望[18]中的作者训练了各种分类器来回答这个问题，即分解是否可能产生比简单地使用原始问题的通用求解器更好的虽然使用这种方法取得了一些成功，但这一系列研究仅有助于解决分解方法是否合适。然而，它并没有提供关于在考虑多个候选项时应选择什么分解来求解的见解[4]中的虽然发现了一些有希望的结果，但最终这一研究仍处于起步阶段，只有有限的成功被证明。特别是，我们认为需要进一步分析以下方面：1）实例相似性在排名性能中扮演什么角色; 2）ML排名函数是否能够准确预测未在训练集中采样的测试实例的分解质量; 3）ML排名函数在基准测试4J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061分解质量的其他启发式测量;以及4）是否存在可以被识别为对分解质量重要的任何约束特征，因为这可以用于未来的采样过程。在本文中，我们提供了一个广泛的分析ML的方法来排名分解质量的有效性，其中求解时间和边界质量的组合被用作量化分解质量的度量为此，我们创建了一个重要的数据集，其中包含从MIPLIB 2017库中的24个实例中采样的超过40，000个独特分解这些分解是使用[24]中描述的多目标方法创建的，该方法能够使用边界和子问题度量以及贪婪随机选择算法来产生丰富的帕累托最优分解集，以确保数据集保持一定的多样性。我们展示了实例相似性对ML性能的影响，并展示了ML排名函数如何在以文献和在线求解器中发现的四个已建立的启发式函数为基准时产生最先进的预测。我们还展示了哪些约束特征可以有益于指导未来的自动分解框架，包括约束松弛。最后，我们提供了一个总结和未来可能的工作，我们的发现可能会被用于启发式创建完全自动化的分解。本文其余部分的结构如下。第二部分介绍了本文的研究背景和相关工作。我们的主要方法在第3节中描述。第4节详细介绍了实验设计，第5节介绍了结果，第6节总结了本文2. 背景在本节中，我们简要描述了拉格朗日松弛框架，用于对分解的有效性进行经验评估，以及先前的工作，这些工作试图通过启发式或基于ML的方法量化分解质量，贪婪和NSGA-II框架用于创建分解，2.1. 拉格朗日松弛拉格朗日松弛（LR）是一种流行的分解技术，通常在运筹学（OR）社区中实现。LR最常用于识别和放松“正确”的复杂约束集，从而将原始问题分解为多个独立的子问题，这些子问题更容易解决。适合于这种类型的分解的问题显示角矩阵模式，如图1所示。在这个角度约束矩阵中，通常被称为有边块对角矩阵结构，存在复杂的约束Ac和独立的块结构D1，.，Dk.如果去掉这些复杂的约束，子问题D1，.，Dk自然能够被分解和独立求解，希望解决这些子问题的最优性可以比整个原始问题更快地实现，尽管没有保证。J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）1000615λ≥0联系我们联系我们第1章D⎢2D3⎤. . .⎥⎢⎣A···············DKC······Fig. 1.加边块对角矩阵结构。分解的子问题D1，...，Dk包含独立变量，如果去掉复杂的约束条件Ac，Dk可以独立求解.新的拉格朗日目标函数是通过将放松的约束转移到目标函数来形成的，并附加了惩罚项（拉格朗日乘子）。原始和拉格朗日对偶公式的基本实现分别在等式（1）-（2）中示出，其中x是决策变量，c是相关成本，A和b是约束矩阵和资源约束，λ是引入的拉格朗日乘数。虽然这个公式是二元线性规划的代表，但它可以很容易地扩展到混合线性规划。用最优拉格朗日乘子求解这个新的拉格朗日对偶通常能够提供高质量的问题界。此外，新拉格朗日对偶问题的解决方案通常对于原始原始问题几乎是可行的，并且通常可以通过适当的修复启发式算法或嵌入分支定界框架时变得可行虽然LR试图改进对偶和原始边界，但不能保证其性能优于其他MIP求解方法，例如大多数现代MIP求解器所基于的分支和切割[19minXf（x）=cTxS.T. Ax≤ b，Dx ≤ d，x∈{0，1}n（1）maxLR（λ）=min.cTx+λT（Ax−b）：Dx≤d，x∈{0， 1}n<$（2）这里分解的选择对应于如何在A和D矩阵之间划分约束的选择。一般来说，放松的约束越多，原始问题分解得越多，就意味着更容易求解拉格朗日目标。相反，给定一个分解结构，通过取消放松边界来移除因此，LR方法的有效性受到解决非光滑对偶问题（λ上的最小化）的困难以及可以实现的最佳下限（紧松弛）和评估LR（λ）（小的，容易解决的子问题）之间的权衡的影响由于边界质量和求解时间都是评估基于LR的方法的有效性的重要指标，因此在本文中，我们使用这两个指标为分解分配分数，如第3.4.2节所述。还应该注意的是，当应用DWR而不是LR时，可以找到相同的对偶界限。在DWR中，原始可行解集 x：轴b，Dxe，x0，1 n取而代之的是与x：轴b，xconv（y：Dye，y0，1n ），允许整数解的分数组合的子问题，即。可行集的凸包⎥⎦6J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061M子问题的解决方案。列生成是一种有效的方法，然后解决这个新的重新制定，与相应的定价问题是等价的解决拉格朗日目标，从而产生相同的对偶界。为了找到最佳拉格朗日乘子，存在各种各样的潜在方法，包括次梯度优化[11]，束方法[2]，坐标上升[23]和混合技术[10，25]。此外，最佳拉格朗日乘子，也可以找到通过解决主问题的DWR通过列生成。由于对于大型问题，即使只求解拉格朗日目标函数也可能需要大量计算，因此，我们的目标是找到一些能够准确预测基于分解的直接可观察属性的性能2.2. 启发式分解质量度量在文献中，只有有限数量的研究调查一般MIP的分解这些方法可以分为基于启发式的方法和基于机器学习的方法。基于启发式的方法在[5，17，24]中给出，并使用定义的启发式措施研究分解质量其中两个算法[5，17]在第5节中用作基准，最终方法[24]用于生成用于训练和测试目的的分解集2015 年 ， 第 一 篇 论 文 [5] 展 示 了 自 动 分 解 方 法 的 潜 力 ， 在 通 过 Dantzig-WolfeReformulation过程解决分解的背景为了做到这一点，作者将一般混合随机程序的约束矩阵表示为超图，然后他们解决最小权重平衡k划分问题[16]，试图创建k个相等大小的子问题，同时减少找到这样一个划分所需的放松约束的数量没有提出一个框架来发现哪个单一的decomposition应该通过DWR解决，作者而是对不同的参数选择进行探索性分析，特别是创建的k作者还提出了一个启发式的措施，他们建议可以用来从几个候选人中找到良好的分解，将此措施称为相对边界面积（RBA）。正式地，RBA表示为：RBA=ml×n+m×nl−ml×nlm ×n（三）其中m是链接约束的数量，n是链接变量的数量，m是约束的总数，n是变量的总数。小的RBA值表示高质量的分解。然而，作者指出，在测试的39个实例中，有26个实例，没有链接变量的分解表现最好。当不考虑链接变量时，RBA简单地为ml，即放松约束虽然这是一个相当简单的启发式，但作者指出J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）1000617K∀ ∈MMM当放松一些链接约束就足以将问题分解为更易处理的子问题时Goodness score另一个自动分解框架在[17]中提出，并使用社区检测算法来最大化唯一定义的分解质量度量，作者将其定义为Goodness score。正如作者所指出的，一个好的分解可以通过分别分析子问题和边界分量来计算，它们分别被标记为Q和P然后将这些指标结合起来，给出总体良好度分数。子问题和边界分数可以计算如下：关于子问题组件，三个因素被确定为对分解质量很重要：1. 粒度-具有大量子问题的分解是可取的，因为在理论上，解决较小的子问题在计算上是有利的。2. 均匀性-理想情况下，子问题的大小应该相等在并行处理器上求解子问题时，同质性尤其重要，以确保最大的子问题不会支配求解时间。3. 同构-理想情况下，子问题不仅在大小上相同，而且在目标函数系数和右侧值上相同。这导致在拉格朗日松弛算法的每次迭代中需要解决单个子问题，而不是所有子问题。用于测量这些子问题统计数据的总体代理如下所示Q=（ni[1−ni]）（4）���i=1其中，n=i是块i中的非零条目的数量：iK个块，m是约束矩阵的块对角分量中的非零条目的数量。边界成分根据[5]中的结果，在良好评分内计算的边界成分的质量是放松的约束的百分比，尽管是一个简单的指数衰减函数，因为作者注意到边界大小和最优性差距之间的相关性存在非线性用于测量边界质量的总体替代值如下所示P=（e−λ（b））（5）其中b是边界中的约束的数量，M是约束的总数。分解的最终善度得分计算为（Q，P），并在[0， 1]之间有界。具有较大的良好度分数的分解被认为是较高的质量。8J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061MK多目标方法[24]中提出了一种用于自动生成良好分解的多目标方法，并使用众所周知的非支配排序遗传算法II（NSGA II）来创建和进化分解种群。以类似于良好度分数的方式，两个目标被最小化，这已经被证明会导致高质量的分解。多目标算法的目的是最大限度地减少放松的约束（小边界区域）的数量和每个分解的最大子问题的大小这种方法用于生成本文中使用的训练和测试数据集，因为这种框架能够在相对较短的时间内生成大量良好的分解在GCG求解器[12]中，只有在开放源代码中才能找到具有链接约束的一般分解的1为了进行基准测试，我们将此启发式方法标记为GCG开源（GCG OS），并计算为：GCG OS=（0. 6× m）+0. 01+（0. 2×（1 − min {d1，...，（d））（6）其中m是放松的约束的数量，M是约束的总数，并且dk是子问题k的系数矩阵的非零密度。另一个存在的启发式算法是MIPLIB 2017网站上提供的Max-White（MW）分数，用于确定实例是否适合分解。MW分数表示白色区域，对应于BBD结构中所有系数均为0的约束矩阵部分，该部分不在边界块或子问题块中。MW评分计算如下：= 1千克−ni×mi+nb×mb（七）MWi=1n ×m其中ni，mi是子问题i中的变量和约束的数量，nb，mb是边界中的变量和约束的数量，n，m是实例中的变量和约束的数量。具有大Max-White分数的分解被认为具有更高的质量。2.3. 随机抽样和机器学习据我们所知，[4]中的作者是第一个解决如何基于实例和分解特征对分解质量进行先验排序的问题。为此，使用伪随机抽样算法生成分解，训练分类和回归模型以预测帕累托最优解（其中约束质量和求解时间形成两个目标），然后随后1https://gcg.or.rwth-aachen.de/。J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）1000619TP+FPTN+FPTP+FN根据与最接近的帕累托最优解的距离对所选择的分解进行这个框架被称为数据驱动过程。对于分类，在最初的实验中，当每个基本实例的分解被用作测试集，并且分类器在所有其他实例的分解上进行训练时，在测试的36个实例中，除了5个实例外，所有实例都观察到了较差的结果。此外，即使所有实例的分解都包含在训练集中，测试精度得分（P），其中P=TP，也只有0.0714，预测了大量的假阳性，尽管作者指出，由于类分布的不平衡，精度值是不确定的。对于分类结果较差的情况，作者将其定义为具有真阴性率（TNR=TN）和真阴性率（TNR = TN）。 阳性率（TPR=TP）低于0.5，作者给出了两个潜在的原因，在分类过程中产生的不良结果。首先，作者注意到不同实例中的正分解可能没有足够的共同特征，并建议数据集中可能需要更多的正分解。由于这一发现，我们已经在我们的数据集中包含了通过NSGA-II算法创建的分解，如[24]所述，因为这些分解已被证明比伪随机采样过程产生的分解质量更高分类结果不佳的第二个原因是数据集中的实例可能在结构上不同，因此，如果好的分解模式取决于实例的结构，那么包括所有实例的分解进行训练可能是有害的作者建议需要进一步的研究来调查实例相似性的效果和经过训练的分类器的性能。因此，在本文中，我们专注于包括网络结构的问题，希望增加实例的相似性。我们在5.1节中分析了实例相似性的重要性。数据驱动方法的下一个阶段是训练一个回归变量，以便对分类步骤选择的正分解进行排名。虽然有一些有趣的初步结果，正如同一作者在[3]中指出的那样，当用作排名函数时，回归量的性能往往很差在[3]中，作者试图定义一个基于优势百分比而不是Pareto距离的新排名函数，并注意到一些改进。最后，[4]中进行的基准测试仅比较了通过数据驱动过程创建的有限数量的分解与GCG中静态检测器创建的分解缺乏的是ML排名函数如何与其他基于启发式的分解排名函数进行比较，例如Max-White得分[15]，GCG开源代码（GCGOS）中的边界块对角分解的分解得分3. 方法本文件所采用的方法包括四项主要任务，下文将对此作更详细的介绍：10J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061O1. 使用贪婪随机和多目标方法的分解生成。2. 分解后处理，包括删除冗余约束和重复分解。3. 通过使用来自LP松弛的最佳对偶值作为拉格朗日乘子求解用于分解的拉格朗日函数来建立MIP边界。4. 分解结果分析。所进行的分析涉及三个主要领域：• 研究实例相似性与预测性能之间的关系。• 针对相似和不相似实例的启发式技术对ML方法进行基准测试。• 研究松弛约束特征与预测质量之间的关系。3.1. 分解生成正如作者在[4]中所指出的，使用来自任意MIP的随机采样算法不太可能产生有希望的分解。因此，作者实现了一种伪随机抽样算法，以与[24]中讨论的贪婪随机分解类似的方式，选择与其稀疏性成比例的概率的约束对于本文中使用的数据集，我们使用了由NSGA-II算法和贪婪随机方法创建的分解，如[24]所述。我们包括了NSGA-II生成的分解，因为与贪婪随机生成的分解相比，这些分解以前被证明可以产生高质量的分解此外，为了确保数据集不会过于偏向于只考虑多目标方法中使用的两个度量的分解，还包括贪婪随机方法对于这两种方法，被采样的MIP的约束矩阵被转换成超图，其中行由超边表示，列形成超图内的节点一旦创建了超图，就选择要放松的约束集，从而从超图中移除相应的超边然后运行广度优先搜索（BFS）算法来识别现在存在的独立分区，代表创建的独立子问题。BFS算法能够在（n）中运行，其中n是约束系数矩阵中非零项的数量在本文中，我们还介绍了两个后处理步骤，以消除不必要的分解组件，以便更好地过滤数据集。贪婪-随机分解贪婪-随机方法用于生成各种分解，在放松具有大量非零的约束方面存在偏差，希望这样做会导致更多更小的子问题若要创建分解，将根据变量J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）10006111SV它们包含，那么它们被迭代，松弛的概率等于pi=|Vi|×Q × |C|其中pi是约束i被放松的概率，Vi是在约束i中包含的变量，SV是原始问题中所有约束C的集合上的所有变量计数的总和，Q是要放松的约束的期望比例运行此迭代循环，直到选择了所需比例的松弛NSGA-II分解如[24]中所述创建NSGA-II分解。在NSGA-II实现中，拟合函数由两个目标组成：1）放松的约束的数量和2）最大子问题的大小（由变量的数量来初始种群被播种一些贪婪随机解，包含各种不同百分比的放松约束，以帮助搜索探索。任意数量的个人初始化不同数量的限制放松，从5%到99%的总约束。3.2. 分解后处理两个分解后处理步骤已被创建，以消除冗余的松弛约束和重复的分解。为了本文的目的，当将约束称为冗余时，如果放松该约束，则这样做是关于它对分解的求解时间或边界质量的影响的可能性。这并不是说去除这样的约束不会改变可行解的集合分解创建后，我们已经确定了两种方式，其中放松的约束可能被认为是多余的，并且不会对分解质量做出任何检查松弛的约束和由此产生的子问题，松弛的约束被认为是冗余的，如果：1. 所有与约束相关的变量都已经是其中一个子问题中变量的子集。2. 所有与约束条件相关的变量只存在于单变量子问题中.在冗余约束的第一个定义中，如果松弛约束的所有变量都包含在子问题中，将约束从边界移回到子问题不太可能以任何实质性的方式减少子问题的求解时间因此，我们认为这个约束对于分解来说是多余的。在冗余约束的第二个定义中，如果约束中的所有变量都只存在于单变量子问题中，则这些子问题中的变量的解被简单地设置为变量界，而不提供LP界的收紧一个例子是两个约束条件是一致的，12J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061≥图二.约束冗余处理。以绿色和红色显示的是两个可被视为冗余的放松约束示例。以绿色显示的是冗余约束的示例，其中所有的非零都属于一个子问题，在这种情况下，当放松这个约束时，没有子问题的分解。红色显示的是一个约束，其中所有非零值仅在单变量子问题中找到，当求解时，不会提供LP边界的额外收紧图中显示了侧面冗余二、绿色显示的是一个被认为是冗余的约束红色显示的是一个约束，其中所有非零值仅包含在单变量子问题中。这些单变量子问题可能是约束松弛的结果，其中变量不再是任何约束的一部分，而是简单地受到其边界的约束。最后，在所有约束后处理之后，从数据集中删除所有重复的分解。3.3. 建立双重界限为了建立对偶边界，我们仅用原始问题（1）的LP松弛中相应约束的最优对偶值λ求解拉格朗日目标LR选择这种方法有几个原因，可以追溯到[14]。首先，由于所创建的分解数量很大（40，000），运行完整的拉格朗日松弛算法所需的计算时间以及多次迭代的乘数更新程序将在计算上是禁止的。由于每个子问题都试图解决到最优，这个过程可能是非常昂贵的计算。其次，乘法器更新过程的引入增加了另一层复杂性，并且可能导致分解质量依赖于更新过程，对于更新过程，存在各种可用的潜在方法，例如次梯度优化[11]，束方法[2]，坐标上升[23]和混合技术[10，25]。此外，对于这些方法中的一些方法，存在需要进行多次运行的随机元素。第三，用最优对偶LP值求解拉格朗日目标也提供了一个清晰的J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）10006113我i=1我分解的有用性的度量。如果积分性质成立，则最优LP解等价于拉格朗日对偶LR（λ），并且指示当使用LR求解时分解是无用的这是除非找到最优拉格朗日对偶能够比求解LP更快地实现，这在不使用专门算法的情况下求解一般MIP时不太可能发生。最后，也可以通过无交叉的内点法求解LP松弛来获得良好的对偶值，因为这通常比找到最佳基本对偶解要快得多。因此，用最优LP对偶值求解拉格朗日目标似乎是测量分解质量的适当代理，因为它是求解方法不可知的，与求解LP松弛相比，显示出边界质量的最小改进，并证明了解决子问题所需的时间复杂度。当求解拉格朗日目标时，每个独立的子问题都被求解到最优性的1%以内，因为在这个阶段只考虑边界质量，现代求解器可能会花费大量时间来证明最优性。由于约束条件的放宽，可能存在只包含单变量的子问题对于这些子问题，可以使用可变边界而不是通过求解MIP来求解最优性松弛后，子问题按变量大小升序排序，并给出与变量平方数成比例的运行时间限制，子问题变量大小与MIP之间呈线性关系解决时间似乎不太可能。计算了每个子问题的求解时限当ti=（v2/kv2）×CPU其中ti是子问题运行时间，vi是数字的子问题i中的变量，K是子问题的集合，CPU是分配用于求解具有最优LP对偶值的拉格朗日目标函数的总CPU预算。对于最后和最大的子问题，分配了全部剩余的运行时间如果子问题无法在给定的运行时间限制内得到最优解，则使用分支定界过程中找到的最佳边界作为子问题解决方案。如果在这段时间内无法处理根节点，则额外提供60（s）的CPU运行时间，以尝试为子问题建立有效的边界，并避免所使用的MIP求解器发现的潜在边界错误在根节点仍然无法处理的罕见情况下，将子问题作为LP求解并使用LP界限，而不需要花费额外的时间来将子问题作为LP求解计入总运行时间。3.4. 数据集选择在解决第3节中描述的分析过程的第一部分时，关于实例相似性如何影响预测性能，我们从MIPLIB 2017库中选择了三种不同的网络问题类型[15]，形成了我们所说的网络数据集。这三种问题类型-网络设计（ND）、固定成本网络流（FCNF）和供应网络规划（SNP）各自包含从相同优化模型生成的实例为了14J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061表1实例统计：例如，在数据集中显示的是变量总数（var），二进制（bin），整数（int）和连续（int）变量的数量，约束的数量（constr）和非零的数量（nz）。每个实例还显示其属于哪种问题类型实例名称Var斌IntContConstrNZ问题类型cost266-UUE416117103990144612312NDdfn-bwin-DBE3285247508102359855ND德国50-UUM69710886883208820737NDta1-UUM2288060516834395654NDta2-UUE9241118808053268726533NDg200x740148074007409402960FCNFh50x24504900245002450254912152FCNFh80x6320d12640632006320655831521FCNFk16x240b4802400240256960FCNFSNP-02-004-104228350167167228016126512463941SNP粤ICP备05011552号-122143845464546212346129662459205SNP粤ICP备06004052号-1328461494494327473183168668716SNP粤ICP备05011552号-15387778158155371473003481097780SNP粤ICP备05011552号-154902111059110595269033208361138760SNP拼接1k1325332521065051761020兰德neos-4954672-berkel1533630090318488007兰德公司简介11096660804488606456400兰德traininstance2128905278260250101560341531兰德neos-4338804-雪13441260424217016342兰德neos-4387871-tavua4004200002004455423496兰德30n20b81838018318620576109706兰德空气05719571950042652121兰德blp-ic981364013550090717191947兰德空气0310757107570012491028兰德为了解决ML方法如何推广到随机选择的实例，我们还从MIPLIB 2017库中选择了10个实例，这些实例包含代表广泛的潜在不可见实例的我们将由这些实例组成的数据集选择MIPLIB库中的10个实例，使得1）为了便于收紧LP界限，离散变量的显著比例，尽管这不一定总是如此一个要求，因为即使是一些二进制或整数变量仍然可以显着收紧LP界; 2）为了约束处理和分解创建，合理数量的非零能够在合理的时间内运行; 3）预处理步骤，以确保大多数实例的LP边界不是最优的，这是为了有效地对分解进行排序的必要要求; 4）一些容易快速求解到最优性的实例，可能表明不放松约束被认为是最佳分解。完整的实例和实例统计信息如表1所示。3.4.1. 考虑的特征虽然在优化社区中没有关于哪些实例和分解特征直接影响分解质量的共识，但已经发现，最小化链接约束的数量和最大化链接约束的数量是有效的。J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）10006115-××UB∗∗|| ∗相似大小的子问题的BER可以缩小完整性差距，并分别导致更快的分解运行时间[5，17]。最小化放松约束的数量和最大子问题的大小也被证明有利于生成良好的分解[24]。为了利用机器学习模型方法，我们使用了更广泛的特征列表，依赖于子问题统计和边界统计。完整的特征列表可以在附录中的表A1中找到，并且包含[18]和[4]中使用的许多特征，作者注意到存在对分解质量很重要的特征组合。由于计算特征的计算复杂性也是任何未来自动分解框架的一个因素，因此我们只包括最好地解决问题并且计算成本低的特征。附录图A1和A2分别显示了网络和随机数据集的归一化特征数据的分布。 在这些数据集内，所有特征在[Q 1 1. 5个IQR，Q3 +1 .一、5IQR]，其中Q1为第25百分位数，Q3为第75百分位数，IQR为四分位距，分别为9.68%和4.43%。这样的分布突出了使用ML方法的潜在困难，因为特征数据在实例之间可能会有很大差异，包含大量的3.4.2. 训练和测试最后，为了本文的目的，每个实例的最佳分解是达到最低分数的分解，我们将其定义为边界质量（表示为最优性差距（UB−LB100））和解决所有子问题所需的解决时间的组合使用加权和模型[22]，我们将间隙值（g）和求解时间（t）同等重要，得分= 0。5 g+0.5 t，尽管在未来的工作中，该权重可以根据用户要求而改变。所有分解都是在逐个实例的基础上分配分数的，其中所有最优性差距和求解时间都使用Min-Max归一化进行归一化还使用最小-最大然后训练各种回归模型来预测分解分数，以便基于所考虑的特征先验地对分解的质量进行排名。由于ML模型只有在分解质量可以预测的情况下才有用，因此使用近似Leave-One-Out-Cross-Validation [ 21 ]方法进行测试，并在第5节中进一步描述。训练的回归模型包括一些最流行的线性和非线性回归模型以及两种不同的集成方法，包括：1. 线性回归与岭正则化（岭）2. Lasso Regularisation（Lasso）3. 基于径向基函数核的4. K近邻回归（KNN）5. 随机森林回归（RF）16J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061−6. 多层感知器（MLP）7. 使用岭，套索，SVR，KNN和MLP训练回归和线性回归估计（堆叠）8. 使用Ridge、Lasso、SVR、KNN和MLP训练回归的投票Entrance（投票）4. 实验装置Hypergraph分区和NSGA-II算法在Intel i7- 7500 U CPU上运行CPLEX 12.8.0使用单线程来解决所有MIP子问题和LP基准测试。由于可行性原因，所有LR运行的运行时间有限，为300 CPU秒，因为测试的分解总数超过40，000，如表A2所示使用Pagmo框架[6]和默认参数设置运行NSGA-II算法这些设置包括：交叉概率=0.95，交叉分布指数=10.0，突变概率=0.01，突变分布指数=50.0。NSGA-II算法使用300代运行，种群大小为32。虽然证明了良好的收敛性较小的代数，使用帕累托最优解的百分比在第n代，也发现在第n1代作为性能指标，由于我们的超图分区算法的快速运行时间，我们包括300代，以获得更丰富，更多样化的数据集。应该注意的是，对于某些供应网络计划实例，完整的NSGA-II算法无法在分配的运行时间内完成这是由于NSGA-II算法的实现，在分析后发现交叉实现中存在轻微的逻辑错误对于未来的工作，交叉实现中的这个错误可能会被解决，以加快搜索时间，但是为了我们的目的，生成了足够数量的分解用于分析。对于贪婪随机分解，每个实例生成999个分解，其中111个分解是针对特定的放松约束百分比创建的，范围从总约束的10%到90%。测试的分解中还包括未放松约束的分解虽然使用上述方法为每个实例生成了超过10，000个分解所有ML模型都使用默认参数设置进行训练，如Scikit-learn library [20] with Python 3.6.13.唯一的例外是为Lasso和岭线性回归模型选择的α正则化参数，因为这些模型的训练时间相对不显著，因此测试了一系列正则化参数对于Lasso和Ridge模型，选择的α参数分别为0.001和0.01J. Weiner等人 /EURO Journal on Computational Optimization 11（2023）100061175. 结果进行了多个实验，以确定1）实例相似性对ML方法的预测质量的影响; 2）ML排名方法与文献和开源求解器中发现的其他基于启发式的排名函数相比如何？3)哪些松弛约束特征对分解质量很重要？4）在从MIPLIB库中随机选择