多割与极大割的组合持久性准则

1多割与极大割的组合持久性准则扬-亨德里克·兰格萨尔大学马克斯·普朗克信息学研究所比约恩·安德烈斯马克斯·普朗克信息学研究所博世人工智能图宾根大学保罗·斯沃博达马克斯·普朗克信息学摘要在组合优化中，部分变量分配如果与某个最优解一致，则称之为持久分配.我们提出了多割和最大割问题的持久性标准以及快速组合例程来验证它们。我们得出的标准是基于映射，提高可行的多割，分别削减。我们的基本准则可以用枚举的方法来检验。更先进的依赖于快速算法的上限和下限的相应削减问题和最大流技术的辅助最小削减问题。我们的方法可以作为一种预处理技术，用于减少问题的大小或计算部分最优性保证的解决方案输出的启发式求解器。我们展示了我们的方法在计算机视觉，生物医学图像分析和统计物理这两个问题的实例上的有效性。1. 介绍将图划分成有意义的簇是组合优化中的一个基本问题，在计算机视觉、生物医学图像分析、机器学习、数据挖掘等领域有着广泛的应用MUL-TICUT 问题（又名MUL-TICUT问题）相关聚类）和MAX-CUT问题可以说是划分图的最著名的它们能够纯粹基于节点对之间的成本进行图聚类，因此通常用于对计算机视觉中发生的图像处理和分割任务进行建模[34，3，22，18，5]。以下因素对MULTICUT和MAX-CUT问题的重要性有贡献后者本质上等价于二进制二次规划，它在图像处理中有各种应用。然而，由于计算机视觉模型通常是大规模的，因此基于求解LP松弛的标准求解技术不能足够好地扩展，因此不适用。更重要的是，在全球范围用现成的商业求解器来求解具有分支和切割的最优解是不可行的因此，需要开发专门的启发式求解器，输出高质量的解决方案，为现实世界的问题，尽管最坏的情况下NP-硬度的MULTICUT和MAX-CUT问题。不幸的是，虽然启发式求解器通常可以实现良好的经验性能，但它们通常没有任何最优性保证。具体而言，即使大部分的变量分配计算的启发式同意全局最优解，这样的最优性是不承认的。在这项工作中，我们考虑组合技术的MULTICUT和MAX-CUT 问 题 ， 我 们 可 以 有 效 地 找 到 持 久 性（a.k.a.）。部分最优性）。持久变量赋值附带一个证书，证明它们与全局最优解的一致性。潜在的好处是双重的：（i）在运行原始启发式之后，我们可以计算证书，这些证书表明某些变量是持久的。(ii)甚至在运行启发式之前，我们可以在预处理步骤中确定持久变量分配。在任何一种情况下，问题的大小都可以减少。在第一种情况下，随后的优化与精确求解器加速。在第二种情况下，也可能减少启发式算法的运行时间，并提高解决方案的质量。联合处理MULTICUT和MAX-CUT问题似乎是有益的，因为许多准则都有类似的表述，并基于类似的论点。对于MAX-CUT问题，据我们所知，我们提供了一种计算持久变量赋值的新方法.对于MULTICUT问题，我们的经验证据表明，我们的方法提供了实质性的改进，比以前的工作persistent。我们的经验结果是最显着的非常大规模的问题，目前的物理学几乎不能处理，例如。生物医学图像分割[5]。通过持久化减少问题的大小，我们的方法在这种情况下实现了高质量的解决方案。本文的结构如下。在第2节中，我们回顾了相关的工作。在第三节中，我们在一个共享的紧公式中介绍了MULTICUT和MAX-CUT在第4节中，我们回顾了改进的概念60936094持久化上下文中的映射此外，我们介绍了基本的积木的建设，提高映射的MULTICUT和MAX-CUT问题。在第5节和第6节中，我们提出了我们的组合持久性标准，并设计算法来检查它们。最后，在第7节中，我们评估我们的方法在数值实验的例子从文献中，并比较相关的工作。由于篇幅所限，我们提供了我们的结果的证明以及我们在柔性材料中的实验的运行时间。这些补充还包含了我们的持久性标准的技术改进，为了清晰起见，这些改进在主论文中被省略了。2. 相关工作马尔可夫随机场（MRF）的持久性，作为特殊情况，对于二进制二次优化问题（a.k.a.二次伪布尔优化（QPBO））已经得到了很好的研究。在[31]中观察到，稳定集问题的自然LP松弛具有持久性：LP解的所有积分变量都与全局最优变量一致这一结果已被转移到QPBO [16，6，7]中，并在[45]中进行了扩展，以找到关系持久性，即。表明某些变量对必须具有相同/不同的值。对于高阶二元无约束优化问题，屋顶对偶的概念可以被推广以得到进一步的持久性结果[34，19，26]。超越QPBO的基本LP松弛，持久性证书涉及高阶多项式0/1程序的更严格的LP松弛，这些程序不具有持久性属性（即，积分变量不需要是持久的）已经在[ 1 ]中进行了研究。对于一般MRF，可以初步检查的标准包括死端消除（DEE）[12]。在[44]中可以找到更强大的技术，这些技术概括了仍然可以用于快速预处理的DEEMQPBO方法[24]包括将多标记MRF转换为QPBO问题，随后可以使用QPBO的持久性结果来获得原始多标记MRF的持久性。在[27，28]中已经开发了多标签Potts问题的持久性标准，可以使用最大流计算进行有效检查，并在[14]中进行了改进。在[41]和[38，42，40]中，针对一般离散MRF，提出了基于LP松弛的多标记Potts问题的更强大的标准在[37]中可以找到对隐式或显式用于所有上述MRF标准的在[39]中可以找到对上述持久性技术的全面理论讨论和比较。据我们所知，对于MULTICUT和MAX-CUT问题，在每平方上所做的工作较少.对于MULTICUT，作品[2，29]提出了简单的持久化标准，允许固定一些边分配。我们不是了解MAX-CUT的任何持久性结果。而且，即使在QPBO和MAX-CUT之间存在直接的转换，也根本原因是从MAX-CUT到QPBO的转换引入了当前持久化标准无法处理的对称性更具体地说，已知的持久性标准依赖于改进的映射，但在对称的情况下，总是可以通过利用对称性将标签映射到具有相同成本因此，改进映射的固定点，这相当于持久变量，无法找到。对于密切相关的（但多项式时间可解的）MIN-CUT问题，在[32，17]中提出了一族持久性准则。它们直接转化为MAX-CUT问题，我们在下面的研究中将它们作为特例导出。描述MULTICUT和MAX-CUT问题的更多涉及的约束使得难以直接转移一些可用于MRF的强大的持久化技术。在我们的工作中，我们展示了如何在[37]中开发的改进映射的框架可以用于导出具有更复杂约束结构的组合问题的持久性准则，例如MULTICUT和MAX-CUT问题，一旦确定了一类作用于可行解的映射。具体地说，我们证明了在我们的理论框架中可以导出[29]中已知的MULTICUT持久性准则和[17]中的持久性准则（转移到MAX-CUT此外，我们定义了更强大的标准，可以找到更持久的变量，如实验第7节所示，但可以有效地评估。我们相信，我们的方法组成改进的映射从初等映射是有益的，在寻找更多的持久性标准。3. 多割和最大割让minθ，xθs. t. x∈ X（P）其中X∈ {0，1}m是一个线性组合优化问题。在本文中，我们研究了（P）的具体实例，称为MULTICUT和MAX-CUT问题，这在本节中以数学方式介绍。为此，设G=（V，E，θ）是一个加权图，其中θ∈RE. 我们通过以下公式区分非负边和负边：E+E−，其中E+={e∈E|θ e≥0}且E−={e ∈ E |θ e<0}。 对于任意两个不相交的顶点子集U，W<$V，令δ（U，W）={uw∈E|u∈U，w∈W}表示U和W之间的边的集合。进一步，我们记δ（U）= δ（U，V\U）和E（U）={uv ∈ E |u，v ∈ U}。定义1（多重切割和切割）。 设（U1，. . . ，U ，k）是V的分区，即， U1. . 对于以下情况，则<$U k= V且U i<$U j=<$U6095X我e所有i，j，其中i = j。划分的任何一对分量之间的边M的集合，由下式定义[M=δ（Ui，Uj），a)b）c）1≤i j ≤k称为G的多重割。如果k=2，则M=δ（U）=δ（U）图1.初等映射的图解a）原始多切割x∈ MC（实线）和连通区域U（虚线）。 b）、1 2截映射pδ（U）（x）的结果。 c）连接映射pU（x）的结果。被称为G的切割。对于任何一组边F∈E，定义关联向量 {0，1}EofF via .有两个微不足道的改进映射：（一）被告人的姓名;我们写（F）e=1如果e∈F0其他。tity mappingid：x›→x.它根本不提供任何持久性，因为没有变量是由约束x∈X单独固定的(ii)将任意x映射到a的映射p<$：x<$→x<$MC=、、、CIMM| M是G的多切，固定最优解x<$∈argminx∈X <$θ，x<$. 这张地图-ping显然提供了最大的持久性，即，它修复CUT=.✶Σ| UVMC所有变量，但对于NP-难问题，通常计算x的值是容易的。对于多重割的关联向量集，分别给出了G.多割问题是找到一个最小权w.r.t.的多割θ和可以写成（P）的一个实例如下：最小θ，xθS.T.x∈ MC。（PMC）最大割问题是找到一个割δ（U），U∈V，最大重量（或等效的最小重量为−θ）。因此，它可以w.l.o.g.可以写成（P）的一个实例如下：minθ，xθs. t. x∈ CUT。（PCUT）注意，我们使用min而不是max来符合（P）。4. 改进映射在这一节中，我们引入改进映射作为一个概念，以导出部分最优性结果，并定义ele-history构建块来构造MULTICUT和MAX-CUT问题的改进映射。定义2（[38]）。一个p：X→X的prop-λ映射nθ，p（x） n ≤ nθ，x n x∈X叫做改进映射。将某个变量xi映射到固定值β的改进映射p提供了持久性（也称为部分最优性）：因此，我们对中间立场感兴趣：我们希望找到改进的映射，尽可能多地固定变量（不像id），但在多项式时间内可计算（不像p）。这允许我们通过固定持久变量来简化原始问题（P）。对于MUL-TICUT问题，我们可以收缩那些可以永久设置为0的边，这允许缩小底层图。然而，对于MAX-CUT问题，持久变量的任何值都可以用于收缩，如下所示4.1. 初等映射为了构造MUL-TICUT和MAX-CUT问题的改进映射，我们使用本节中定义的初等映射。定义3（多割映射）。设U∈V是G的一个连通分支的节点集。(i) 初等割映射pδ（U）定义为：pδ（U）（x）= x δ（U）.换句话说，这意味着对于所有边pδ（U）（x）e= 1e∈δ（U）且pδ（U）（x）e=xe.(ii) 初等连接映射pU被定义为：Uv∈E（U）v-路径P，使得对于每个可行元素x∈X，将p应用于x，因此pU（x）uv=λEe∈EP：（一）固定xi=β给出了至少同样好的另一个元素n=0或e∈E（U）引理1（Persistence）. 设p：X→X是改进映射，β∈{0，1}. 如果UV，否则。p（x）i=β <$x∈X，则在（P）的某个最优解x_∞中x_∞ = β。直观地说，初等割映射pδ（U）将割δ（U）加到由x定义的多割上。初等连接映射pU合并与U相交的所有分量，δ（U）X6096δ（U）Fδ（U）δ（U）δ（U）a)b）、图2.对称差分映射的图解a）原始切割x∈ CUT（实线）和切割δ（U）（橙色虚线）。b）对称差分映射p△（x）的结果。参见图1.为了严格地证明初等割和连接映射的良好定义性，我们需要对多割进行以下刻画。事实1（[9]）。 一个集合M∈E是一个多割当且仅当对每个圈5. 持久性标准在本节中，我们提出了基于子图的标准来寻找改进的映射。我们提供的标准，小连通子图，如边或三角形以及一般连通子图的标准。在第6节中，我们提出了有效的启发式算法来检查本节中提出的子图标准。首先考虑单边子图的特殊情况[29]已经对MULTICUT问题的以下准则进行了评估定理1（边缘准则）。设f∈E是一条边，U∈V与f∈δ（U）连通.此外，设β=（1−signθf）/2。如果该委员会认为，|M C|= 1时。θf≥Σ|，P = P MC，β = 0（2）|,P = P MC, β= 0(2)引理2（良定性）。 映射p δ（U）和p U定义明确，即(i) pδ（U）：MC→ MC，对任意连通U∈Vε∈δ（U）\{f}|θf|≥εe∈δ（U）εE+θe，P=PMC，β=1（3）|θ |≥|，P = P|,P = P（四）(ii) p U：MC→MC对于任何连接的UV。贝加尔夫ee∈δ（U）\{f}切割MAX-CUT问题的初等映射充分利用了割的著名性质，即在取（边的）对称差时割是闭的。事实2（[36]）。 设x，y∈CUT.则x△y∈CUT。特别地，由于x<$→x△y是对合（即，它自己的逆）对于任何割y∈CUT，它保持CUT△y ={x△y|x∈CUT}=CUT。 举一个MAX的例子，CUT定义为G=（V，E，θ）和一个割y∈CUT，这种可行集的变换对应于切换对所有e∈E且ye=1的θe的符号s∈，并将常数e∈Eθe ye添加到目标值。如果y对于原始实例是最优的，那么y△y=0对于转换实例。因此，每当我们想要计算对于xf=1的持久性，我们可以通过对任何包含f的cut应用所描述的切换，然后检查xf=0是否持久保持，将实例转换为等效实例定义4（对称差分映射）。 让你去吧。则在（P）的某个最优解x_∞中x_∞ = β。本文证明了定理1的判别准则，证明了将任意x∈X且xf/=β映射到（pf<$pδ（U ））（x），pδ（U ）（x）或p△（x）的映射p：X → X是改进的.定理1中U的简单候选是{u}和{v}，其中f=uv。 对于每个边f∈E检查这些可以在线性时间内完成。所有的u-v-割（将u与v分开的割）可以通过在加权图G上使用最大流技术最小化（2）-（4）的右侧而被一次检查|·|=（V，E，|θ|），分别对于（3），G+=（V，E+，θ）注意，（3）中的条件是比（2）的限制性小。计算G的Gomory-Hu树[13]|·|或G+减少了检查所有边f∈E的准则的总计算工作量，|V|-1最大流问题。5.1.一般子图准则我们给出了一个技术引理，允许推广定理1中所述的持久性准则。初等对称差映射p△δ（U）定义为：w.r.t.引理3. 设f∈E，β∈ {0，1}.进一步，设H=（VH，EH）是G的一个连通子图，使得f ∈ EH. 如果对于每个y∈CUT（H），其中yf=1−β，则存在△δ（U）（x）= x△△δ（U）。一个映射p y：X→X，使得对于所有x∈X，其对H的限制与y一致，即 X|EH = y，我们有换句话说，这意味着，（x）e=1−xe，（i）nθ，py（x）n ≤ nθ，xnpΣΣ6097δ（U）δ（U）F所有边e∈δ（U）和p△（x）e=x e否则。的（ii）py（x）f=β，对称差分映射定义良好，因为事实2. p△的图示见图2。则在某个最优解x∈{\displaystylex∈{\displaystylex∈{\displaystylex}中x∈ {\displaystyle x ∈ {\displaystyle x}= β}。6098vWuUVuwUVuwδ（U）对于所有U∈VH，其中u∈U且v∈/U，a）b）\VHΣ Σθe≥θe，（9）e∈δ（U，VH\U）e∈δ（VH）<$E+则在（P-MC）的某个最优解x_∞中x_∞ = 0。图3. a）推论1中给出的条件比较了三角形周围的内割（- -）和外割（- -）{u，v，w}。b）定理2和3中给出的条件（9）和（10）比较了内割δ（U，VH\U）和外割δ（VH）= δ（U，V\VH）<$δ（VH\U，V\VH）的权重。引理如下：当x|EH=y。 考虑以下特殊情况，当H是三角形子图时。如果满足持久性准则，则对于x的每个赋值，|EH有一个改进的组合初等映射从第4.1节。推论1（三角形准则）。设{uw，uv，vw} ∈E为三角形。设U<$V使得uv，uw∈δ（U），W<$V使得uw，vw∈δ（W）。请注意，当在这些特殊的子图上计算时，- orem2中所述的MULTICUT子图准则与边和三角形准则不同如果H=（f，{f}）对于某条边f ∈ E，则条件（9）转化为Σθf≥θe。e∈δ（f）<$E+如果H是三角形，则H=（{u，v，w}，{uv，uw，vw}）对于某些顶点u，v，w ∈ V，则条件（9）转化为min{θuv +θuw，θuv+θvw，θuw+θvw} Σ≥θ e。e∈δ（{u，v，w}）<$E+(i) 如果θuw+θuv≥θuw+θvw≥Σe∈δ（U）\{uw，uv}Σ|、（五）|,(5)|（六）|(6)定理3（最大割子图准则）. 设H=（VH，EH）是G的连通子图，且uv∈EH. 如果对所有U∈VH，其中u∈U且v∈/U成立，Σθeholds，则xe∈δ（W）\{uw，vw}=0的最优解。e∈δ（U，VH\U）.Σ≥min|θe|、Σ|θ e|Σ、（10）(ii) 如果另外Σe∈δ（U，V\VH）e∈δ（VH\U，V\VH）θuw+θuv+θvw≥θe（7）e∈δ（{u，v，w}）<$E+则在（P-CUT）的某个最优解x_0中x_0 = 0。成立，则对于（P MC）的某个最优解，x ≠ 0。推 论 1 中 的 切 割 的 直 接 选 择 是 δ （ {u} ） 、 δ（{w}）、δ（{v，w}）和δ（{u，v}），如图3a）所示有可能找到更好的削减w.r.t.成本|θ|，但是我们不知道比通过每个三角形的最大流显式地计算它们更有效的技术（不像计算Gomory-Hu树来评估所有边的单个边准则）。我们进一步使用引理3来说明MULTICUT和MAX-CUT问题的一般子图准则.证明了满足以下条件的映射p：X→X注意，如果H是一个单边或三角形，则子图定理3中所述的准则专门针对边cri，分别是三角形准则，其中仅考虑切割δ（{u}）、δ（{v}），分别是δ（{u}）、δ（{w}）、δ（{v，w}）和δ（{u，v}）。6. 算法在这一节中，我们设计算法来验证，对于给定的MULTICUT或MAX-CUT问题的实例G=（V，E，θ），第5节中给出的持久性准则。边和三角形准则可以明确地检查G的所有边，分别为三角形。请注意，巧妙地应用pVH◦ pδ（VH），分别为p△，正在改善。图的所有三角形都可以有效地完成[35]。示意图见图3定理2（多割子图准则）. 设H=（VH，EH）是G的连通子图，并假设因此，我们专注于开发高效的算法-找到满足定理2和定理3的标准的子图H的算法。具体来说，我们提出的例程，（i）检查给定的连接子图H是否uvUVH\UV6099uv ∈ E H。如果miny∈MC（H）θ，y一些持久性标准适用和（ii）找到好的候选人H。我们的方法重复应用所有子程序，直到没有更多的持久边缘被发现。61006.1. 子图求值设H=（VH，EH）是G的一个子图，我们要分别检验它的持久性条件（9）和（10）。现在，对于给定的边uv∈EH，我们可以通过最小化左边的w.r. t来确定（9）是否对所有u∈U且v∈/U的U∈VH成立联合相比之下，对于（10），我们还需要同时最大化右侧，因为它不注意，假设1 i）也意味着一个平凡的MAX-CUT解，因为CUT是MC的.假设1有以下的权宜结果。引理4. 设H=（VH，EH，θ）是满足假设1的赋权图.则降低的成本θ定义为：（13）对所有e∈EH和对任意截δ（U）满足θ∈e≥0，它认为，你也一样。 显然，最小化左手（9）或（10）的边意味着找到最小u-v-cutw.r.t. θ。此外，由于右侧是非负的，Σ0≤e∈δ（U）公司简介Σe∈δ（U）θe。（十四）最小u-v-cut必须具有非负权重。然而，一般来说，H上的权重θ可以是负的，这使得两个优化问题一般都很难。为此，我们通过限制到满足以下假设1的合适的子图H来简化问题我们将在后面看到如何利用这个条件。为了严格地陈述假设1，我们需要简要回顾以下MULTICUT问题的整数线性规划（ILP）MULTICUT问题可以等价地表述为（P-MC），即找到w.r.t.的最小权边集。|它覆盖每个周期，恰好有一个负沿，即所谓的错误或冲突周期[ 11，29 ]。|that coversevery cycle with exactly one negative edge, the so-callederroneous or conflicted cycles [11, 29]. 相应的ILP公式如下：Σ我们的方法利用假设1和引理4如下。首先，我们通过[29]中的快速迭代循环包装（ICP）算法计算包装对偶（12）然后，如果计算出的对偶界表明H有平凡的MULTICUT解（因此对偶解是最优的），我们可以通过在容量为θ的H上应用最大流技术来计算（ 9）和（10）左侧的下界。在MULTICUT问题的情况下，（9）的右侧是常数w.r.t.所以计算H上的Gomory-Hu树就足够了.然而，在MAX-CUT问题的情况这是不够的，因为（10）的右边也取决于U。在这里，对于所有e∈EH，用θe替换θe后，我们需要解决以下最小最大问题.美因河畔|θ|，x+xΣe∈E−θe（11）minUVH：Σe∈δ（U，V\U）天角θS.T.x∈e≥1， 不冲突Ce∈ECu∈U，v∈/UH.ΣΣΣ Σx∈{0，1}E.相关的包装对偶是线性规划-min|θ e|、|θ e|e∈δ（U，V\VH）e∈δ（VH\U，V\VH）.Σ Σ=−|θ |+minθ最大值λ，λ+λΣΣe∈E−θe（12）e∈δ（VH）.+ MaxeUVH：u∈U，v∈/UΣ|θ e|、e∈δ（U，VH\U）ΣeΣΣ|θ e|.S.T.C：e∈ECλ ≥0。λ C≤ |θ e|e∈ E，e∈δ（U，V\VH）e∈δ（VH\U，V\VH）（十五）对于任何对偶可行λ≥0，原始问题（11）的相关降低成本由下式给出：由于解决这个问题似乎是困难的，我们建议解决一个松弛，这是通过替换内部最大项，θe= .|θ e|−ΣC：e∈ECΣλ C符号θ e <$e ∈ E。（十三）Maxα∈[0，1]Σαe∈δ（U，V\VH）Σ|θ e|+（1 −α）e∈δ（VH\U，V\VH）|θ e|假设1. 设H=（VH，EH，θ）是一个赋权图然后交换min和max的顺序。 这产生使得i) 图H有平凡的最优MULTICUT解（15）≥−Σe∈δ（V|θ e|+ Maxα∈[0，1]）minUVH：.Σe∈δ（U，V\U）θe+6101y=0，即miny∈MC（H）θ，yHu∈U，v∈/UHΣΣ Σii) 给出了H上MULTICUT问题的一个最优装箱对偶解λ<$，它对应于y<$αe∈δ（U，V\VH）|+（1 − α）|+ (1 −α)e∈δ（VH\U，V\VH）|.|.6102右边是单位区间上凹的非光滑函数的最大化，可以用二分法有效地求解。在每一次迭代中，内部最小化问题需要针对固定的α∈[0，1]来求解，这可以再次被公式化为最大流问题。为了解决我们的方法中出现的最大流问题，我们使用Boykov-Kolmogorov为了计算Gomory-Hu树，我们使用Gusfield算法的并行实现6.2. 寻找候选子图为了有效地找到好的候选子图，我们采用以下策略。首先，我们通过快速启发式方法（如贪婪边收缩算法[20，23]）计算原始可行解x<$∈X如果启发式解决方案x相当好，那么由x定义的许多组件应该接近最优。因此，在MULTICUT问题的情况在MAX-CUT问题中，我们使用x¯通过第4节中描述的切换操作来转换实例。然后，我们通过ICP计算整个图G=（V，E，θ）的启发式包装对偶解λ<$。候选子图被确定为本文给出了一种新的剩余图（V，{e∈E|θ∈e>0}），其中θ∈如前（13）所述。 这背后的直觉-EGY是通过构造，子图内的边具有比外出边相对更高的权重。这有利于条件（9）和（10）的应用。降低固定成本。此外，当原始解和对偶解都可用时，我们使用以下称为降低成本固定的技术来确定添加其他持久变量。设γ=θ，x−θ，λ−e∈E−θe表示原始-对偶解的对偶间隙对，设γθ<$f，其中f∈E。然后，它如下所示xf=1不可能是最优的，因此我们可以固定xf=0。7. 实验为了研究我们的方法的有效性，我们从文献中收集了200多个实例进行评估。 实例的大小范围为 几百到几亿个变量（边）。我们测量和比较的平均相对大小减少的测试实例，通过应用我们的算法。实例. 对于MULTICUT问题，我们使用OpenGM基准[21]中的分割和聚类实例以及[5]和[33]的作者提供的生物医学分割实例。数据集图像分割包含平面图，表1. 该表收集每个数据集的实例数（#I）、图形大小和实例类型（P）。数据集#我|V||E|P图像分割100156–3764439–10970PMCKnott-3D-1508572–9723381–5656PMCKnott-3D-30083846–589623k-36kPMCKnott-3D-450815k-17k94k-107kPMCKnott-3D-550827k-31k173k-195kPMC模块聚类634–115561–6555PMCCREMI-小型320k-35k17万-23.5万PMCCREMI-大号3430k-620k3.2M-4.1MPMC水果蝇等级145M-11M28M-72MPMCFruit-Fly全球190M650MPMC伊辛链30100–3004950–44850P截骨二维圆环9100–400200–800P截骨3D环面9125–343375–1029P截骨反卷积2100111k-34kP截骨超分辨率2524715k-25kP截骨纹理恢复47k-22k59k-195kP截骨表2.对于每个数据集，该表报告了应用我们的方法后剩余节点和边的平均分数，分别是[29]中的方法（越低越好）。†Fruit-Fly Global的结果没有基于ICP的候选子图。我们[29日]数据集|V||E||V||E|图像分段二十七岁占7%二十七岁百分之四63岁占7%62. 占7%Knott-3D-1509 .第九条。占7%9 .第九条。占6%75. 百分之二88岁百分之三Knott-3D-300五十四百分之八61岁占6%七十六。占7%91. 占6%Knott-3D-45066岁。百分之九七十七。占6%七十七。占6%92. 百分之四Knott-3D-55067岁百分之八79岁。0%的百分比七十七。百分之八92. 占6%Mod. 聚类88岁占7%八十占6%92.0%的百分比八十五百分之一CREMI-小型三十三岁。百分31岁百分之九七十六。占6%75. 百分之三6103之八CREMI-大号44.0%的百分比44. 百分之二83岁占7%86岁。占6%水果蝇等级18. 占7%9 .第九条。占6%二十四岁占6%二十七岁百分之九Fruit-Fly Global†五十六百分之三51岁百分之八七十七。百分之九74岁百分之五从照片的超像素邻接中。Knott-3D数据集包含由电子显微镜获取的体积图像产生的非平面图。模块化聚类集合包含从小型社交网络上的聚类问题构建的完整图。CREMI数据集包含从神经组织的体积图像扫描获得的超体素邻接图果蝇实例是从果蝇脑物质的体积图像扫描生成的。全局问题是这项研究中最大的例子，大约有6.5亿个变量。它代表了目前最先进的局部搜索算法所能解决的问题的极限实例级别1-6104100806040200图像分段CREMI-小型[29]第二十九话ICP表3.对于每个数据集，该表报告了应用我们的方法后剩余节点和边的平均分数，分别是QPBO方法[34]（越低越好）。请注意，由于对称性，后者不适用于原始MAX-CUT实例.图4.该图显示了在使用越来越昂贵的持久化标准缩小实例后剩余变量的平均比例。添加的条件从左到右为：无[]，G+[2]的连通分支，单节点割[29]，边子图[Edge]，三角子图[△]，贪婪子图[贪婪]，ICP候选子图和降低的成本固定[ICP]。对于MAX-CUT问题，我们使用两种不同类型的实例.(i)数据集Ising Chain，2D Torus和3D Torus包含源于统计物理学应用的实例[30]。Ising Chain中的实例假定节点上的线性顺序。 对于任何一对节点 是具有关联权重的边。 绝对值100806040200公司简介权值随节点的距离呈指数线性递减。二维环面和三维环面中的实例分别定义在两个环形网格图上。具有高斯分布权重的三维(ii)数据集去卷积、超分辨率和纹理恢复包含源自图像处理应用的QPBO实例[34，43]，其被转换为我们的MAX-CUT问题的公式。该变换引入了与所有其他节点连接的附加节点到附加节点的切割（未切割）边表示标签0（相应地，①的人。表1总结了所有数据集的实例大小统计信息。结果在表2中，我们报告了MULTICUT实例的平均图大小，这些实例是使用第6节中的算法缩小的。在图4中，对各个持久性标准的贡献进行了分离和比较。从表2和图4中可以看出，我们的标准能够找到比以前工作更持久的变量[2，29]。相对于基线收缩后的图大小[29]，我们的方法对于大型CREMI和Fruit-Fly实例实现了约30-这表明，我们的算法找到持久变量分配，更难检测比从以前的工作的标准。在表3中，我们报告了MAX-CUT实例在每个数据集上的平均图大小减少。对于QPBO实例，我们与QPBO方法进行比较[34]。对于原始的MAX-CUT实例，我们不知道任何基线方法，QPBO方法不适用。在图5中，我们比较了不同子图标准的贡献。可以看出，我们的方法解决了所有伊辛链图5.该图显示了在使用越来越昂贵的持久化标准缩减实例后剩余变量添加的条件从左到右为：无图[A]、边子图[Edge]、三角形子图[△]、ICP候选子图和降低成本固定图[ICP]。实例的最优性，这是由它们的权重的特殊分布促进的。在2D环面上，我们实现了大幅度的尺寸减小，在更密集的3D环面上，我们发现几乎没有持久性。我们在QPBO实例上的结果与[34]的反卷积和超分辨率相当，而我们的方法对纹理恢复不太有效。8. 结论我们给出了MULTICUT和MAX-CUT问题的组合持久性准则此外，我们设计了有效的算法来检查我们的标准。对于MUL-TICUT，我们的方法在普通基准测试和实际情况下进行评估时，比以前的工作对于最大切割，我们是，据我们所知，第一个提出一个算法，计算puts持久变量分配的一般问题。对于QPBO问题的特殊情况下，我们的方法匹配的性能在某些情况下以前的工作我们的研究结果表明，在实践中计算持久变量分配的NP-难图割问题除了获得部分最优性保证外，我们的方法是缩小问题规模的有用工具，因此对于确定全局最优解至关重要。2D TorusSuperRes.百分比（%）|E|百分比（%）|E|我们[34个]数据集|V||E||V||E|伊辛链0的情况。0%的百分比0的情况。0%的百分比n/an/a二维圆环23岁占6%二十七岁百分之九n/an/a6105引用[1] 沃伦山口Adams，Julie Bowers Lassiter，and Hanif D.谢拉里0-1多项式规划的持久性数学运筹学，23（2）：359[2] 阿米尔·阿卢什和雅各布·戈德伯格使用高效整数线性规划的包络分割。TPAMI，34（10）：1966[3] BjoernAndres，J？gH. Kappes，ThorstenBeie r，UllrichK？the，andFredA. 汉普雷希特具有封闭性约束的概率图像分割见ICCV，2011年。[4] Egon Balas和Clarence H.马丁枢轴和补充-一个启发式0-1规划。Management Science，26（1）：86[5] 放大图片作者：Thorsten Beier，Constantin Pape，NasimRahaman，Timo Prange，Stuart Berg，Davi D.放大图片作者：Albert Cardona，Gra- ham W.作者：Stephen M.路易斯？普拉扎Scheffer，Ullrich Koethe，Anna Kreshuk，and Fred A.汉普雷希特Multicut使自动神经突分割更接近人类的认知。Nature Methods，14（2）：101[6] 作者：Endre Boros，Peter L.锤.伪布尔优化。离散应用数学，123（13）：155[7] 作者：Peter L. Hammer，Richard Sun，Gabriel Tavares.二次无约束二元优化问题改进下界的最大流方法。离散优化，5（2）：501纪念乔治·B。丹齐格[8] 尤里·博伊科夫和弗拉基米尔·科尔莫戈洛夫。最小割/最大流算法在视觉能量最小化中的实验比较TPAMI，26（9）：1124[9] Sunil Chopra 和 M.R. 娆 分 区 问 题 。 MathematicalProgramming，59（1[10] 放 大 图 片 作 者 ： Luiz A. Rodrigues ， Fabiano Silva ，Renato Carmo，Andre 'L.P. Guedes，and Elias P.杜阿尔特 gusfield 割 树 算 法 的 并 行 实 现 在 Algorithms andArchitectures for Parallel Processing，第258-269页[11] 埃里克·D Demaine，Dotan Emanuel，Amos Fiat，andNicole Immorlica. 一般加权图中的相关聚类TheoreticalComputer Science，361（2[12] Johan Desmet ， Marc De Maeyer ， Bart Hazes ， andDaughace Lasters.死端消去定理及其在蛋白质侧链定位中的应用。Nature，356（6369）：539，1992.[13] R. E. Gomory和T.C. 胡多终端网络流。Journal of theSociety for Industrial and Applied Mathematics，9（4）：551[14] Igor Gridchyn和Vladimir Kolmogorov。Potts模型，参数最大流和k-次模函数。InICCV，2013.[15] 丹·格斯菲尔德。非常简单的方法，用于所有对网络流分析。SIAM J. Comput. ，19（1）：143[16] Peter L. Hammer，Pierre Hansen，and Bruno Simeone.二次0-1最优化问题的屋顶对偶性、互补性和持续性。Mathematical Programming，28（2）：121-155，1984.[17] Monika Henzinger，Alexander Noe，Christian Schulz和Darren Strash。实用最小割算法。进行中-20世纪20年代算法工程和实验研讨会（ALENEX），第48-61页。SIAM，2018年。[18] Eldar Insafutdinov、Leonid Pishchulin、Bjoern Andres、Mykhaylo Andriluka和Bernt Schiele。Deepercut：更深、更强、更快的多人姿势估计模型。在ECCV，第34-50页[19] 弗雷德里克·卡尔和皮特·斯特兰德马克广义屋顶对偶离散应用数学，160（16-17）：2419[20] Sera Kahruman-Anderoglu ， Elif Kolotoglu ， SergiyButenko，and Illya V.希克斯关于MAX-CUT问题的贪婪构 造 算 法 。 International Journal of ComputationalScience and Engineering（IJCSE），3（3）：211[21] J o¨rgH. 放大图片作者：Kappes，Bj o？ nAndres，FredA.Hamprecht， ChristophSch