0-1二次计划的精确解决方法的计算比较：从业者的建议

摘要

本文涉及二进制二次程序（BQP），这是由于各种应用程序，这是非线性整数优化问题中最良好的非线性整数优化问题。虽然已经提出了许多不同的解决方案方法来解决BQP，但从业者需要高效且易于实施的技术。我们重新审视BQP最广泛使用的三种最广泛使用的线性化战略，并检查在文献中提出的这些配方的增强功能的有效性。我们在五种不同类别的BQP上进行详细的大规模计算研究，以比较这两个线性化，并将非线性整数程序直接提交给优化求解器。目标是为从业者提供有关如何以有效且容易实施的方式解决BQP的指导。

1.介绍

二元二次程序（BQPs）是非线性整数优化问题的最充分研究的课程之一。这些问题出现在各种各样的应用（见[1那2例如])，并且众所周知是np困难的。已经为bqp提出了许多不同的解决方案技术，包括启发式和精确解决方法。由于实现和维护自定义算法的困难，最常用的bqp精确解方法涉及将非线性问题线性化，然后将等效线性形式提交给标准混合整数线性规划(MILP)求解器。有趣的是，大多数商业MILP解决方案都已更新，以处理BQP的直接提交，这提供了一个有吸引力的替代解决方案。

在本文中，我们重新审视了BQPS的两种最广泛使用的线性化策略：标准线性化[3.和格洛弗的方法[4.］.对于这些方法有许多提出的增强，但据我们所知，还没有全面的研究来确定应用这些线性化技术的最佳方式。为了调查这些增强功能，我们利用文献中的五种不同的BQP（无约束的BQP，多维二次背包问题， -项目二次背负问题，最重的 -子图的问题，和二次半分配问题）和三个不同的MILP解算器（CPLEX，GUROBI和XPRESS）。我们还做比较，上海鲁和史密斯[更近的线性化战略5.]并直接向求解器提交BQP。本文的目标是为从业者提供以有效且容易实现的方式解决BQP的建议。请注意，我们的工作与[6.那7.]谁也执行不同的线性化策略的计算研究的BQPs。然而，我们的重点不仅是在比较不同的线性化，但也增强了标准的线性化和Glover的方法如何影响算法的性能。

给出了BQP的一般公式 在哪里和线性和二次代价系数分别是和吗是表示可行域的多面体集合。为了便于记法，我们从此设指标和从1跑到,除非另有说明。注意，对于每个二进制变量， 那因此，可以纳入线性术语不损失一般性。此外，请注意，与产品相关的总成本是 ．因此，即使和被修改，使得它们的和不变，问题依旧。在文献中最常见的两种二次系数表示是要么假设 对所有人 使二次系数矩阵是对称的）或承担 对所有人 使二次系数矩阵是上三角）;这两者可以假定不失一般性。对于我们而言，我们将明确地保留两个方面和 ．注意，这里没有假设是负半纤维矩阵，因此，问题BQP的连续松弛不一定是凸优化问题。然而，关于线性化，客观函数的凹陷与其被重写为线性形式无关。

2.线性化

一的用于优化BQP最广泛使用的技术是利用线性化的步骤，重新表述非线性程序进通过引入辅助变量和约束的等效线性形式。然后线性化模型可以提交给标准MILP求解器。而再形成的规模和不断放宽实力肯定是在一个线性的性能时提交给MILP求解器发挥作用，它并不总是可以推断其配方将会有更好的表现。事实上，采用预处理技术，切割面，启发式，以及其他增强功能使得它具有挑战性的预测2个线性化将如何计算比较。

在本节中，我们将回顾两个最知名的线性化战略，并认为可能影响其计算性能的修改。此外，我们描述了上海鲁和史密斯[更近的线性化战略5.］.

2．1.标准线性化

的标准方法来线性化BQP，由于Glover和伍尔西[3.，就是更换每一种产品在具有连续变量的目标函数中 ．为了简化表示，我们首先将BQP的目标函数重写为 在哪里 对所有人 与 那我们可以在没有普遍的情况下做的。我们现在定义了标准下面BQP的线性化。 受到约束

注意 （4.） - （7.）强制执行 对于所有二进制文件 ．虽然这种线性化方法是直接的，但它的缺点是需要添加 辅助变量和 辅助约束。

正如指出的[8.[我们可以通过使用标志来减少辅助约束的数量 ．让 ：和 ．然后，我们可以省略约束（4.)和(5.）边界从上面开始 那我们可以省略约束（6.)和(7.）边界从下面的 那因为这些将在最优暗示。我们把这种减少的形式并注意连续放松可能可能比那样弱 ．

这导致我们的第一个问题，我们想解决：

问题1:当采用标准线性到BQP，你应该减少配方的基础上，二次目标系数的符号的大小？也就是说，它再形成，性病或性病 那提交给标准MILP求解器时提供更好的性能吗？

我们将在计算研究中解决这个问题。

2.2。Glover的线性化

一种更紧凑的线性化方法是由于GLOVER [4.］.给定问题BQP，该方法替换每个 ）在具有连续变量的目标函数中找到并使用四个线性限制来实施 ．具体而言，格拉弗线性化是如下。 受到约束

为每一个 那 和上上限 那尽管和是下限 ．问题BQP和G1在这方面是等价的，给定任意二进制 那约束(10.） - （13.） 确保这件事 ）对于每一个人 ．注意，这个公式只需要添加（不受限制的）辅助连续变量和辅助约束并且因此比标准线性化更紧凑。

如前所述，二次目标系数的两个最常见的表示在文献中，其一是假设 对所有人 使二次系数矩阵是对称的）或承担 对所有人 使二次系数矩阵是上三角）;这两者可以假定不失一般性。而STD和STD的连续放松强度不受客观函数表示的选择的影响，G1的弛豫值取决于BQP的目标函数的方式表达，如[9.那10.］.这是二次目标系数的事实不要出现在STD或STD的辅助约束中 那而他们做出现在那些G1的。此外，如果二次系数矩阵是上三角，则变量可以从g1中删除，以及相关的约束（10.） - （13.)．要看到这一点，请注意何时是上三角，（10.） - （13.） 确保这件事 因为 对所有人 ．因此，当二次系数矩阵为上三角形时，手套的配方只需要添加辅助变量和辅助约束。此外，当上部三角形，G1的辅助约束比何时少是对称的，当提交给MILP解算器，其可以提供的计算优势。这导致我们的下一个问题，我们将在我们的计算研究解决。

问题2：在制定格洛弗的制剂时，如果您代表二次物镜系数矩阵在上三角形或对称形式？

G1内的边界可以用许多不同的方法来计算。如最初在[4.),为每个 那它们可以很容易地计算为

如[9.，考虑可行域的强边界可以计算为 为 ．这些界限可能通过实施甚至甚至通过实施而更严格地进行x二进制,

虽然可以通过加强价值来突破G1的连续放松 那 那 那和该制剂中的边界，我们需要考虑找到界限所需的计算工作量的数量。这使我们对我们的第三个问题。

问题3：至于整体计算努力制定和使用MILP求解器解决问题G1到最优，我们应计算范围 那 那 那和使用(15.)， (16.）， 或者 （17.）？

正如指出的[11.[我们可以通过去除约束来减少G1的大小（11.)和(13.），其结合由于最大化目标和事实，从下面术语不会出现在问题的其他地方。因此，问题G1可以更简洁地写成修改格洛弗G2: 受到约束

有趣的是，问题G2只需要辅助约束与但G2的持续松弛强度与G1相同。

我们的下一个问题，在计算研究加以解决如下。

问题4：在提交给MILP求解器时，配方G1和G2如何进行比较？

事实证明，我们可以通过替换变量来进一步降低G2中的结构约束的数量 或者 对所有人 那表达变量对于不等式的松弛变量(10.)和(12.）分别（见[11.]）。在执行第一个替代时，我们获得G2A： 受到约束

第二替代产量G2B： 受到约束

请注意，G2A和G2B都仅需要n（非负）的辅助变量和n辅助约束，但它们均具有与G1和G2相同的连续弛豫强度。这会导致我们下一个问题：

问题5：是否有利进行变量替换提交模型的求解MILP时，问题G2减少的G 2a或群G2b？也就是说，怎么办配方G2，的G 2a，，G2B各自比较时提交给MILP求解？

2.3。舍拉利史密斯线性制剂

索尼提和史密斯介绍了更新的线性化[5.］.该方法将BQP转换为下面的线性形式。

受到约束

为每一个 那 和在上部和分别下限，上 那的计算方式类似于(15.)， (16.）， 或者 （17.)．然而，根据初步计算结果，我们将构造采用SS计算为界限（16.)．请注意[5.]实际上推出了三种配方，称为BP， 那和BP-strong，它们都考虑包含二次约束的BQP实例。然而，这三个公式中的每一个都等价于SS对于BQP。执行约束条件所建议的替换后(25.)， SS通过添加额外的元素来增加问题的大小非负辅助变量和辅助约束（26.） - （29.)．

3.二元二次分类计划

在本节中，我们将介绍五种不同类别的BQPs的，我们在我们的计算研究审议和讨论中，产生我们的问题实例的方式。

3.1。无约束0-1二次程序：布尔最小二乘问题

0-1二次问题的第一家庭，我们会调查的是不受约束的BQP（UBQP），使被定义为

虽然简单来说，UBQP非常值得注意的是它代表各种应用程序的能力（参见[2对于最近的一项调查）。对于我们的实验中，我们决定把重点放在布尔最小二乘问题（BLSP），这是在数字通信的基本问题，其中的目的是确定一个二进制信号从一组嘈杂的测量数据中。传统上，这个问题被建模为 受到约束 在哪里 和 给出了。忽略常数项 那我们可以在我们的符号，并通过设置最大化形式改写这一提法 那 那随后定义为 那 为 那和 对所有人 ．

我们随机生成了BLSP的实例，如[1］.具体来说，我们设置了 并生成一个随机具有来自标准正态分布的元素的矩阵 一个二进制向量 与来自均匀分布的元件 ．向量然后构造为 在哪里是一个随机噪声术语，其中元素 ．为每个值生成10个实例 那我们的增量从30到70变为10，以10到70，以提供一系列逐步更具挑战性问题。

3.2。二次多维背包问题

我们考虑的下一类问题是多约束二次背包问题，也称为二次多维背包问题(QMKP)(见[10.那12.]）。这些问题有以下形式。 受到约束

在QMKP中， 那 那 那和系数通常是非负标量。我们假设每一个那 对于每一个人因为其他变量可以固定为0 为了约束是限制性的。

问题是多维背包问题和二次背包问题(QKP)的推广。多维背包问题是QMKP的情况，其中 对所有人 那这样问题就会减少线性形式。QKP保留了二次客观术语，但只有单个背包约束定义 这后一问题是在文献中研究最广泛的非线性离散优化程序之一（见[13.]为了一个很好的调查）。

我们随机生成两个不同的试验台;其两个实例包含与 和10个背包约束。系数是从间隔[1,50]的统一分布中取出的整数，以及整数是否均匀分布在50和 ．

对于第一次试验床，物镜系数是无负的。具体而言，（非零）物镜系数对所有人和 为 与 是从间隔的统一分布[1,100]的整数。评估非零密度的影响和上的CPU时间，这些系数的非零与一些预定的概率 ．我们认为具有概率（密度）的实例 对于每个价值 那为每个值生成10个实例n，它从80变化到110中的10时的增量 从30到70，以10为增量 或10。

对于第二次试验床，物镜系数在符号中混合。具体而言，（非零）物镜系数对所有人和 为 与 从在区间的均匀分布的整数 ．与第一个试验台一样，目标系数的密度从 -以增量为例 ．对于每个价值 那我们为每个值生成了10个实例 那这为10到50的增量为10 那和10。我们使用较小的尺寸作为目标系数，在符号中混合明显更难以解决。

３．３．最重的 -子画面问题

最重的 -子图问题（HSP）涉及确定块加权图的节点，使得由块引起的子图内的总边缘重量最大化[14.］.HSP可以表述为 受到约束

HSP也被称为基数约束的二次二进制程序，是最密集的 -子画面问题， -分散金额问题，以及 -集群问题。对于节点的每个数字， 那我们随机生成了10个具有三种不同图形密度的实例， ．具体而言，对于每个密度和任何一对索引 这样 那我们分配 的概率和 除此以外。我们设置 我们所有的测试。

3.4。 -项目二次背包问题

这 -项目四次背包问题（kQKP)，由[15.那16.]，包括最大化与线性背负约束的二次函数，具有附加的平等基本限制： 受到约束

在这里，我们假设 对于每一个人我因为其他变量可以固定为0 为了限制限制。让我们表示最多的物品可以填充在背包中，即最小的最多数量谁的总和不超过 ．我们可以假设 ．

注意QKP包括两个子问题古典，所述HSP通过丢弃约束（39.）通过丢弃约束来（40)．我们随机产生了两张不同的测试床;这两者都包含随机所选值的实例从以上的范围内离散均匀分布 ．对于第一个试验台，目标系数都是非负的，其中(非零)目标系数对所有人和 为 与 是从间隔的统一分布[1,100]的整数。目标系数的密度变化 -增量为25％。对于每个价值 那我们用 变量。对于第二个试验台，目标系数的标志，其中所述目标系数混合对所有人和 为 与 从在区间的均匀分布的整数 ．与第一个试验台一样，目标系数的密度从 增量为25％。对于每个价值 那我们为每个值生成了10个实例 那在哪里从50到90，以10为增量。

3．5．二次半分配问题:任务分配问题

在这里，我们考虑一个称为任务分配问题的二次半征收问题（QSAP）的特定实例[17.］.一组任务 分配给一组处理器 ．分配任务的执行成本处理器用来表示和之间的通信成本在和在用来表示 ．约束将每个任务限制为完全一个处理器。具体制剂如下。 受到约束

在我们的测试中，我们考虑的两个值（4和5）和三个值(10、12、15)。每一个都是 对，我们生成了10个实例，其中系数和是在区间[−50,50]内均匀分布的整数，如1］.请注意，在我们的测试中，我们改变了QSAP目标函数的感觉，以最大化。

4.计算研究

在本节中，我们试图回答前一节中提出的问题。此外，我们将标准线性化和格洛弗的方法与Shalari和Smith的线性化策略进行比较，并直接向求解器提交BQP。所有测试都是在Python中实现的，并在配备双2.4 GHz Xeon处理器的Dell精密工作站上执行，64 GB RAM运行64位Windows 10 Professional。为了更好地了解独立于求解器的线性制剂的性能，我们使用了三种不同的MILP优化包，CPLEX 12.8.0，Gurobi 8.0.0和Xpress 8.5.0，这是可用软件的最新版本当我们执行计算测试时。我们在所有MILP求解器上使用了默认设置，每个实例的时间限制为3,600秒（1小时）。请注意，为了简洁起见，我们只介绍了我们研究期间生成的数据的子集。但是，在对相应作者的请求时可以获得更完整的数据。

我们使用性能概要，这是Dolan和Moré引入的图形比较方法[18.]到基准优化软件。而不是使用平均解决倾向于由少数难题实例是偏斜倍分析数据，性能概况提供的特定制剂对所有制剂作为最佳时间的解决时间的比例的累积分布函数性能指标。这有效地消除任何异常值的影响，并提供不同的配方中预期的性能差异的图形表示。

为了描述我们的性能曲线具体实施，假设我们有一组的配方和一套的问题实例。对于每个问题和制定 那我们定义

我们比较配方的表现关于问题通过任何关于此问题的任何配方使用的最佳性能绩效比率为

然后,累积业绩概况被定义为 以便为制剂的概率 绩效比率是一个因素最佳比例。因此，例如，是制剂的概率成为解决任何给定问题的最佳配方是制剂的概率以最佳时间因子为3的最佳配方。请注意，性能配置文件还提供了关于未能在时间限制内达到最优的配方的信息。特别是那些不符合要求的档案 表明它们在时间限制内不会解决问题的概率。

4.1。标准线性化的结果

我们首先提出提出的第一个问题：在实施标准线性化时，如果您使用完整的配方或使用基于二次目标系数的标志的制定？也就是说，STD如何与STD进行比较当提交给米尔普求解器时？

数字1示出了用于STD和STD获得的性能对于每类BQP，我们在其中汇总了每个问题类别的所有尺寸和密度，以及三种不同的静验溶剂。注意，因为STD和STD根据目标系数的符号而变化，我们为qmmp和qmmp提供了两个性能配置文件QKP，一个用于具有正反二次系数的实例，一个用于具有二次系数的混合标志的实例。对于读者不熟悉的性能配置文件，让我们检查图中呈现的BLSP的结果1（a）详细。这里， 当我们比较两个配方std和std 那尽管 尺寸 ．然后使用STD和STD解决这150个实例中的每一个 ．对于每个实例，确定了两个制剂的最小计算时间，然后每个配方的计算时间被除以最小时间，从而提供性能比。利用所有情况的计算性能比，然后计算累积曲线，用于一组固定的时间因子比率。回想起那个是概率配方对于任何给定的问题，将具有最快的解决时间。因此，STD的概率将有最快的解决BLSP的时间约为86%，而STD将是最快的配方的概率约为14%。

性能配置文件清楚地表明STD对于所有正在考虑的bqp，更有可能拥有最快的解决时间。而没有在图中显示1，当对所有问题类进行聚合时，STD最快的配方是92％。我们还注意到，更详细的分析显示了STD是优越的制剂无论目标系数密度，问题大小，或MILP的求解器，我们省略为了简洁的细节。

虽然性能配置文件提供一个特定的配方将如何可能有一个更快的解决时间的信息，他们不表明解决时间的实际差异。我们报告的平均CPU时间来解决配方证明最优的图不同BQP类2．这些平均CPU时间是在删除所有实例后计算的，其中至少有一个公式在时间限制内没有解决。也就是说，平均值只包括两个公式在1小时时间限制内都达到最优的情况。注意，性能概要表明，在时间限制内未解决的实例数量相当少。要看到这一点，请回忆那些不符合的配置文件 表明它们在时间限制内不会解决问题的概率。例如，注意，在1小时限制内，用STD制定的Hsp的大约5％的Hsp实例没有解决。数字中的数据2表明STD比STD显著快于平均水平考虑所有BQP类。事实上，对于STD的7个分类的图5中，平均CPU时间还不到性病的一半

因此，我们的结果清楚地表明，在利用标准线性化时，最好使用基于符号的STD无论BQP类、目标函数密度、问题大小或MILP求解器。有趣的是，STD有一个持续的放松，至少和STD一样紧但是以较大的问题大小为代价。我们的测试清楚地表明，STD的较强的连续放松不提供整体计算优势。

4．2．格洛弗公式的结果

在本节中，我们调查了有关格鲁比韦的制定的四个问题。虽然理想情况下，我们将同时调查这些问题，但这样做需要禁止的测试用例。因此，我们以逐步的方式调查问题，使任务更具易行。

我们首先关注回答提出的第二和第四个问题。也就是说，在制定格洛弗的模型时，我们应该在对称或上三角形形式中记录二次物镜系数矩阵，并且如果我们通过去除约束来降低G1的大小（11.)和(13.）获得改性的手套配方G2？为了比较对称二次系数矩阵的使用C在制定G1和G2时，在上三角形式中具有一个，我们取代了在BQP的目标函数中定义如下。为了获得上三角形物理系数矩阵，我们设置了 对所有人 与 和 为 ．为了得到一个对称的目标系数矩阵，我们设 ）对所有人 与 和 对所有人 ．

数字3.给出了考虑的四种不同公式的性能:G1和G2同时采用对称和上三角目标系数矩阵。我们再次汇总了所有目标系数密度、大小和MILP求解器。请注意，当公式G1和G2时，我们计算公式中的边界，如(16.）由于初步计算经验显示这种方法提供了最佳性能。但是，我们将正式比较（15.)， (16.）， 和 （17.）在另一组试验。我们还注意到，计算解决方案时候，我们包括发现G1和G2中的边界所需要的时间。

在图中的结果3.为问题4提供一个相当明确的答案。当使用相同的客观系数表示进行比较时，问题G2优于G1。的确，上三角形目标系数的G2在所有类别的BQPs中最快的概率最高，而对称形式的目标系数的G2在除BLSP和QSAP外的所有类别中最快的概率次之。关于问题2，请注意，G1和G2用上三角形式的客观系数表示的速度都可能比它们各自用对称的客观系数表示的速度更快，除了的例子QKP具有积极的物镜系数。有趣的是，我们注意到，更详细的分析（这里未呈现）显示，具有对称物镜系数的G2也适用于更高的密度（ ）QMKP具有正系数的实例。请注意，性能配置文件还表明，一些配方努力解决时间限制内的所有实例。例如，用对称物镜系数配制的G1和G2不能解决QSAP的大约50％的QSAP实例，而这些配方都不能够解决HSP的所有情况。

我们报告的平均CPU时间来解决配方证明最优的图不同BQP类4.．和以前一样，这些平均CPU时间删除其中配方中的至少一个未在时限内解决所有实例后计算。

数字4.提供在性能配置文件中未捕获的一些其他信息。首先，请注意，虽然图中的性能配置文件3.表明G2优于G1，图4.表明，当用相同的客观表示形式表示时，G1和G2的平均解时间的实际差异几乎可以忽略不计。然而，G1和G2的对称系数和上三角系数表示之间有明显的区别。特别是，用对称目标系数表示的G1和G2的实例通常比用上三角系数表示的各自模型的平均求解时间要长得多。有两个例外，即目标系数对称的g2对于HSP和kQKP具有正系数。

虽然结果不是完全确定的，数字3.和4.表明，在一般情况下，约束条件（11.)和(13.)从G1中取下，得到G2和二次目标系数C应该以上三角形形式表示。我们重申，虽然G1和G2之间的平均CPU时间差异相当小，但对于两个不同的客观函数表示，这些差异相当大。

我们现在尝试回答问题5，该问题5涉及是否有利于执行将G2减少到G2A或G2B的变量的替代。数字5.节目G2，的G 2a和G3B的性能曲线，我们在所有的目标系数密度，大小和MILP求解器聚集。正如我们之前的测试情况下，我们计算出的配方内的范围为（16.)．

注意，通常，G2是最慢的制剂，而G2A和G2B具有相当相当的似况的最快可能性。尽管仔细检查表明，除了具有正面目标系数的QMKP实例之外，G2A对于所有问题类别略有制定。我们报告中图的平均CPU时间6.，计算结果与以前一样。

虽然G2，G2A和G2B的平均CPU次数对于每个问题分类均相当相似，但G2A倾向于是最快的配方。因此，根据我们的测试，我们建议G2应通过替换变量来减少大小 获得G2A。虽然结果肯定不是确定的，但他们确实表明G2A具有最快的配方的概率最高。

我们现在解决问题3关于如何Glover的制剂中的边界应计算。在我们的测试中，我们将计算为界限（15.） 作为弱，那些计算在（16.） 作为紧的，和那样的（17.） 作为严格的．根据我们之前的结果，我们的测试都是使用G2a执行的，使用三种不同的方法来计算边界。我们再次重申，我们的求解时间不仅包括将G2a求解为整数最优的时间，还包括计算公式范围所需的时间。我们的结果如图所示7.我们再次跨越所有客观系数密度，尺寸和摩尔普求解器。请注意，我们不包括BLSP实例，因为这些问题，界限（15.)， (16.）， 和 （17.都是一样的。

有趣的是，请注意，G2A与（15.)往往是最快的配方。我们发现这一结果令人惊讶，因为初步经验表明，16.）均优于。更详细的分析表明，对于较小规模的情况下，额外的时间需要找到的更严密的界限（16.)是不正当的。然而，一旦实例开始变得更具挑战性，紧边界所提供的额外力量(16.）是即使时间去寻找边界增加有利。为了更好地理解这些界限是如何影响CPU的时间，让我们看看图中给出的平均CPU时间8.．

注意，在平均CPU时间方面，G2a用严格的边界(16.）除了实例之外，是所有问题分类的最佳配方kQKP具有积极的物镜系数。而且，不仅缺点（15.）在平均CPU次数方面表现不佳，它们通常比更严格的边界更差。这源于与配制的G2A的连续弛豫强度源于（15.）对于除较小的情况之外的任何内容，对于线性化来说太弱而言是有效的。因此，我们的一般性建议是用紧张的界限制定格洛弗的模型（16.)，特别是对于较大的实例。

我们总结了表中问题1到问题5的答案和建议1．

总之，我们基于五种不同类别的BQP和三种不同阵联求解器的详细计算研究的推荐是使用简洁版本G2a实现Glover的配方，其中具有上三角形物理系数矩阵C在配方中的界限被计算为（16.)．

4．3．精确解的方法比较

在本节中，我们比较了我们推荐的标准线性化和格洛弗方法的推荐版本，STD 那用上三角二次系数矩阵表示的G2a和（16.)，与Sherali和Smith最近的线性化和直接提交到优化求解器。在构建Sherali-Smith模型时，我们利用了(16.）和上三角二次系数矩阵。

如前所述，许多MILP求解器最近已更新为直接处理非凸bqp。在检验我们的研究结果之前，我们回顾了商业MILP求解器用于直接求解非凸bqp的两种典型方法。CPLEX、GUROBI和XPRESS的MILP求解器采用两种不同的策略来求解非凸bqp。第一个策略是将非凸问题转化为一个等价的凸BQP，然后使用标准的凸二次规划技术来求解。这是通过使用标识来实现的 当是二进制。目标函数的二次部分因此可以用 ．一些策略来选择一个以便 将提出负面的Semidefinite，例如亿万的那些。[19.］.第二种策略是利用线性化技术将非凸BQP转换为等价的线性形式，如标准线性化。

对于我们计算研究的第二部分，我们随机生成了一系列从部分中使用的测试问题4．1和4．2．此外，我们还调整了问题实例的大小，以包含更具挑战性的问题(尽管实例的所有其他方面都如本节所示生成3.)．至于问题QMKP的情况下，具有正的目标系数，在10时的增量从110变化以140 以10的增量在50到80之间变化 或10。以目标系数为混合符号的QMKP为例，以10为增量的40到70变化 ．我们改变从20到50以10到50的问题Hsp。对于实例kQKP正客观系数，在10的增量从60变化以90，而对于具有混合符号的目标系数的那些情况下，我们改变从80到110，以10为增量。关于问题QSAP，我们考虑了10个 在哪里 和 ．对于BLSP，我们在此集合已经具有挑战性之前保持了与此前相同的大小。

我们的结果的性能配置文件显示在图中9.，我们再次跨越所有客观系数密度和尺寸。请注意，为了确保问题实例的数量我们只解决了线性化的STD 那G2A和SS与CPLEX，而不是所有三个求解器在第4．1和4．2．我们报告中图的平均CPU时间10.，计算结果与以前一样。也就是说，这些平均CPU时间是在删除所有实例后计算的，其中至少有一个公式在时间限制内没有解决。因此，平均值只包括所有公式在1小时时间限制内求解到最优的实例。

虽然我们曾希望单一策略将出现作为解决所有BQPs不管问题类的最好的办法，结果在图呈现9.和10.显然表明这不是这种情况。实际上，不同的策略似乎对每个不同的问题课程都有优越。我们首先注意到一般来说，BQP的直接提交似乎与提交任何线性重构似乎没有竞争力。事实上，当使用CPLEX，GUROBI和XPRES的二次溶剂时，平均CPU次数通常更高，而不是解决线性化。此外，二次溶剂更可能无法解决所有情况。例如，Xpress求解器不能解决QMKP的大约55％的QMKP实例，其具有混合标志的物流系数。在三个求解器中，CPLEX是最佳的直接提交，这对CPLEX的非膨胀性BQP求解器比Gurobi或Xpress更成熟（CPLEX有能力在GuRobi或Xpress之前良好地解决非膨胀性BQP）．总的来说，我们的测试表明，虽然能够直接向求解器直接提交BQP，但在应用求解器之前，通过用户将问题重新重新制定线性形式，可以显着降低解决方案。

我们现在检查数字的性能概况9.比较线性化STD 那G2a和SS，标准线性化STD具有最高的概率是具有物质系数的QMKP的最快配方，其混合标志和HSP的情况。格洛弗的线性化G2A具有最佳配方的最高概率，以解决Blsp和实例的实例QKP既积极客观系数和混合符号的目标系数。海鲁和史密斯SS的线性曾经有过与积极的目标系数的情况下QMKP的情况下，最快的配方概率最大目标系数为混合符号的QKP，以及QSAP实例。当更仔细地检查数据时，对于密度为75%的HSP，密度为75%和100%的客观混合系数的qmmp，以及密度为75%和100%的情况，G2a是最佳配方QKP具有物流系数的混合标志，致密致密。

就图中的平均CPU时间而言10.，三种线性化之间无显著差异。除STD外，所有的平均解决时间都相当接近应用于QSAP的实例。的确，std.在这门BQP课上表现很差。

通过将所有类别的BQP的测试结果聚合到单个数据集中，我们结束了我们的分析。三种线性化的性能配置文件呈现在图中11.，而平均CPU时间显示在图12.．

我们可以看到的G 2a有最快的解决时间的时候，STD约26％大约38％的时间是最快的重构，而SS是大约34％的卓越制剂。有趣的是，就平均整体CPU时间而言，我们看到了不同的模式。请注意，STD.需要70秒的平均总CPU时间，而只的G 2a需要平均28秒。虽然我们省略了简洁的细节，对数据的仔细检查表明，STD更适合于BQP的较小情况，可能因为大量辅助变量和约束。对于BQP的较大实例，G2A和SS的紧凑性似乎在提交到MILP求解器时提供了优势。

5.结论和建议

在本文中，我们重新审视的标准线性化[3.和格洛弗的方法[4.]用于将BQP重构为线性形式。在五种不同类别的BQPS上使用大规模的计算研究，我们评估了这两个线性化提出的许多增强功能。根据我们的分析，我们建议使用标准线性化重新制定BQP，基于符号的版本STD应该使用。在应用Glover的线性化时，我们建议使用简洁的版本G2A具有上三角形物理系数矩阵在配方中的界限被计算为（16.)．

在我们研究的第二部分，我们比较了性病和G2A配方与少年和史密斯的最近线性化以及直接提交BQP到求解器。我们的分析表明，虽然将BQP直接提交给求解器的方便，但是，用户希望预先执行线性重构本身是有利的。已经说，在许多不同的问题类别上可以良好地获得多孔的越来越成熟的非膨胀BQP求解器。在研究的线性重构中，就具有最快的解决时间的概率而言，在所有问题类别上没有线性化优于所有问题类别。就所有类别的BQPS，G2A和SS而言，就整体平均CPU时间产生了最佳时间。根据我们的分析，我们建议使用STD对于较小的bqp实例，而对于较大的实例，我们建议使用G2a或SS。

数据可用性

用于支持本研究结果的数据可根据要求可从相应的作者获得。

利益冲突

作者声明他们没有利益冲突。