社交网络论文翻译.docx

分块解决:迭代搜索策略组合优化问题摘要：分支定界和分支切割使用搜索树来确定组合优化问题的最优解。在本文中，我们介绍一种迭代搜索策略，我们称这种方法为分块解决的最优性以及终止证明。这是一种不同于传统的没有分支的搜索树的搜索方法。在每个节点的搜索路径中，一个容易解决的问题和一个稀疏的问题将被解决，并且会向易解决的问题附加一个约束条件。会向稀疏的问题提供一个现有的解决方案。当约束条件变得十分的紧凑，那么它解决问题的价值就不如现有的解决方案。在这一点上，现有的解决方法是最优的。使用这种策略很容易在一个任意时间算法内，发现搜索树节点上的最优的解决方法。分块解决方法有两个比较好的优势。因为没有分支，所以在搜索树之中不会出现错误的分支树，这种错误的分支树会在进行搜索时，使得搜索路径丢失，找不到正确的解决方法。因为这些原因，所以这种方法可以用来很好的解决使用深度优先算法和最优算法无法解决的难题。在本文中，我们证明了分块解决方法对于解决非对称旅行问题与策略推销员问题（ATSP）是可行的。我们的最优算法，在用于解决ATSP问题时，优于国家最先进的分析仪器。这个没有经过优化的算法对于解决一些还没有被解决的难题有十分好的效果，就像ASTP问题中的“七桥问题”这类问题延展出的五类实际问题。对于现在存在的四个类似的问题，使用分块解决方法是十分有可能解决的。我们的代码都已经发布到我们的网站上了。关键字：搜索策略；分支定界；分支切割；任意时间算法；线性规划；旅行商问题。1.简介生活之中充满了优化问题。我们正在不断的寻找最优秀的算法来降低成本，时间，能量，或一些其他有价值的资源，或最大限度地提高性能，利润，生产，或其他一些理想的目标，同时满足在解决这些问题是需要考虑的约束条件。优化问题是很有趣的，经常有一个非常大的可行的解决方案，可以满足带有许多约束条件的问题；挑战在于通过搜索这个庞大的解决方案空间，确定一个最优解。当解的数目非常大的时候，这两个搜索策略，分支定界 4 和分支切割 28 ，已被证明是非常有用的。分枝定界使用搜索树来确定一个最佳的解决方案。（注意：可能有一个以上的优化解。）如果整个树的生成，每一个可行的解决方案，将由至少一个叶节点代表。对于搜索树的遍历和随意的变化，原来的问题是在每个节点进行解决的。由现在的解决方案，可以推导出其子问题的解决方法。其他发现这种类型的解决方案，既需要进行更新，始终保持最佳的可行的解决方案。当搜索树对于解决较小问题表现的不是很好时，现在的解决方案可以被认为是最优的解决方法。如果解决方案的数目太大，允许显式地进行对比，然而搜索树太大是要进行全面的探讨。分支定界的力量来自它的剪枝规则，它允许修剪不必要的分支树以保证整个子树的最优性。如果搜索树被修剪到一个足够小的尺寸，就会显现出来问题解决方案的最优性。分支切割提高分支定界修剪的概率。在一些或所有的节点，为切割面 28 添加收紧或松弛子问题。对于松弛子问题，这些切割平面会删除一组解决方案。但是，为了确保最优解，这些切割平面在进行设计时，不排除任何可行的解决当前收紧问题的方法。当切割面可大幅度减少花费在每一个节点上的时间时，这些减少的时间可能会大大减少搜索树的大小，这已经被用来解决大量以前难于解决的问题。因为分支定界和分支切割对于线性空间的要求以及其他有利特征的要求，所以通常用深度优先的算法实现这种解决方案 49 。然而，深度优先搜索可能遇到的问题是，对于探讨的问题不存在最优解，即不存在最优子树，这将会导致在进行搜索时，花费较大的搜索成本。在进行子树选择时，如果选择了一个错误的子树，那么在进行早期的探索过程中，用深度优先算法是很难发现这个错误的，因此不可能较早的及时的对问题进行纠正。而对于这一缺点，现在的人工智能领域已经投入了巨大的精力寻求解决这一问题的办法。分枝技术 4 ，启发式算法研究 42 ，和搜索技术，像有限的差异 24 和随机并重新启动 19 一直在努力解决这种持续性发展问题。在本文中，我们介绍一种迭代搜索策略，克服了用深度优先算法解决分支定界问题时容易选择错误的分支树的问题，并且对于要求的存储保存也会满足。我们称这种搜索策略为分块解决，并展示它的整数线性规划。作为一个迭代策略，它没有复杂的搜索树，只存在一条搜索路径。换句话说，在每个节点只有一个孩子，所以没有必要选择哪个孩子节点，用来对以后的结果进行预测。在每个节点的搜索路径中，两个相对简单的子问题都解决了。首先，一个松弛问题得到了解决。然后通过求解稀疏问题，对于每一个含有庞大数量的解空间，寻找每一个可能的解决方案，而不是寻找一个最佳的解决方案。现有的解决方案是在发现的第一个节点之后，对后续发现的节点进行持续的更新。当搜索终止后，当前的解决方法可以保证得到的是最佳的解决方案。在本文中，我们证明了最优性和终止的分块解决策略。本文的结构如下。在下一节中，会详细的讨论分支定界和分支切割问题。接下来的章节中，会介绍分块解决策略的扫描方法，并将它与其他的解决方法进行比较。接下来，我们会举例说明分块解决策略在一个简单的线性规划问题中的应用。然后，介绍一个已经实现的切割算法。这个算法对于非对称旅行商问题（ATSP）的证明有很好的实现。我们已经测试了一个初步的，未经优化的算法，并比较它与分支定界和分支切割法的性能的差异。我们的测试表明，对于一些简单的问题，分块解决策略的速度不一定总是比国家最先进的求解仪器计算的速度快一些。然而，对于“七桥问题“的五个实例，这种策略能够更好的解决，它的解决方案比其他的都要更加的优越。在本文的以下内容中我们将会对它进行详细的介绍。2.背景介绍在本节中，我们定义了一些术语，用于更详细的描述分支定界和分支切割。并且使用非对称旅行商问题（ATSP）为例，对这些术语加以说明。分支定界和分支切割已被用来解决各种优化问题。在本文中，我们已经将这种方法运用到任何一种实例之中。但是，为了让我们的讨论更具体一些，所以，在本文中我们将会专注于介绍整数线性规划（IPS）问题。一个IP既是一个优化问题，受到一组线性条件的约束。IP地址已被用于模拟各种各样的问题，如旅行商问题（TSP） 22,36 ，约束满足问题（CSP） 15 ，以及网络优化问题 45 等。此外，许多问题都可以扩展出一个更一般的问题。TSP的应用包括大量的调度，选择，和规划问题，如无等待流水作业，堆垛机，倾斜钻孔机，电脑磁盘的读取头，机器人的运动，以及公用电话钱币收藏的问题 30 。此外，TSP问题可以为各种各样的难以解决的问题建立模型，如最短的超弦问题，这是遗传学的研究方向；CSP是否用于模型配置，设计，诊断，时空推理，资源分配，图形界面之间的调度问题 15 。最后，网络优化问题的例子包括：延迟容忍网络，蜂窝无线网络基站的位置，和在无线ad hoc网络中最小组播的问题。存在可以转换为IP地址的计算机科学，几乎可以应用于各个领域研究的问题。此外，还有一些商业应用程序，也可以转换为IP。一般的IP可以写成以下形式：Z = min (or max)cixi (1)subject to: a set of linear constraints (2)xi I (3)在上面的公式中，Ci值代表特定的常数，集合Xi代表决策变量。约束条件（2）是常数，决策变量，可能还有一些辅助变量组成的线性等式或不等式。约束条件（3）执行的是决策变量的完整性。一个可行的解决方案满足约束条件2和3，并且构成一个可行的解集。所有的可行的解集构成一个解空间，SS。解空间是由给定的条件确定的。与此相反，搜索空间由用来解决问题的算法定义。一个最佳的解决方案是根据目标函数定义（1），求得最小（或者最大）值。 线性规划（LPS）类似于IP地址，他们之间的差别仅在于LPS允许使用决策变量实数。一般唱片具有相同的形式，就如上面给出的遗漏约束条件（3）的常规的IP。LPS可以解决使用椭球方法 33 的多项式时间问题。然而，在实践中的单纯形法 13 是常用的，尽管指数时间是最坏情况下的运行时间 31 。沿多面体的边缘的单纯形算法的移动由约束定义，总是提高解决方案的方向。通常这种方法是非常有效的。 相反，大多数的IP地址不能在最坏情况下解决多项式时间问题。例如，ATSP是一个NP难的问题，可以由下面的IP定义： 2.1.使用范围不失一般性，我们只讨论在本文其余部分的最小化问题。一个IP地址可以由放松一个或更多的条件约束进行放宽处理。这种放松约束条件的方法得到的最佳解决方案不能超过原问题的最优解。此外，该松弛问题的解空间，SS的解空间，包含原始的问题，SS的整个解空间是单点登录的，但是，反过来就不一定正确。一个IP可以通过加强一个或更多的约束条件或添加额外的限制条件进行收紧。这种紧缩方法是通过修改问题的上界，为收紧问题寻到一个最优解决方案，但是，这个方案，不能超过原问题最优解的一个最小值。此外，原问题的SS解空间，包含解空间的紧缩问题，SS的解空间问题，但是，反过来就未必正确。总之，SSTSSSSR。例如，ATSP可以完全放宽约束条件（7）。这个放宽条件允许任何数量的解空间中存在分量。这种轻松的问题是简单的分配问题（AP） 39 。AP是找到最低的成本的匹配，在构造一个二分图时，可以包括所有的弧和两个构造节点。在代表每个城市的节点中，一个节点用于所有输出弧的尾部，一个用于所有的头传入弧。图1描述了对49个城市的TSP对称AP松弛的解决方案。STSPs是一个特殊的类，这个类的成本是由城市I到城市J，它与从城市J到城市I的成本相同。另一个松弛问题可以通过放宽约束完整性的要求，实现（8）。这可以通过更换条件的限制（8），进行实现。限制如下：这项放宽约束条件的变换将IP到LP和称为 25,26 卡普松弛。图2描述了一个解决方案的49城市的卡普松弛。猛的一看，似乎取消子树的限制，也是违反规定的。然而，约束（7）不存在这种问题。 将ATSP问题收紧的方法之一是通过增加约束集，决定选择决策变量的值。例如，添加XIJ = 1，弧（i，j）被包含在所有的解决方案之中。2.2.分支和边界搜索1958，出现许多的论文，使用分支定界搜索 5,12,16,43 。该方法将搜索空间分成一个树形结构。在树的不同级别中，分枝规则是用来产生树的子节点。孩子节点的双亲节点作为约束加入决策变量的设定值。每个节点都继承了来自其祖先节点的所有约束条件。这些紧缩问题代表的子问题，以及父问题和紧缩条件可能会减少他们自己的解的空间的大小。在每个节点的原始问题的松弛已经被解决了。这种放宽条件可增大节点的解空间。因此，在根节点，一个松弛的问题就解决了。在其他的节点，一个双改性问题得到解决；一是同时收紧和放松。这些双重定义解空间问题可能包含额外的解决方案，是不是原问题的解空间可能丢失的解决方案，可以从原来的问题说明得到答案，就如下面的例子所说明的一样。考虑Carpaneto，DellAmico和托特（CDT）提出的实现分支定界搜索的ATSP7算法，如图3所示。在这个算法中，AP是用于减少约束条件，允许任何数量的分量出现在解决方案之中。该分支规则规定需要强制包含和排除的弧。没有被该分支规则约束的弧，称为自由弧。分支规则选择在AP中具有最少的子回路，作为每个子节点的自由电弧排斥。此外，每个子节点后的第一个的弧的兄弟节点被排除在外。更正式地说，给定一个父节点，让E表示其设定的排除弧，I表示一组包括弧和节点 a1，a2，an 的回路。在这种情况下，孩子节点与第k个孩子节点有EK = E AK 和IK =IA1.AK1 。因此，K是孩子节点通过添加约束条件形成的节点，E为圆弧的决策变量，等于零，其余的部分为收紧弧I。当孩子节点K被加工，AP与这些额外的约束条件组合，进行求解。解决方案这种双改性的问题，是所有包含在EK中的弧。然而，它是在所有不属于一个单周期的AP中加入并扩大约束，求得不包含在EK弧中的解，但是这个解包含所有的弧IK。与CDT算法实验相比，本文的部分解将会进行优化。2.3.戈莫里削减在五十年代后期，戈莫里提出了一种迭代的搜索策略，在切割面进行了系统的推导并应用于一个松弛问题 20 。一个切割平面的例子如下：假设我们有三位二进制决策变量，x1，x2， x3，一个计算式，10x1 + 16x2 + 12x3 20，和完整性松弛条件，它是观察到以下的减少可能被添加到的问题：x1 + x2 +x3 1，不删除任何的解决原来的问题。然而，解决方案将被移除轻松的问题（如，x1 = 0.5, x2 = 0.25, and x3 = 0.5)。戈莫里削减收紧松弛问题的解空间的一部分，通过去除约束，这些削减不会缩紧原来（未松懈）的问题解空间，可以用来解决原来没有被删除的问题。然而，去除约束条件以后，问题的解趋于增加，为下一个容易理解的解决方案，发现并且解决了非松弛的可能性问题。这样的解决方案可以用于建立或更新现有的解决方案。加入削减和松弛条件，求解松弛问题直到使得问题再次收紧并变得紧缩，它的解决方案与现有的解决方案拥有同等的解决效果。在这一点上，搜索是终止现有的解决方案的优化。2.4.分支与分割搜索切割搜索是在分支定界搜索与切割面添加在一些或所有节点。这些切割面收紧问题增加了两个潜在的解决方法。首先，对解决这一问题的价值可能会增加（并不能减少）的紧缩。如果这样的增加使得值大于或等于现有的解决方案的价值，那么整个子树可以减掉。第二，推出一套简单的解决方案可能会增加发现一个松弛问题解的可能性。如果这是可行的解决方案，有一个值小于现有的解决方案，它将取代现有和未来的有可能的解决方案，提高修剪效率。切削平面算法在削减节点的数目的应用是有实际问题决定的。一些算法只适用于削减根节点，而有些算法则适用于多个或所有节点的削减。协和式算法 1,2 是一个屡获殊荣的分支切割算法，它设计了对称TSP代码（南科）。此代码已被用来解决许多非常大的TSP实例，包括对应于瑞典等24978个城市问题的实例 2 。这一问题的解决是由切割平面设计算法定制的可能针对这一问题的解空间得到的。2.5.分支定界和分支和切割的设计考虑 当设计一个使用分支定界或分支切割算法的问题时，一些规则必须确定。这些规则包括确定松弛问题应采用哪一种算法来解决，分枝规则，和搜索方法。它决定对该节点的探讨过程。因为一个简单的问题可以转化为相应的子节点的问题，所以算法必须解决的问题空间比原来的问题大大简化。因此，这种方法是可取的，严格的放宽约束条件，可以使得问题得到更好的解决。分支规则确定搜索树的结构。他们决定树的深度和广度。因此分支规则收紧的子问题，可以增加潜在的强规则剪枝的可能性。最后，必须选择一个好的搜索方法。最佳优先搜索选取节点的方法与最好的启发式值的确定算法是已经被讨论过的了。一个最好的搜索策略就是用一个给定的节点到目标节点的路径的成本总和，作为启发值 23 。这一策略保证最少一个给定的节点使用搜索树算法，至少可以得到一个启发式。不幸的是，确定当前节点的最佳值，并要求存储当前所有的活动节点，这个工作需要巨大的存储空间，就今天的存储技术而言，也有可能会用完所有可用的空间。因为这个原因，深度搜索是最常用的。虽然这种策略解决内存问题的效果是接近最优的 49 ，但是它引入了大量的新问题。使用启发式引导搜索可能会在错误的方向引导，产生许多规模庞大而没有用处的子树。不幸的是，即使政策的组合是微调，以获得最佳的结果，许多问题的实例仍然不能相互兼容。这通常是由于不适当的修剪子树造成的。有时，由于需要计算松弛问题或实现切割平面的要求，这也会导致一些困难。例如，单纯形法是常用的为解决IP松弛问题而设计的算法，但是它也存在一个最坏的性能。3.切割和解决的搜索策略3.1.基本算法在不同的切割面进行切割搜索，减少和解决使用削减故意裁剪解决方案原来的解空间。我们用冲孔切是指一切去除至少一个可行的解决方案从原来的（未松懈）问题的解空间。切割和求解算法提出了在图4.1在该算法中，每次迭代对应的搜索路径中的一个节点。首先，选择穿刺切割。让是由被剪掉的解空间的可行解集。然后在sssparse最好的解决方案被发现。这个问题往往是比较容易为稀疏的解空间解决，相对于庞大的解决方案原问题的空间，寻找最佳的解决方案。在根节点，该解决方案被称为现任，或者最好的，解决方案。如果以后的迭代中找到一个比最佳的解决方案，最好是由这个新的替代解决方案。在接下来的步骤中，冲孔切添加到IP。这刺耳的sssparse切排除所有的解决方案该IP。因此，冲孔切收紧IP和降低其解空间的大小。下限为这个然后发现了IP。如果这个下限大于或等于最好的，然后结束搜索和最好的是一个最佳的解决方案。在随后的节点，重复该过程。现任的解决方案是需要更新。穿孔切割积累与每个迭代。当拧紧由于这些刺耳的削减成为足够的紧缩这双改性问题的解决方案将成为大于或等于现任的解决方案的价值。什么时候这种情况发生时，现任的解决方案是返回的优化。定理1。当切割和求解算法终止，现任的解决方案必须是一个最佳的解决方案。证明。现任者在解空间，被刺穿的削减切离最优解。最后的双改性问题的解空间包含所有的解决方案，原来的问题除了。那些被裁掉的穿孔切割。如果这种减少解空间张弛有度的值是更大的大于或等于现任值，然后减少的解空间中不能包含一个比溶液现任。该算法证明下面的定理：定理2、如果原问题的解空间是有限的，并且松弛算法以及该算法的选择和解决稀疏性问题是保证终止，然后切割和求解算法保证终止。证明。在搜索路径中的节点数目必须作为一个非零的数目有限的解决方案，从单点登录在每个节点。因此，有一个有限数量的问题，每一种保证终止。切割和解决可以转换为一个二进制搜索树高度不成比例的儿童，如图5所示。在每个节点，解决了松弛和剪切被选择。这将是用于分支规则。左子的解空间小，它不仅包含由冲孔切裁掉的解决方案。对孩子有巨大的解决方案空间，去除后剩余的左孩子的解决方案。左孩子的解空间的探索是很容易现任的解决方案和生产潜力。这是立即的解决和正确划分为另一个孩子套不相称的孩子。当放松对孩子的解决方案是大于或等于当前现任，它是修剪和搜索完成。因此，搜索树的最终配置是一个单一的路径的一个分支，在每个级别的左右边。这基本上是线性搜索策略：坚持立即解决容易的问题，然后分裂。3.2.使用分割解决作为一个完整的时间算法分割解决算法容易操作，可随时随地使用 6 。随机时间算法可以对于迄今已经发现的任意问题的最佳解和最好的解空间进行终止。许多随机时间算法是基于局部搜索的解决方案。这种类型的随机时间算法不保证最佳的解决方案，因此最终会发现并不能确定当前的解决方案是否是最优的。确定时间算 35,46,47 可以克服这两个限制。如果找到一个最佳的解决方案，这种算法可以提供时间和最优性的保证。分割解决算法发现现任溶液在根节点有一种近似的解决方案可用后的任何时间，根节点是解决。该解决方案提高到最佳是发现或执行结束，使之成为一个完整的时间算法。切割和解决提供了一个良好的效益作为一个随时解算器。许多近似算法无法提供一个解决方案的质量约束。这可能是特别有问题时，结果是用于进一步的分析和估计误差需要被传播。终止切割和解决，价值最近解决双改性问题是一个下界的最优解，得到所期望的信息。此外，对现任和双改性问题之间的间隙减少率解决方案可以监测和用于确定何时终止时间解算器。3.3.并行处理 切割和解决可以使用并行处理计算机。每个稀疏可以独立解决问题在不同的处理器。这是没有必要的，每一个稀疏问题完成运行。每当一个稀疏问题解决了，这是确定的迭代有最小的下界大于或等于溶液的稀疏问题。这是必要的，稀疏的问题之前，迭代运行完成的保证最优性。 考虑如图5所示的搜索。对双结非降低解我增加。假设首先，A4完成解x。进一步假设B1具有一个小于X和B2的解决方案有一个解决方案，等于x。（在这种情况下，B2的解决方案不能大于X是一个低的溶液中的结合空间中找到的解决方案在A1和A2）A4。只需要运行完成，在A3搜索可以它不包含一个比X溶液终止。更一般地，让Y等于成本的解决方案在一个节点发现AP。让BQ和成本最小的节点这也是大于或等于y。所有的搜索节点的AI在我 Q可以终止。4.一个简单的例子 在本节中，我们提出一个简单的例子，问题和步骤通过减少搜索过程和解决。考虑下面的IP：这个IP只有两个决策变量，可以表示为二维图如图6所示。每一个X，Y对是可行的，都必须遵守的约束。每个第一五线性约束（11）至（15）对应于一个边的图6中的多边形。所有可行的解决方案必须在或多边形的边。约束（16）和（17）要求决策变量取整数值。因此，这个IP可行的解决方案由点位于内、在多边形的边。目标函数的条款（10）可以重新排列成斜截式为：y = 45XZ.因此，这个IP目标函数代表以45的坡度平行线无限。在这例如，Z值等于其相应的截距。（一般2D IPS，Y等于恒次Z.）图6（b）显示了这一家人的线。在这一点上可行的解决方案有一个x值零和一个Y值3，得到的Z值3。显然，这不是最佳解决方案。考虑到所有的线一个坡度为45，很明显，用最小的截距值也与可行解的线将确定最佳的Z值。这条线可以通过检查，并显示在图6（d）。最优解为x = 2和y = 1，Z = 0.6屈服。这个IP，原问题的解空间，单点登录，包含九个点上多边形。以上九点是可行的解决方案，满足所有的约束。适用于切割和解决，必须选择一个松弛。在这个例子中，我们放松的约束（16）和（17）。这个解空间轻松的问题，SSR，包含每一个点的x和y内和实际值在多边形无限数量的解决方案。 图7显示了在解决这个IP使用切割步骤和解决。首先，轻松的找到解决方案。的这个松弛的解决方案如图7所示（一）。x的值为3.5，Y为1.4，与这种轻松的解决方案的价值子等于1.4。这是一个下界的最佳解决方案的价值。 接下来，冲孔切选择如图7（b）。阴影区域包含的松弛问题的解决方案以及对原问题的可行解。它也包含无限数量的可行的解决方案轻松的问题。这个稀疏问题的解决寻找整体最佳的解决方案。只有一个整数解在这稀疏的问题，所以它是最好的。因此，现任的解决方案设置为x = 3，y2，和目标函数价值是0.4。最好是将0.4。 削减了阴影区域从图7中的多边形线（B）可以由一个线性约束的代表：Y17314 。这个约束添加到IP。现在降低了IP可行域及其当前的解决方案空间包含八点，如图7（c）。当前的IP弛豫如图7（d）。价值这是轻松的解决方案1.1。请注意，这个下限是小于最佳，所以继续搜索二迭代。 在搜索的第二节点，我们选择了一个冲切如图7所示（E）。稀疏表示的问题图7中的阴影区域（E）是解决产生了价值0.6。这个值是小于的现任的，所以该解决方案成为新任总统，最好设置为0.6。相应的电流冲切线性约束添加到IP，从而减少可行图7所示的解决方案空间（F）。轻松的问题是解决目前IP如图7所示（G）。新的下限是0.2。此值是大于0.6的最好，所以搜索完成。现任者必须是一个最佳的解决方案。现任溶液在联盟最好的解决方案所有已解决的稀疏问题空间。0.2是一个下界的最佳解决方案在剩余的解空间。因为它比现任总统，就不能在这个空间，是一个解决方案比现任。因此，为保证最优性。本节给出的例子的问题是容易解决的检验。然而，问题可能感兴趣的包含成千上万的决策变量，获得了由一个凸多面体的定义的解空间相应的高维空间。例如，100个城市有9900个决策变量的ATSP。刺骨的削减选择本节中的示例问题进行定制的这种特殊情况。在下一节，获得一个通用的程序提出了刺耳的削减。5.一个通用的切割和解决程序 切割和解决算法需要三个选择。一个放松的必须选择，推导出一个穿孔的方法削减必须设计，并解决了稀疏问题的技术必须选择。为了达到最好的效果，这些选择必须以特定的被解决的问题认真评估确定。许多感兴趣的问题，解决稀疏的情况下放松技术和算法可能已经研究。然而，冲孔切导数没有以前的探索。在本节中，我们总结了得到他们刺穿削减和提出了一个通用的程序良好的特性。然后，我们提出了一个通用的切割和解决所有三个选择指定的算法。这个程序可以用于任何IP。而更定制的方法产生更好的结果，这种通用的方法，用于实现ATSP效果很好。每个IP可以转换为一个二进制的IP（BIP） 27 ，其中决策变量被限制在0和1的值。对于一个给定的BIP，决策变量可以被划分成两组：一个小的和一个大型稀疏集L.问题的解决在小这基本上是相同的L设置所有的变量的值零。在稀疏的问题解决了，设置所有的变量在L为零的约束被删除。然后穿孔切割后添加到BIP：使用此切分区解空间。无论是总和的变量L等于零或大于或等于一。对应于第一案的解决方案正是稀疏的问题的解决方案。所有的在解空间中其他的解决方案是包含在冲孔切除原来的问题（18）。剩下的问题是如何分区的变量集S和L，产生有效的穿孔切割。的这个问题的答案被认为是依赖的问题。我们提供一些指引，在这里。以下是刺耳的削减的理想的特性：（1）每个冲孔切应删除当前宽松的问题的解决方案，以防止这种解决方案在随后的迭代发现。（2）空间的冲孔切割拆除应充分稀疏，所以可以最优解发现相对容易。（3）刺耳的削减应该尝试捕捉了原问题的最优解。该算法将不终止到最佳的解决方案已被砍掉，从而使现任。（4）为了保证终止，每个冲孔切割应包含原来的至少一个可行的解决方案，未松懈，问题。敏感性分析是广泛的研究和应用研究 44 。我们从域借工具设计分区决策变量为集合S和L如下一个完全通用的方法。首先完整性约束的放松和BIP是一个LP解决。LP的解决方案定义了一组值的简称降低成本。每个决策变量西有降低成本的价值，这是一个较低的LP的增加束缚解决方案的成本如果变量的值增加一个单位。每个决策变量不为零的值在LP溶液具有降低成本为零。如果另一个决策变量，西，具有降低的成本为零，它可能是可能增加西价值不增加的LP的解决方案的成本。另一方面，如果西有一个大的降低成本，那么一个同样大，或者更大的LP的解决方案的成本增加，如果有一个单位增加发生西安的价值。我们使用这个概念，我们的通用算法。集可以由所有决策变量的减少成本小于参数，在 0。应设置足够小，产生的稀疏问题比容易解决的令人满意的特性（2）。另一方面，它应设置尽可能大的可能性增加这集的包含所有关于原问题的最优解的必要的决策变量。财产（1）和LP的解决方案满足必须包括在稀疏的解空间，因为决策变量在LP溶液非零的值的零成本的降低。直观地说，小的降低成本的决策变量似乎更可能出现在一个最佳的解决方案。因此，财产（3）是以降低成本为指导解决用于设置和通过实际大的变量选择。如果保证终止是必需的，（4）可以满足设定到足够大的值或添加变量，将保证至少有一对原问题的可行解。在确定一个划分决策变量的方法，我们提出了一个完全通用的减少和解决的程序，可用于任何BIP（并因此任何IP），如在图8概述。松弛的使用。完整性约束的省略。稀疏的问题可以解决使用任何BIP或IP求解器。刺耳的将被添加到BIP是。注意，这个通用的方法的性能是通过定制它手头的问题的改进。更严格的下限，更有效的穿孔的削减，和/或使用的求解器，是为了解决稀疏的情况下感兴趣的问题可能会产生性能的急剧增加。然而，在接下来的两部分，我们展示了如何这种通用的方法，简单的实现可以产生令人印象深刻的结果。6.切割旅行推销员的威风 我们已实施的削减和解决解决ATSP现实世界的情况下，算法。ATSP可以用来模拟一个主机的规划，路由，和另外一些不同的应用调度问题在1节中提到。许多这些现实世界的应用程序是使用传统的方法很难解决的问题因此这是很好的候选人可供选择的搜索策略。七个真实世界的问题类的ATSP已在 8 研究。这七个问题的实例生成器类可在戴维约翰逊的网页：HTTP：/ / / DSJ / chtsp / atsp.html。一个简短的七个问题的描述如下。第一类是近似最短公共超（超）。这个问题涉及到基因组重建，在一个给定的字符串组合成尽可能短的超弦。第二类是倾斜钻孔机，一个添加剂范数（rtilt）。这类对应对调度孔钻成一倾斜表面的问题。第三类（高跷）对应于同样的问题，但不同的规范。第四类是随机欧氏堆垛起重机（吊车），属于规划操作起重机时的一些项目不同的位置。第二类是磁盘驱动器（磁盘）。这个类别代表计算机的磁盘调度问题的读取头，因为它读取一个文件数。第六类是付费电话收集（硬币），相应的付费电话收集硬币问题。手机是位于一个双向的街道网格，以网格组成的单向街周边。最后，无等待流水车间（车间）级代表每个需要使用多种设备工作调度。在这个问题上，不能有任何延迟的机器之间的工作。在遗传算法中，下限是放松的完整性发现。的ATSP，这是举行卡普下结合的。然后弧与降低成本小于选择集和由这些弧稀疏解决了。在稀疏图最佳旅游成为我们的第一个现任的解决方案。原来的问题然后收紧通过增加的弧的决策变量的总和小于或等于1 N约束，在那里n等于城市数量。有相同的效果在泛型算法穿孔切割有在ATSP最优解氮弧。如果所有的最优解所需的弧在选定的一组弧提出，该解决方案将使现任。否则，至少一个弧形，不在这一集是最佳的旅游需要。这个约束被穿刺切割代表。解决举行卡普下界的过程，解决一个稀疏问题，并添加一个穿孔切割的问题不断重复直到举行卡普价值的深切的问题大于或等于现任的解决方案。在这一点上，必须是一个最佳的旅游。解决卡普举行的最坏情况下的下限的复杂性（用单纯形法）和解决稀疏的问题都是指数。然而，在实践中这些问题通常是比较容易解决的。此外，第一次迭代后，现任的解决方案可以作为一个上限的稀疏问题求解，有可能改善其性能。为一个适当的值的选择可能依赖于成本的降低值分布。在我国目前实施，我们简单地选择一个弧数，mcut，是在初始切割。在根节点，弧排序通过降低成本和mcut选择最低的弧。等于最大限度的降低成本这一套在随后的节点，是用来确定所选的弧。为mcut值的选择取决问题类和城市的数量。我们认为，确定直接从分布，降低成这将提高实施作为先验的问题类的知识就没有必要和是定制适合在一类问题的情况下的变化。如果切不包含一个可行的解决方案，它可以扩大，这样做。然而，在我们的实验检查有没有明显的好处。使用很少的迭代求解问题，从而保证终止没有实际意义。我们使用了一个LP求解器CPLEX IP， 29 ，解决松弛和稀疏的问题。全部参数该求解器被设置为默认模式，没有“热启动”的使用。对于一些较大的情况下，这通用的求解成为深陷在解决稀疏性问题。的性能可替代的改进的一种算法，专为解决稀疏atsps。我们无法找到这样的代码，我们可用正在调查此任务的三个可能的实现：（1）采用哈密顿回路的一个枚举算法利用ATSP性质，（2）通过加入有效的改善，如提高CPLEX实现的帕德博格和雷那蒂收缩程序，外部定价，切割定制的稀疏atsps飞机，启发式算法为节点的选择，并试探法确定先进的基地，或（3）实施的一种混合算法结合线性规划约束规划。然而，尽管我们实施的残酷，这足以证明切割的潜在的解决方法。我们比较我们的算法与分支定界与分公司在下一节将实现。7.的ATSP计算结果在本节中，我们比较减少和解决与分支定界和分支切割法。我们使用的七现实世界中的问题发电机 8 ，在6节讨论进行大规模实验。每个问题的类型和大小，我们跑了500个试验，显示了巨大的洞察到每个解算器的预期行为的每个问题类。我们开始与n = 25和25递增的城市一次直到求解器无法解决在十分钟或更少的平均时间实例；从而允许最多5000分钟的试验。随着超级问题发生器的例外，发电机使用一个参数，对影响有效数字用于电弧成本数。我们将此参数设置为100000。鹤类使用一个二参数是大量的城市增加 8 。我们将此参数设置为10 for n _ 100, 13 forn = 125, and 15 for n = 150。我们比较了切割和解决（CZ）的分支定界算法的dellamico卡帕倪托，介绍，和托特（CDT） 7 ，这是在第2节讨论了。我们还可以比较两个分支切割法：协和1,2和CPLEX 29 。协和式飞机是在2节介绍。它用于解决对称TSP（stsps）。ATSP实例可以转化为南科实例使用一个两级变换 32 。戴维约翰逊已经公开可用的代码这两级变换在HTTP：/ / / DSJ / chtsp / atsp.html。采用两级变换时，的弧的数目增加到4N22N。然而，这也不是没有零弧数（本质上）无穷成本N2N，在原来的问题。协和式飞机允许调整其“块”的大小。此参数控制在何种程度上项目提利用削减 3 。项目和升力削减是动态生成适合解决特定的实例。如果块的大小被设置为零，没有项目和扬程切割产生的和协和的行为作为一个纯粹的南科求解器。这是显示在 17 ，16产生最好的结果为现实世界的ATSP实例的默认尺寸。我们用这个在我们的试验中的默认值。唯一的公开可用的分支，专门解决TSP问题，我们可以找到削减代码是协和式飞机。然而，问题是一个强大的分支和切割的IPS求解一般，所以我们也包括它的比较。该解算器动态地确定为每个实例检索策略和削减。例如，选择分支变量的搜索方向是根据给定的实例。此外，CPLEX使用九个不同的类别切割面（戈莫里削减包括一个类）和自动确定每个组的频率削减使用。最后，CPLEX使用各种启发式找到可行的解决方案，整数遍历搜索树。一般来说，CZ是我们CPLEX实现通用。两种算法识别subtours加适当的子回路消除约束。除此之外，这两种算法的通用IP求解器。我们的代码是运行使用CPLEX 8.1版。我们使用速龙1.9兆赫双处理器，2GB的共享我们测试的内存（虽然我们没有使用并行处理）。为了确定在松弛问题subtours，我们使用了马修Levine实施的和永持和茨城最小割代码 37 ，这是可用的在 38 。我们的代码可以在 10 。在这里介绍的实验中，我们发现，搜索路径很短。通常只有一个或两个稀疏两个或三个放松的问题，问题就解决了。这一结果表明小降低弧集成本可能包含最优解。平均归一化的计算时间和对现实世界的问题类别95%的置信区间图所示。9通过15。一个可能在“典型”的时间，对于每一个这些求解器所需的兴趣，因此，中位时间为所有的试验在图中给出。16通过22。表1列出了最大的问题实例的大小这是解决由每个算法在执行时间限制。协和式飞机比其他所有的求解器的超类，如图。9和16。它能够与N = 625解决的情况下，CZ解决的600个城市，275个城市和CDT CPLEX解决，解决250个城市。协和式飞机也优于其他解决问题的rtilt类如图。10和17。它解决了125个城市的实例，CZ解决了100个城市，75个城市和CDT CPLEX解决，解决25个城市。我们解决了一些超级和rtilt实例的所有解决方案和发现他们都有很多的优化解决方案。对于其他五个问题类，CZ优于其他求解器。用于起重机的阶级，CZ，协和式飞机，和CPLEX能够解决了125城市如图。12和19。CZ是这个城市的数量最快，其次是协和式飞机。对于其他四个问题类，CZ能够解决比任何其他解决较大的情况下。对于高跷，CZ解决100个城市在规定的时间内，而协和与CPLEX解决城市如图75。1118。磁盘，CZ解决775个城市，而CPLEX跟着远远落后325个城市如图。1320。CZ解决100城市硬币实例和CPLEX解决城市如图75。14和21。最后，cz可以针对550市店的情况下，用CDT以下350个城市如图。15和22。CDT进行适度的超级商店。然而，它是唯一能够解决50座起重机25个城市的其他四个问题类。我们让计算跑过去的时间限制，发现很多这些试验所需的大量时间。最坏的情况是50市盘类，这是我们最后在25900分钟内杀死。总之，对于问题的情况下，我们测试，CDT是不是很强大。CPLEX是强大的，但温和的性能一般。协和式飞机是两个问题类，有大量的最佳最快的解决方案。CZ是强大的和最好的性能为其他五类。8.讨论和相关的工作 许多有趣的优化问题是很难解决的，它们的最优解很难求出来，因此需要采用它们的近似最优解。舍弃掉在一些条件下需要昂贵的代价求得的最优解。近似的问题对于研究问题的进展有很大的影响，如在生物学中的应用。对于近似最优解，在仔细考虑后会发现它有很多用处，如解决一个航天器的路由问题，或在制造应用时解决服用的问题。此外，当任何应用程序中使用同一个近似解时，它也会产生不好的影响。为解决这个问题，分块解决提供了一种方法，减少分支定界与分支切割时产生的问题，以找到最优解。 在我们的实验中，我们观察到的切削性能和减少大量的问题解决最佳的解决方案。我们监测这些试验发现减少和解决发现的最优解在搜索的早期，但需要大量的计算时间证明的最优性。我们怀疑许多优化在双改性问题的解决方案，使松弛等于最优的困难解的值。这可能是大部分的最优的解决方案必须砍掉之前的计算可以完成。一个关注削减的可行性和解决可能是选择一个贫穷的减少可能是类似的选择在深度优先搜索树的路径错误。这两种行为是非常不同的。当选择了错误的孩子在深度优先搜索，决策是永久性的所有子树的后代的。例如，如果一个变量出现在每一个最佳的解决方案（骨干变量 40,48 ），然后将它的值设置为零是灾难性的。相反，迫使一个变量，并没有出现在任何可行的解决方案，包含（脂肪变 9 ）在一个类似的可怕的结果现状。在每个节点的子树是注定的。另一方面，当一个可怜的切割是切割和解决的选择唯一的结果是，在探索单节点是相对无效的时间。这不完全是浪费哪怕是一个拙劣的削减有助于收紧的问题在某种程度上，一经提出，这将不能重复在未来的迭代。此外，随后的节点不是“锁定”为电流切断的选择。搜索树的方法，如分支定界和分支和切割的必须记忆问题或之间选择无果搜索子树不包含最优解的风险。切割和解决这些困难是免费的。它的内存的要求是微不足道的只有现任的解决方案和电流双改性问题需要保存的搜索路径遍历。此外，在迭代搜索，有没有子树迷路。许多技术已经在努力克服这个问题，设计了深度优先搜索。其中迭代深化 34 ，有限的差异 24 ，和随机并重新启动 19 。另一个有趣的对比是，分支定界和分支切割必须计算至少一个放松的解决方案，不仅是可行的为原来的问题，但是它还必须为原来的问题是最优的。在相反，减少和解决不需要找到一个轻松的解决方案，为原来的最优或甚至是可行的问题。考虑，例如，通用削减和解决。每个图5右边的孩子可能会推测解决方案。然而，搜索是尽快的松弛值大于或等于终止现任的价值。我们现在讨论的几种算法，类似的减少和解决。切割和解决类似戈莫里的算法在削减用于约束的问题和一个线性路径搜索。戈莫里的算法有时称为“在根节点解决问题”，因为这基本上是其行为相比它的分支andcut。然而，切割面施加和放松的问题都解决了一个迭代的方式直到搜索终止，提示搜索迭代的进展。切割和解决可以被认为是一个扩展的戈莫里的方法。像戈莫里的技术应用，切割，一次一个，直到找到最佳的解决方案。这两种方法之间的主要区别是，戈莫里的削减不刺耳的削减他们不砍掉任何可行的解决原来的问题。穿孔切割深度超过戈莫里削减他们不需要装饰的可行的解决方案，为未松懈的问题。切割较深的有两个好处。首先，它提供了一套从该解决方案的最佳选择一个潜在的责任。第二，这些刺耳的削减收紧宽松在一种积极的方式问题，因此往往会增加双改性问题的解决方案更迅速。切割和解决也是类似的算法解决的定向问题（OP）在 18 。在这项工作的条件下，降低原问题的可行解。这些削减是配合使用传统的削减，是用来加强问题。当一个有条件的切割技术，所有的枚举可行的解决方案，在切割的尝试。如果枚举是不是短时间内限制了，伤口被称为分支覆盖切割和与它相关的稀疏图的存储。该算法试图解决OP在一个迭代的方式，但是，分支发生后每五支盖的削减已经应用。在这之后分支和切割树的问题，第二个分支切割树是解决超过所有存储的图的联盟分支覆盖伤口。切割和解决不同于这种运算算法的几种方法。第一，现任的解决方案被发现在降息早解决了搜索。这些公司提供有用的上界以及提高随时性能。第二，该方法 18 存储稀疏问题和它们的解决将作为一个单一的，更大的问题在最初的分支切割树进行了探讨。最后，这不是真正的迭代运算算法分支是允许的。在更广泛的意义上，减少和解决类似于分而治之的 41 在这两个方法识别小原问题的子问题和解决他们。而且分而治之解决所有这些问题，切口解决了一个非常小的比例的人。在比较这两种技术，减少和解决可能思想是分而治之的强大的修剪规则。我们和一般性的一个注穿孔切割结束这一节。刺耳的削减是用于在一个迭代时尚的切割和解决，但也可应用于其他搜索策略，如分支和切割。只要由切定义稀疏的问题解决了，刺骨的削减可能会被添加到一个IP。例如，Fischetti和托特的分支切割算法 17 解决了许多在该搜索树的每个节点的稀疏问题提高上限。穿孔切割对应这些稀疏的问题可以被添加到IP没有损失的最优性。这些刺耳的减少可能会收紧的问题，更大程度上比收紧由于传统削减和可以减少所需的时间解决实例。9.结论在本文中，我们提出了一个搜索策略，我们称之为分割解决。虽然没有分支上的应用，但是我们发现的这个算法可以提供最优性和终止保证。这是一个迭代的策略，该技术避免了一些困扰搜索树的方法，如分支定界和分支切割的陷阱。对于本算法内存的要求是可以忽略不计，因为只有现在已有的解决方案和目前的问题需要通过搜索路径的遍历提出解决的方法。此外，没有必要使用技术来降低搜索到无效子树的风险，增加问题解决的可行性。我们证明了分块解决的整数规划和实施这一策略的ATSP问题的解决方案。在一般情况下，我们的使