GPU加速的大规模整数线性规划求解器

439FastDOG：GPU艾哈迈德·阿巴斯·保罗·斯沃博达马克斯·普朗克信息学研究所萨尔信息学校区摘要针对结构预测中的0-1整数线性规划问题，提出了一种大规模并行Lagrange我们提出了一个新的迭代更新方案解决拉格朗日对偶和扰动技术解码原始解。为了表示子问题，我们遵循[40]并使用二元决策图（BDD）。我们的原始和对偶算法需要很少的子问题之间的同步和优化BDD只需要基本的操作，没有复杂的控制流。这使我们能够利用GPU为我们方法的所有组件提供我们目前的实验结果组合问题的MAP推理马尔可夫随机场，二次分配和细胞跟踪发育生物学。我们的高度并行GPU实现将[40]中算法的运行时间提高了一个数量级数量级。特别是，我们接近或超过了一些国家的最先进的专门的算法，同时是问题不可知论。我们的实施可在https://github.com/LPMP/BDD上获得。1. 介绍在并行计算设备上高效求解整数线性规划是一个开放性的如果处理得当，它将使计算机视觉和机器学习中的结构化预测目前，最先进的普遍适用的ILP求解器往往不会从并行中受益[45]。特别地，用于计算松弛的线性程序（LP）求解器从多核架构中适度地（内点）或根本没有（单纯形）受益。特别地，一般适用的求解器不适合在GPU上执行。据我们所知，不存在实用的和通用的基于GPU的优化例程，并且只有少数用于窄问题类的求解器与GPU兼容，例如。[1、48、58、65]。这一点，以及一般ILP求解器的超线性运行时复杂性，阻碍了ILP在大型结构化预测问题中的应用，从而导致限制最多为中等问题规模通用CPU GPU专门图1.结构化预测的ILP求解器的定性比较。我们的求解器（FastDOG）比Guideline [23]更快，与专用CPU求解器相当，但性能优于专用GPU求解器。FastDOG适用于各种各样的应用程序，避免了为新问题类开发求解器的人力。或者，如在MAP-MRF的特殊情况下观察到的那样，专门求解器的开发困难且耗时[33]。我们认为，加快通用ILP求解器的工作只有有限的成功，到目前为止，由于复杂的控制流和计算的相互依赖性。我们追求一种完全不同的方法，并且不将我们的工作基于ILP求解器的典型组件。我们的方法从一开始就被设计为只使用提供足够并行性的操作来在GPU上实现我们认为，我们的方法位于结构化预测问题的普遍适用性和效率之间的最佳点，如图1所示。与通用ILP求解器类似[15，23]，很少或根本没有努力调整这些问题以使用我们的方法来解决它们另一方面，我们在结构化预测的大型问题的执行速度方面优于通用ILP求解器，并实现了与手工计算相当的运行时间。FastDOG几百件作品[1、48、58、65]440制作了专门的CPU解算器。我们只有通过专门的GPU解算器才能显着超越。然而，快速专业求解器的开发，特别是在GPU上， 是耗时的，并且需要对每个新的问题类重复。我们的工作建立在[40]的基础上，其中作者提出了一个拉格朗日分解成由二元决策图（BDD）表示的子问题作者提出了求解拉格朗日分解的顺序算法和并行扩展我们提出了大规模并行化的GPU服从route- tines双重优化和原始舍入后，他们的求解器进行改进与他们的方法相比，这导致了显着的运行时改进。2. 相关工作通用ILP解算器并行性商业供应商提供的通用ILP解算器[15，23]的最有效实现[45]中给出了最近的一项调查。在ILP求解器中使用并行性的主要方式是：多个独立执行最新技术求解器[15，23]提供了运行多个算法（对偶/原始单纯形，内点，不同参数）的选项，并行地解决同一问题，直到找到一个解决方案。虽然对于最佳算法和参数配置未知的问题来说很容易并且值得，但是这种简单的方法只能在有限的程度上提供并行化加速。并行分枝定界树遍历虽然乍一看很吸引人，但已经观察到[46]，由于利用了改进的下限和上限以及生成的切割，遍历分枝定界树的顺序是至关重要的因此，似乎很难获得显着的并行化加速，许多最近的改进依赖于顺序执行。另一项工作[50]利用GPU并行性进行域传播，以减少分支定界树的大小。并行LP求解器内点方法依赖于计算线性系统的一系列解。该线性代数可以并行化以加速优化[20，49]。然而，对于稀疏问题，顺序单纯形求解器仍然优于并行内点方法。此外，交叉步骤需要获得一个合适的基础，为原始舍入和分支定界搜索的单纯形法重新优化，限制了这个顺序瓶颈可获得的加速。单纯形法比较少直接并行化。该工作[28]报告了并行实现，然而当前最先进的商业求解器在顺序执行的实现中优于它。最近，已经提出了基于深度学习的方法，用于选择要分支的变量[17，43]，并直接计算解的一些容易猜测的变量[43]或改进给定的变量[51]。虽然并行性不是这些工作的目标，但底层的深层网络在GPU上执行，因此整体计算量大的方法很快，并带来了加速。尽管如此，这些并行组件并不能取代求解过程的顺序部分，而是与它们一起工作，从而限制了可达到的总体加速。上述方法在应用于机器学习和计算机视觉中的非常大的结构化预测问题时的缺点是，它们仍然没有足够好地扩展以在几秒钟内解决具有超过百万个变量的问题并行组合求解器对于专门的组合问题类，GPU上的高度并行算法已经被开发出来。对于马尔可夫随机场中的最大后验推理[48，65]，提出了稀疏图和稠密图的双块坐标上升算法[58]。文[1]中提出了一种多割的原始-对偶算法。最大流GPU实现已在[60，64]中进行了研究。虽然上述专门算法的某些部分可能被推广，但其他关键组件不能，限制了它们对新问题类别的适用性，并且每当试图解决不同问题类别时都需要耗时的算法设计。专门的CPU求解器在结构化预测中，有大量关于特定问题类的专门CPU求解器的文献。为了概述MRF特殊情况下所采用的算法技术，我们重新[33 ]第33话。与我们的方法最相关的是所谓的双块坐标上升（a.k.a.消息传递）算法，其优化La- grange分解。已经为MRF开发了求解器[19，30，31，36，37，42，47，58，59，61，62]，图形匹配-ing [54，55，66]，multicut [1，39，52]，多对象跟踪[27]和细胞跟踪[24]。上述算法中的大多数需要更新步骤的顺序计算。我们的工作建立在[40]的基础上。作者提出了一种拉格朗日分解的ILP，可以通过顺序优化，441我X {}∈{0，1}IJ0≤||∈我J∈IJX∈I∈∈∈ IΣXi优化变量i[n]J约束j[m]的可行集J约束j[m]中的变量集i包含变量i[n]β的约束集对于ij子问题j[m]中的j子问题j表1.在我们的问题分解中使用的符号表示法。双块坐标上升方法或可利用多个CPU核心的基于分解的方法。作品[5，6，41]类似地考虑分解成多个BDD，并使用通用ILP求解器解决由此产生的问题。文献[7]研究了多值Lagrange分解的决策图与次梯度方法。延长3.1. 拉格朗日对偶虽然（BP）是NP难解决的，但对单个约束的优化为了利用这种可能性，我们使用类似于[40]的拉格朗日分解来对偶原始问题这使得我们可以通过只解决子问题来解决整个问题（BP）的拉格朗日定义2（拉格朗日对偶问题）。定义约束变量x i的子问题集为Ji={j∈[m]|i∈ Ij}。设子问题j∈[m]的能量为w.r.t. 拉格朗日对偶变量λj∈RIj是E j（λ j）= min x<$λ j。（一）x∈Xj拉格朗日对偶问题定义为：在[26]和[14]中，MaxλΔE j（λ j）s.t.<$λ j= c i<$i ∈ [n]. （D）路由问题。 混合求解器使用混合整数亲，在[21，22，56]中研究了语法求解器的j∈[m]j∈Ji作品[3，8，9]考虑了稳定集和最大割，并提出优化（i）松弛以获得下界[3]或（ii）限制以生成近似解[8，9]。与以前的基于BDD的优化方法相比，我们提出了一种高度并行化和问题不可知的方法，适用于GPU计算。3. 方法首先介绍了最优化问题及其La- grange分解.接下来，我们阐述了我们的并行更新计划，优化拉格朗日对偶，其次是我们的并行原始舍入算法。对于问题分解和二元论，我们遵循[40]。我们的符号总结在表1中以供参考。定义1（二进制程序）。 考虑线性目标cRn和m个约束的可变子集j[n]，其中j [ m ]的可行集j0，1Ij。相应的二进制程序定义为如果各个子问题Ej（λj）的最优解彼此一致，则从将单个子问题解拼接在一起解决了原始问题（BP）。一般来说，（D）是（BP）的下界。（D）的形式推导在[40]中给出。3.2. 最小边际为了优化对偶问题（D）并获得原始解，我们使用定义为定义3（最小边缘）。 对于i∈[n]，j∈Ji，β∈{0，1}letβ= min xλ js. t.xi=β（MM）x∈Xj表示最小边际w.r.t.原始变量i，子问题j和β。定义4（最小边际差）。 对于符号连接-xminncxs. t.xIj∈Xjj∈[m]，其中xIj是对Ij中变量的 限 制。实施例1（ILP）. 考虑0mincxS.T.Ax≤b，x∈ {0，1}n.（ILP）线性约束系统Axb可以分为m个块，每个块表示系统的单个（或多个）行。例如，设a_j_x≤b_j表示Ax≤b的第j行，则该问题可以通过设置I_j={i∈[n]：a_j_i_j=0}而写成（BP）的形式，Xj= {x∈ {0，1}Ij：i∈Ij ajixi≤bj}。让我们也定义一下Mij=m1−mij，（MD）其表示通过（MM）计算的最小边际差如果M ij> 0，那么给变量i赋值0的代价比给子问题j赋值1的代价低，反之亦然。因此，数量M ij表示如果x i固定为1（如果M ij> 0）或0（如果Mij<0），则E j（λ j）增加多少。最小边际函数已经以各种方式用于设计双块坐标上升算法[1，4，19，24，27，30，31、36、37、40、42、47、52、54、55、58、59、61MλM442X20的X32不R−50的2⊥10加递延最小边际差：9对于j∈J，i∈Ij做λj+=ωMij我∈JX {}∈我∈J我我IJ|JI|k∈Jiik我1.提案 在每一次对偶迭代中，我ω∈Jminx∈{0，1}−5x1+x2+4x3+3x4X1：x1+x2+x3≤2，X2：x2+x3−x4=0x3x4x1x2λ1=（−5，0. 5，2），（x1，x2，x3）∈ X1λ2=（0. 5，2，3），（x2，x3，x4）∈X2图2.一个二进制程序分解为两个子问题的例子，每个子问题对应每个子问题由加权BDD表示，其中实心弧模拟将1分配给变量的成本λ，虚线弧具有0成本，该模型分配0。BDD中的所有r−k路径都编码了相应子问题的可行变量分配（以及r−k不可行）。关于当前（非最优）λ的最优分配以绿色突出显示，即对于X 1，x1 = 1，x2 = x3 = 0，对于X2，x2 = x3 = x4 =0。我们的双重更新方案并行处理多个变量，这些变量用相同的颜色表示（例如， x1，x2分别在X1，X2中）。算法1：并行延迟最小边缘。平均法输入：拉格朗日变量λjRi[n]，ji，约束集j0，1Ijj[m]，阻尼因子ω（0，1]1初始化延迟最小边际差异。M=02 while（不符合停止标准）3对于j∈J在平行做其中Mij在（MD）中定义。该更新方案（2）需要包含用于最小边际平均步骤的变量i的所有子问题i为了克服这一限制，我们提出了一种新的双重优化过程，该过程对来自先前迭代的最小边际差异M执行该平均步骤，如下所示<$λ j<$λ j− ωM +M。（三）ik4，对于i∈Ij，按升序，ii ij|k ∈Ji|k∈Ji5计算最小边际差。Mij（MD）6通过（3）更新对偶变量λj7更新延迟最小边际差异。M←M8按照Ij的降序重复第3-63.3. 并行延迟最小边际平均为了利用GPU并行性解决对偶问题（D），我们希望更新多个对偶变量 并联然而，传统的双重更新方案是不友好的并行化。例如，[40]中针对子问题j中的变量i的对偶更新方案为：1<$λj<$λj−M+M，（2）由于M是在前一次迭代中计算的，因此上述对偶更新可以对所有子问题并行执行，而不需要同步。 在[63]之后，我们使用阻尼因子ω（0，1）（0. 在我们的实验中，5）以获得更好的最终解决方案。我们提出的方案在算法1中给出。我们对每个子问题j进行并行求解。对于每个子问题，变量按顺序访问，最小边际值被计算并存储，以便在下一次迭代中更新（第4-5行）。减去当前的最小边际差，并通过在子问题i中均匀分布来添加来自先前迭代的最小边际差（第6行）。在终止时（第10行），我们执行最小边际平均步骤，以考虑上次迭代的延迟更新。对于停止准则，我们使用两个后续迭代之间的对偶目标的相对变化我们初始化输入拉格朗日变量通过λj=ci/|JI|，n∈[n]，j∈Ji.m`in-mar ginalaveragixng可以使用钳子和延迟的最小边缘3不2R0的3⊥2443∈X {}∈我我我Σ我←·X∈联系我们我P {}∪ P\{⊤ ⊥}P我{P P}∀∈ ∈J联系我们·∈J∈J满足对偶可行性，且对偶下界（D）是非减的。与其他双块坐标上升方案类似，算法1可能会陷入次优点，参见[62，63]。然而，正如我们在实验中所看到的，这些通常离最佳值不远在第5节中，我们将解释如果我们将子问题表示为二叉决策图，我们如何可以重复使用以前的计算来递增地计算最小边际这使我们不必从头开始计算最小边际，从而提高了效率。4. 原始舍入为了从（D）的近似对偶解得到（BP）的原解，我们提出了一种基于代价扰动的GPU我们迭代地改变成本的方式，变量分配的子问题同意彼此。如果所有的变量都倾向于一个单一的分配，我们可以重建一个原始的解决方案（不一定是最优的）。而不是只使用变量分配的所有子问题，我们使用最小边际差（MD），因为它们还表明如何强烈的一个变量有利于一个特定的分配。算法2详细描述了我们的方法。我们并行地检查所有变量，并检查最小边际差异。如果对于一个变量i，所有最小边际差都表明最优解为0（分别为：1）拉格朗日变量λ增加（分别为减少），从而为这些变量留下甚至更确定的最小边缘差异。这一步模仿了分支定界中的变量固定，但是我们只通过成本扰动隐式地执行软固定。在最小边际差异相等的情况下，我们随机扰动相应的对偶成本。最后，如果最小边际差异表明冲突的解决方案，我们计算总的最小边际差异，并作出相应的决定。在最后两种情况下，我们为力增加更多的扰动，使之趋向于非冲突。为了加快收敛速度，我们在每次迭代后增加注意，通过Alg.2对于对偶问题（D）不一定是可行的。虽然我们的原始舍入算法不能保证终止，但在我们的实验中，总是在不到100次迭代中找到解决方案。备注。[40]中的原始舍入方案和典型的原始ILP算法[10]是顺序的，并建立在顺序操作（如变量传播）上。我们的原始舍入有助于并行化，因为我们同时扰动所有变量的成本，并通过算法1重新优化。算法2：扰动原始舍入输入：拉格朗日变量λjRi[n]，ji，约束集j 0，1Ijj[m]，初始扰动强度δR+，扰动增长率α输出：可行标记x0，1n1计算最小边际差Miji，j（MD）2当i[n]和jk为s.t.符号（Mij）符号（Mik）do对于i = 1，. - 是的- 是的，n并行做4从[−δ，δ]均匀采样r5如果Mij>0<$j∈Ji，则6λj+=δj∈Ji7elseifMij0<$j∈Jithen8λj−=δj∈Ji9elseifMij=0<$j∈Jithen10λj+=r δji还有11个12计算总最小边际差：Mi=j∈JiMij13λj+=sign（Mi）·|R|·δj∈Ji图14增量扰动：δ δ α15通过算法1重新优化扰动λ16重新计算Mij i，jw.r.t优化λ5. 二元决策图我们使用二元决策图（BDD）来表示可行性集j，j[m]并计算它们的最小边际（MM）。BDD本质上是有向无环图，其两个特殊节点（根和终端）之间的路径编码所有可行解。具体来说，我们使用简化的二元决策图[12]，如[40]中所示。定义5（BDD）。 设一个有序变量集=w1，. . .，wk[n]对应于一个约束。对应的BDD是有向非循环图D=（V，A）特殊节点：根节点r，终端r和r。出弧：每个节点v∈V\{v，v}都有两个后继s0（v），s1（v），出弧vs0（v）∈A（零弧）和vs1（v）∈A（一弧）。分区：节点集合V被1，. . .，k，塞吉i= V， . 每个分区包含所有节点对应于单个变量， i对应于变量w i。它认为1=r，即，它只包含根节点。分划排序：当v∈Pi时，对ik有s0（v），s1（v）∈Pi+1<${n}，对v∈Pk有s0（v），s1（v）∈ {n，n}.<4440⊥{} P {} P {}得双曲正弦值.∈IPP我∈Pλiw∈s1（v）Pm=min<$SP（r，v）+β·λi+SP（s（v），λ）<$（6）定义6（约束集对应）。每个BDD通过以下关系定义约束集Xn（v1，. - 是的- 是的 ，v k，v k+1）∈ Paths（V，A）s.t.x∈ X惠v1=r，vk+1=n，vi+1=sxi（vi）ni∈[k]（四）因此，BDD中根r和终端r之间的每条路径对应于某个可行的变量分配x∈ X。图2和图3示出了线性不等式的可行集合的BDD编码。备注。在文献[12，35]中，BDD有额外的要求，主要是没有同构子图。这允许一些额外的规范性属性，如唯一性和极小性。虽然我们的算法中的所有BDD都满足额外的规范性属性，但对于我们的目的来说，只需要定义5中所需的内容，因此我们保留了这个更简单的设置。5.1. 高效的最小边际计算为了计算子问题的最小边值，我们需要考虑加权BDD。为了符号上的方便，我们将在upcomm中放弃对子问题j的依赖P1 P2 P3 P4图3.含变量I={a，b，c，d}的子问题的加权BDD，代价（λ）分别为2，3，1，4.并且约束a-b-c+d=0。对于每个节点，示出了从根节点a到终端节点a的最短路径成本。这里P1={a}，P2=b1，b2，3=c1，c2，c34= d1，d2s（c2）=d1s1（c2）=.虚线弧的成本为0，因为它们对将0值分配给相应变量进行建模。算法3：前向传递最小边际补偿桩号例如，我们用λi代替λj。1，对于v∈Pi，拉斯 敏SP（r，u），定义7（加权BDD）。加权BDD是一个BDD2SP（r，v）=minu：s0（u）=vARC的成本。设函数f（x）定义为minu：s1（u）=v3 计算mβ通过（6）SP（r，u）+λif（x）=.xλx∈ X我.（五）∞否则加权BDD表示f，如果它满足Def。6因为给定X，i∈[k]，v∈ P，vw∈A的弧成本为 我算法4：反向传递最小边际组合插补设置为.0w∈s0（v）.1，对于v∈ P2i+1do.SP（s0（v），p）， p一期+1变量i的最小边际一个子问题的最短路径距离可以通过计算从r到i中所有节点的最短路径距离和从i+1到i我们使用SP（v，w）来表示节点v和w之间的最短路径距离，加权BDD最短路径计算示例如图3所示。在（MM）中定义的最小边际可以计算为：ββ我vsβ（v）∈Av∈Pi3 计算mβ通过（6）高效的GPU实现除了并行解决所有子问题外，我们还在最短路径更新期间利用每个子问题内的并行性。特别是在Alg。3，我们在所有v上并行化i，并原子地执行min操作。在Alg中也是如此。4我们并行化在所有v∈Pi+1上，但不需要原子更新。为了通过内存合并实现快速GPU内存访问首先，BDD中属于同一分区为了在算法1中进行有效的最小边际计算，我们重用（6）中使用的最短路径距离。具体地，为了计算Alg.1.使用Alg。3为递增变量顺序和Alg.4表示第8行中的降序变量顺序。（因此对应于相同的变量）被连续地布置其次，在不同的BDD中，节点是有序的w.r.t增加距其对应根节点的跳距。图2中的ILP的这种布置在图4中示出。00SP（a，·）SP（·，T）00C11140000一B13334C2D14不21002B2421C31D20∞⊥1我SP（s1（v），λ）+λSP（v，V）= min445X1⊥ ⊥升序X1RX1X1RX2X2降序. -是的-是的专门的求解器：针对每个数据集的最先进的问题专用求解器。对于细胞跟踪，我们使用[24]中的求解器，[55]中提出的用于图匹配的AMP求解器和用于MRF的TRWS[36]。FastDOG：我们的方法是使用CUDA [44]和Thrust [25]编程框架来实现GPU-X2tion.对于舍入原始解，算法2我们设置δ = 1。0且α = 1。二、对于构造-ing BDD出线性（在）等式，我们使用相同图4.用于ILP的GPU存储器中的BDD节点布置在图2中对于Alg中的升序1我们从根节点到终端节点，反之亦然。6. 我们的解决方案包括最先进的ILP求解器[23]、基于BDD的通用求解器[40]和特定问题类的专用CPU求解器我们选择了一些我们在公开文献中知道的最大的结构化预测ILP 。 除 非 另 有 说 明 ， 否 则 我 们 的 结 果 是 在 单 个NVIDIA Volta V100（ 16GB ）GPU上 计算 的 。对 于CPU解算器，我们使用AMD EPYC 7702 CPU。数据集我们从[53]中获得的基准问题可以分类如下。细胞跟踪：来自[24]的样本，我们将其划分为小实例和大实例，如[40]中所做的那样。图匹配（GM）：计算机视觉[57]（酒店，房屋）和发育生物学[32]（蠕虫）中的二次分配问题马尔可夫随机场（MRF）：来自OpenGM [33]基准的几个数据集，包含具有不同拓扑和标签数量的小型和大型实例。我们选择了数据集color-seg，color-seg-n4，color-seg-n8和object-seg。QAPLib：在组合优化社区中广泛使用的二次分配问题的基准数据集[13]。我们将QAPLib实例划分为小（最多50个顶点）和大（最多到128个顶点）实例。对于大型实例，我们使用NVIDIA RTX 8000（48 GB）GPU。算法我们比较以下算法的结果。Guidance：商业ILP求解器[23]，如[40]中所报告。屏障方法用于QAPLib，对偶单纯形用于所有其他数据集。BDD-CPU：[40]的基于BDD的最小边际平均方法。该算法运行在CPU上，具有16个线程的并行化。原始解决方案四舍五入使用其基于BDD的深度优先搜索方案。与BDD-CPU相同。对于MRF，存在[58]等并行算法，但TRWS在我们考虑的稀疏问题上更快虽然我们知道甚至更快的纯原始算法[11，38]的MRF和例如。[29]对于图匹配，它们不优化凸松弛，因此不提供下界。因此，我们选择TRWS[36]用于MRF，AMP[55]用于图匹配，类似于FastDOG，优化等效的响应。类似的拉格朗日分解，因此可以直接比较。结果在表2中，我们显示了每个特定基准数据集的所有实例的聚合结果。运行时采用w.r.t.计算原始边界和对偶边界。附录中给出了每个实例的结果的更详细的表格在图5中，我们显示了各种求解器的平均收敛图一般来说，我们提供了一个非常好的任何时候都可以生产，在大多数时候，一般在开始时，比我们的基线更好的下限。讨论一般来说，我们总是比BDD-CPU快（最多10个因子）[40]，除了蠕虫，我们实现了类似或更好的下限。与相应的手工制作的专用CPU求解器相比，我们还实现 了 具 有 可 比 下 限 和 上 限 的 可 比 运 行 时 间 虽 然Guidelines实现了，如果给定不有限的时间，更好的下限和原始解决方案，我们的FastDOG求解器优于它在较大的情况下，当我们放弃Guidelines早期达到时间限制。我们认为，由于其超线性迭代复杂性，我们在较大的实例上优于Guesthouse当将对偶迭代的数量与BDD-CPU进行比较时，我们需要大约3倍的数量才能达到相同的下限。尽管如此，由于我们每秒可以执行更多的迭代，这仍然导致整体更快的算法。由于我们求解的是一个松弛问题，所以原始解的下界和质量取决于松弛的紧度对于除QAPLib之外的所有数据集，我们的（以及446108104104BDD CPUFastDOG规格·Gurobi-0细胞跟踪图匹配MRF QAPLib小大酒店房子蠕虫C-segC-seg-n4C-seg-n8奥布日塞格小大实例数10510510530399510529nmax1 .一、2M10米0的情况。3米0的情况。3米1 .一、5M3 .第三章。3米1 .一、2M1 .一、4M681k3米49米mmax0的情况。2M二、3米52k52k0的情况。2M十三岁6M4.第一章2M8. 3米二、2M245k2M双目标（下限）↑[23]第二十三话−1.545e8−4.293e3−3.778e3-4。849e43.085e81 .一、小行星9757 e41 .一、小行星9729e43 .第三章。1311e4二、913e64.第一章512 e4[40]第40话. 387 e6-1。549 e8−4.293e3−3.778e3-4。878e43 .第三章。085第八季 1.一、小行星9643 e41 .一、小行星9631e43 .第三章。小行星1248e43 .第三章。675e68. 172 e6专业化-4。385 e6-1。551 e8−4.293e3−3.778e3−4.847e43.085e82.0012e41.9991e43.1317e4--快狗-4。387 e6-1。549 e8−4.293e3−3.778e3-4。893 e43 .第三章。085第八季二、0011e41 .一、9990 E43.1317e43.747e68.924e6主要目标（上限）↓[40]第40话. 337e6-1。515e8−4.293e3−3.778e3-4。小行星783e43 .第三章。086第八季二、小行星1781e4快狗-4。376e6−1.541e8−4.293e3−3.778e3-4。831e43 .第三章。085第八季二、0016e4表2.所有数据集的结果比较，其中值在数据集中取平均值。对于每个数据集，使用[24，34，55]计算相应专业求解器的结果。粗体数字突出显示最佳性能。nmax，mmax：类别中变量和约束的最大数量。GuesthouseBDD CPU-1。5-4。6·规格FastDOG3-1。55-1。6-4。8−5-5。2二、521 .一、51 .一、6510101102时间[s]103-5。4101102时间[s]1031100101时间[s]102103(a) 细胞追踪：大(b) 图形匹配：蠕虫(c) MRF：Color-seg-n8图5.收敛图对数据集的所有实例取平均值。下曲线描绘了增加的下限，而标记表示四舍五入原始解的目标。x轴是按图解法绘制的。7. 结论我们提出了一个大规模并行通用算法，可以解决各种各样的ILP在GPU上。我们的研究结果表明，专门的高效CPU求解器的性能我们的实现是第一个原型，我们推测，更多的加速比可以通过精心设计的实现技术，例如。压缩的BDD表示，更好的内存布局，更好的内存合并，多GPU支持等，我们认为，未来的改进优化算法的结构化预测可以通过开发GPUBDD CPUFastDOG规格·GurobiPrimal Dual obj. （×108）原始和双重目标。（×104）Primal Dual obj. （×104）[23]第二十三话-1。524 e8−4.293e3−3.778e3-4。842 e43.085e8二、小行星8464 e4专业化-4。361 e6-1。531 e8−4.293e3−3.778e3−4.845e43.085e82.0012e4二、小行星7829e4二、小行星2338e41.9991e41 .一、小行星9995e41 .一、小行星4981 e53 .第三章。小行星1525e43.1317e43 .第三章。小行星1322e4五、186e7五、239e7-4.330e71 .一、431 e81 .一、452e8-1.376e8447友好的特定问题求解器，并在我们或其他通用GPU求解器的改进，可以同时受益于许多问题类。另一个未来的途径是优 化来自其他领域的ILP ，例如。在MIPLib基准上[18]。这些问题包括难以表示为BDD的约束，并且需要额外的编码技术[2，16]。8. 致谢我们要感谢所有的评论者，特别是评论者1的宝贵反馈和Jan-Hendrik Lange的深刻讨论。448引用[1] 艾哈迈德·阿巴斯和保罗·斯沃博达RAMA：一种基于GPU的快速arXiv预印本arXiv：2109.01838，2021。一、二、三[2] Abel Abo，Robert Nieuwenhuis，Albert Oliveras，EnricRodr 'ıguez-Carbonell，and Valentin Mayer-Eichberger.伪布尔约束的bdds新观点。Journal of Artificial IntelligenceResearch，45：443-480，2012. 8[3] Henrik Reif Andersen，Tarik Hadzic，John N Hooker，and Peter Tiedemann.基于多值决策图的约束存储。在约束编程的原则和实践国际会议上，第118Springer，2007. 3[4] Chetan Arora和Amir Globerson一致性多目标跟踪的高阶匹配。在IEEE计算机视觉国际会议论文集，第177-184页，2013年。3[5] David Bergman 和 Andre A.Cire. 基 于 决 策 图 的 分 解Claude-Guy Quimper，编辑，约束编程中AI和OR技术的集成，第45施普林格国际出版社.3[6] David Bergman和Andre A Cire。状态空间分解的离散非线性优化。管理科学，64（10）：4700-4720，2018。3[7] David Bergman ， Andre A Cire ， and Willem-Jan vanHoeve.决策图的拉格朗日边界。约束，20（3）：346-361，2015年。3[8] David Bergman，Andre A Cire，Willem-Jan Van Hoeve和John Hooker。决策图优化，第1卷。施普林格，2016年。3[9] David Bergman，Andre A Cire，Willem-Jan van Hoeve和John N Hooker。用决策图进行离散优化INFORMS Journal on Computing，28（1）：47-66，2016.3[10] 蒂莫·贝特霍尔德。混合整数规划的原始算法2006. 5[11] Yuri Boykov Olga Veksler和Ramin Zabih通过图割的快速近 似 能 量最 小 化 IEEE Transactions on pattern analysisand machine intelligence，23（11）：1222- 1239，2001.7[12] 兰德尔·E·布莱恩特基于图的布尔函数操作算法。计算机，IEEE Transactions on，100（8）：677-691，1986。五、六[13] Rainer E Burkard ， Stefan E Karisch ， and Franz Rendl.QAPLIB–a Journal of Global optimization ， 10（ 4 ） ：391-403，1997. 7[14] Margarita P Castro ， Andre A Cire ， and J ChristopherBeck.基于mdd的多商品提货配送tsp拉格朗日方法。INFORMS Journal on Computing，32（2）：263-278，2020。3[15] Cplex，IBM公司CPLEX优化工作室12.10，2019。一、二[16] M.藤田湾Lu、E. Clarke和J. Jain。基于abdd抽样的有效变 量 排 序 。 设 计 自 动 化 会 议 ， 第 687-692 页 ， LosAlamitos，CA，美国，2000年6月。IEEE计算机协会。8[17] MaximeGasse，DidierCh'telat，NicolaFerroni，LaurentCharlin和Andrea Lodi。图卷积神经网络的精确组合优化arXiv预印本arXiv：1906.01629，2019。2[18] Ambros Gleixner ， Gregor Hendel ， Gerald Gamrath ，Tobias Achterberg，Michael Baiderbe，Timo Berthold，Philipp M. Christophel，Kati Jarck，Thorsten Koch，JeffLinderoth，Marco L übbeck e，HansD. 放大图片创作者：PeterD. 作者声明：Dr.MIPLIB 2017：第六届混合编程库的数据驱动编译。数学规划计算，2021年。8[19] Amir Globerson和Tommi S Jaakkola。修正最大乘积：MAP LP松弛的收敛消息传递算法。神经信息处理系统的进展，第553-560页，2008年二、三[20] Jacek Gondzio和Robert Sarkissian。结构化线性规划的并行边界点求解器数学规划，96（3）：561-584，2003. 2[21] JaimeEGonza'lez ， AndreACire ， AndreaLodi 和 Louis-Martin Rousseau。基于BDD的二次稳定集优化问题。离散优化，第100610页，2020年。3[22] JaimeEGonza'lez ， AndreACire ， AndreaLodi 和 Louis-Martin Rousseau。集成整数规划和决策图搜索树及其在最大独立集问题中的应用限制，第1-24页，2020年。3[23] Gurobi Optimization，LLC. Guesthouse Optimizer参考手册，2021年。一、二、七、八[24] Stefan Haller 、 Mangal Prakash 、 Lisa Hutschenreiter 、Tobias Pietzsch 、 Carsten Rother 、 Florian Jug 、 PaulSwoboda和Bogdan Savchynskyy。大规模分配跟踪的原-对偶求解器。在AISTATS，2020年。二三七八[25] 杰瑞德·霍伯洛克和内森·贝尔Thrust：A parallel templatelibrary，2010.版本1.7.0。7[26] John N.妓女改进了决策图中的作业排序界限在ThomasSchiex和Simon de Givry，编辑，约束编程的原则和实践，第268-283页施普林格国际出版社. 3[27] Andrea Hornakova ， Timo Kaiser ， Paul Swoboda ，MichalRo-linek ， Bodo Rosenhahn ， and RobertoHenschel.使高阶MOT可扩展：提升不相交路径的有效近似求解器。在IEEE/CVF计算机视觉国际会议论文集，第6330- 6340页，2021年。二、三[28] Qi Huangfu和J. A. J·霍尔对偶修正单纯形法的简化。数学课程。Comput. ，10（1）：119-142，2018. 2[29] Lisa Hutschenreiter ， Stefan Haller ， Lorenz Feineis ，Carsten Rothe r，DagmarKainm üller，andBogdanS a vchyns k y y. 融合移动图形匹配。2021. 7[30