达达的博客

原创 获取CPLEX求解MIP时添加的cutting planes (C program)

【代码】获取CPLEX求解MIP时添加的cutting planes (C program)

翻译 Removing Propagation Redundant Constraints in Redundant Modeling 翻译（二）& 全文总结

6. EXPERIMENTS我们可以利用传播冗余的推理来消除传播冗余。然后我们得到一个传播强度完全相同但传播器更少的模型。这可以转化为更快的传播。我们对第4节中问题去除传播冗余约束的改进进行了实证验证，除n-Queens问题外，由于n-Queens问题存在较好的单一模型，使用全局alldifferent约束，使得冗余建模不值得。在以下实验中，所有基准测试都是在运行Solaris 8的S...

翻译 Removing Propagation Redundant Constraints in Redundant Modeling 翻译（一）

消除冗余建模中的传播冗余约束abstract一种广泛采用的解决约束满足问题的方法是将系统树搜索和不同程度的约束传播相结合，对搜索空间进行剪枝。提高执行效率的一种常见技术是添加冗余约束，这些约束是问题模型中其他约束逻辑上隐含的约束。然而，一些冗余约束是传播冗余，因此不会向约束求解器提供额外的传播信息。冗余约束是在冗余建模过程中自然产生的，在冗余建模过程中，同一问题的两个模型通过通道约束进行连...

翻译 handbook of CP 10.6/7/8/9 翻译

10.6 Combinations of Symmetry Breaking Methods我们已经描述了各种对称破缺方法，每种方法都有优点和缺点。 将两种或更多种方法结合起来以获得所有优点显然是个好主意。 不幸的是，正确组合对称破坏方法已被证明是非常困难的。 对称破坏方法试图从每个等价类中保留一个解决方案。 如何选择这种解决方案取决于对称性破坏的方法。 任意组合任意两种方法可能意味着每种对称...

翻译 10.10 Conclusions 翻译

我们已经介绍了约束规划中的对称性。 我们在强调与群体理论的联系方面毫不羞愧。 对称性的研究是群论，所以任何曾经考虑过约束对称性的人都在考虑群论 - 尽管可能没有意识到。 我们还强调了计算群理论为约束中对称性的有效利用提供方法的能力。 约束编程的研究人员和用户可以通过链接到现有的计算代数包或通过实现他们自己的算法来访问这些技术。 再一次，任何编写过在约束条件下利用对称性的代码的人，无论是否无意识地进...

翻译 handbook of CP 10.5 Dynamic Symmetry Breaking Methods 翻译

动态对称破坏方法是在搜索过程中破坏对称性的方法。 SBDD和SBDS是本节中描述的两种方法。 在这两种方法中，对称性作用于变量/值对。 通过启发式破坏对称性包含在此类别中，因为尽管这些变量和值排序启发式算法在搜索开始之前已完全定义，但它们在搜索期间使用。 这些方法将在后续章节中概述。Figure 10.9:一个示例显示，即使所有行和列都是lex排序，右下子矩阵中的完整矩阵对称也可以保留。...

翻译 handbook of CP 10.4 Adding Constraints Before Search 翻译

毫无疑问，历史上最常用的对称性破坏方法涉及向基本模型添加约束。 在这种情况下，术语“对称性破坏”是完全合适的。 我们从一个具有大量对称性的问题转向一个新的问题，对称性大大降低 - 理想情况下根本没有。 我们为实现这一目标而添加的约束称为“对称破坏约束”。约束程序员在识别约束问题中的对称性时，总是以一种特殊的方式添加打破对称性的约束。通常很容易想到破坏对称性的所有或大部分的约束条件。例如，假设一...

翻译 handbook of CP 10.3 Reformulation 翻译

建模对问题的解决效率有很大的影响。适当地重新拟订一个模型可以把实际中不可行的问题变成可行的问题。建模和重新制定同样重要的对称性打破。同一问题的不同模型可以有不同的对称性;一种公式可能具有比另一种更容易处理的对称性。在极端情况下，一个公式可能根本不对称。在其他情况下，从一个模型到另一个模型的对称性可以大大降低。此外，一旦一个问题被重新表述，剩下的对称性仍然可以在搜索之前或搜索过程中处理，而其他打破对...

翻译 handbook of CP 10.2 Definitions 翻译

为了处理约束满足问题（CSP）中的对称性，似乎不言而喻，从业者必须首先理解对称性的含义。 这似乎并非如此：关于该主题的许多论文都没有提供对称性的精确定义。 提供定义的论文通常会给出彼此根本不同的论文，同时仍然在给定问题中识别相同的对称性并正确处理它们。有两种广泛的定义类型：将对称性定义为解集的属性，以及将对称性定义为可以在问题陈述中识别的属性，而不解决它。 这些将被称为解对称性和问题对称性。 在本...

翻译 Chapter 10 Symmetry in Constraint Programming & 10.1 Symmetries and Group Theory

约束中的对称性一直很重要，但近年来已成为一个主要的研究领域。 约束编程中的一个关键问题早已被认识到：搜索可以一遍又一遍地重新审视等效状态。 原则上，已经通过许多不同的技术解决了该问题。 在我们写作时，由于两个原因，研究仍然非常活跃。 首先，在对称排除已知的技术的实际应用中存在许多困难，并且克服这些仍然是重要的研究问题。 其次，到目前为止，该领域取得的成功鼓励研究人员找到利用对称性的新方法。在本章中...

翻译 An Increasing-Nogoods Global Constraint for Symmetry Breaking During Search 翻译（二）

因此，我们从开始检查剩余nogoods的LHS。 为了将剩余的increasing nogoods 的简化版本转换为简化形式，使用两个指针和来索引具有以下条件的3个列表。指针用于根据条件（ii）找到由生成的最短nogood。 如果生成了新的nogood，则使用来检查是否存在可以根据定理7生成的额外nogood并找到最后生成的nogood。如果可以生成额外的nogoods，则设置为。 最初，被设...

翻译 An Increasing-Nogoods Global Constraint for Symmetry Breaking During Search 翻译（一）

abstract搜索过程中的对称破缺(SBDS)在回溯时动态地增加了条件对称破缺约束conditional symmetry breaking constraints(这不是好事)，以避免在对称等价的已访问搜索空间中进行探索。约束存储中存在大量这样的独立nogoods，这些独立nogoods在约束传播中很弱。我们引入了增加nogoods（increasing nogoods）的概念，给出了增加...

翻译 Semantic Learning for Lazy Clause Generation——lazy clause generator相关论文

 懒惰子句生成的语义学习本文核心：针对lazy clause generation中的冲突分析进行改进，用与SAT组件等效的语义推理方法代替它，从而从而减少SAT对高效单元传播的作用。 这使我们可以减少生成的文字数量，并加强冲突分析。试图避免为literals生成SAT表示，为此，放弃使用literals来构造蕴涵图（implication graph），并定义了一种将变量连接到分...

翻译 Lazy clause generation reengineered——lazy clause generator相关论文

Lazy clause generation reengineered本文创新点：原始的lazy clause generator是在SAT求解器中嵌入FD传播引擎，这里是在FD中嵌入SAT求解器作为传播器原始优点：FD传播器被视为子句生成器，它为SAT求解器提供越来越多的问题描述。 混合的优点是：它保留了FD系统问题的简明建模，但它获得了SAT记录nogoods和backjump的能力，...

原创 Local Search Methods 框架

翻译 5.7 Frameworks and Toolkits for Local Search 局部搜索的框架和工具包 & 5.8 Conclusions and Outlook

5.7 Frameworks and Toolkits for Local Search 局部搜索的框架和工具包软件框架和编程工具包极大地促进了求解约束满足和优化问题的局部搜索算法的开发及其实际应用。在处理概念上复杂的约束编程问题时尤其如此。这样的系统可以极大地减轻与实现SLS算法的有效实现相关的负担。它们还促进了软件的重用，并支持分离问题公式(建模)和解决方案。在下面的部分中，我们将简要概述...

翻译 5.6 Local Search for Constraint Optimisation Problems 约束优化问题的局部搜索

现实生活中的许多问题都受到了过度的约束。例如，在生产计划应用程序中，可能没有足够的资源在其各自的截止日期内完成所有给定的作业。在这种情况下，最好能找到一种可行的资源分配办法，使产生的收入总额达到最大;这类优化问题称为最大效用问题（ maximal utility problem ）[104]。在其他情况下，可能会违反某些约束，但这样做会带来惩罚成本。目标是找到一个惩罚最小的解决方案;这就是所谓的最...

翻译 5.5 Other Approaches 局部搜索的其他方法

除了前面部分中介绍的算法之外，还在解决CSP的上下文中应用了许多其他本地搜索方法。 在本章的内容中，不可能对CSP的大量且不断增加的局部搜索算法和密切相关的问题进行全面的调查，例如图着色问题和SAT。 因此，选择下面提到的算法来说明一些主要方法。有大量关于约束满足问题的进化算法的研究。最早的作品包括Tsang和Warwick[108]、Paredis[82]、Hao和Dorne[39]、War...

翻译 5.4 Penalty-Based Local Search Algorithms基于惩罚的局部搜索算法

另一种扩展迭代改进策略的方法是，当搜索过程即将停滞在一个局部极小值时，修改该评估函数[71]。这种方法也称为动态本地搜索(Dynamic Local Search, DLS)[52]。基于惩罚的算法通过惩罚权重来修改评估函数，惩罚权重与解决方案组件或候选解决方案的其他特征相关联；在CSP的情况下，惩罚权重通常与给定CSP实例和SAT的约束关系相关联，类似地，与给定CNF公式的子句相关（在后一种...

翻译 5.3 Tabu Search and Related Algorithms Tabu搜索和相关算法

禁忌搜索（TS）[35,36]背后的关键思想是使用内存来防止搜索过程停滞在局部最小值，或者更一般地说，是给定搜索空间中有吸引力的非解决区域。 在简单禁忌搜索中，迭代改进策略通过短期记忆得到增强，允许它从局部最小值中逃脱。 该存储器用于防止搜索返回最近访问的搜索位置以进行固定数量的搜索步骤。 简单的TS可以通过明确记住先前访问过的候选解决方案并排除任何可能导致这些解决方案的步骤来实现。更常见的情况是...

翻译 5.2 Randomised Iterative Improvement Algorithms 随机迭代改进算法

迭代改进算法的主要限制源于它们陷入给定评估函数的局部最小值的事实。 处理此问题的一种简单方法是偶尔允许不改进的搜索步骤，即，从当前邻域中选择邻居s'∈N（s），其中g（s'）≥g（s）。实现这种方法的机制有很多;其中许多使用了随机决策，以平衡不断恶化的搜索步骤的多样化效果和迭代改进提供的搜索强化效果。随机迭代改进（RII）是迭代改进的扩展，其中在每个步骤中具有固定概率wp，从当前邻域N（s）随...

翻译 Chapter 5 Local Search Methods

局部搜索是解决复杂计算组合问题(包括约束满足问题(CSP))的基本范式之一。它为解决在许多实际应用程序中遇到的大型和困难的问题实例提供了一些最成功和最通用的方法。尽管在系统、完整的搜索算法方面取得了令人印象深刻的进展，但在许多情况下，局部搜索方法是解决这些大型复杂实例的唯一可行方法。本地搜索算法自然也适合于处理在许多实际应用中出现的优化标准。局部搜索的基本思想是从一个给定问题实例的随机或启发式...

翻译 论文Improving Combinatorial Optimization: Extended Abstract

整体来看，这篇论文是对作者在CP中不同方面做出贡献的总结，比较短，发表在AAAI上。Abstract组合优化是计算机科学的一个重要领域，具有许多理论和实际应用。 在论文[Chu，2011]中，我们对组合优化的几个不同领域做出了重要贡献，包括nogood学习，对称性破缺，支配，松弛和并行化 （nogood learning, symmetry breaking, dominance, rel...

翻译 论文Propagation via Lazy Clause Generation(3)

9 Experiments我们使用MiniSat [25]版本2.0 beta作为起点构建了一个原型延迟子句生成器系统。 我们现在使用延迟子句生成给出了许多不同实验的结果。 我们还比较了一些问题上延迟子句生成的各种建模选择。 我们使用3个字母代码来定义建模选择：第一个字母表示（e）ager或（l）azy建模; 第二个字母表示（f）ull整数表示，（n）非连续表示，（b）边界表示和（n）非连续边...

翻译 论文Propagation via Lazy Clause Generation(2)

7.3 Propagator and variable representation independence 在通常的有限域求解器中，我们受到限制，所以如果我们使用边界变量，它们必须被限制只出现在边界传播器中。实际上，我们可以使用这个观察来避免对只出现在边界传播器中的变量使用全整数变量。在延迟子句生成解决程序中，我们可以将布尔变量表示从传播器类型中分离出来。这是因为传播器作用于表示变量的域，...

翻译 论文Propagation via Lazy Clause Generation(1)

通过延迟子句生成进行传播abstract有限域传播求解器通过一组可自然建模为布尔变量的选项有效地表示变量的可能值。在本文中，我们描述了如何模拟有限域传播引擎，将传播器映射到SAT求解器中的子句中。这立即导致有限域传播的强nogood。但是，除非在有限的情况下，简单的静态转换是不切实际的。我们将展示如何为SAT解决程序将传播器转换为lazy clause generators。由此产生的系统...

原创 Backtracking search algorithms框架

翻译 4.10 Comparing Backtracking Algorithms

正如这项调查所表明的，回溯的许多改进已经被提出，而且有很多方法可以将这些技术结合到一个算法中。在本节中，我对回溯算法的性能进行了比较研究。本研究分为实证研究和理论研究两大类。这两种方法都有众所周知的优点和缺点。经验比较允许使用任何一对回溯算法，但是关于哪种算法更好的任何结论总是很弱，因为它必须由短语“on the instances we examined”来限定。理论比较允许对一些回溯算法的相对...

翻译 4.9 Optimization

在一些重要的约束规划应用领域，如调度、排序、规划等，出现了csp, csp除了必须满足的约束外，还有一个必须优化的目标函数f。在不丧失通用性的前提下，我假定下面的目标是找到一个最小化f的解，并且f是CSP所有变量的函数。我还假设在CSP模型中添加了一个变量c，并且约束为等于目标函数;即c = f(X)，其中X是CSP中的变量集。我称之为目标约束 objective constraint。优化求...

翻译 4.8 Best-First Search最佳优先搜索

在由回溯算法遍历的搜索树中，假设节点的分支按照值排序启发式排序，最左边的分支最有希望(或者至少不比右边的任何分支更没有希望)。然后回溯算法对搜索树进行深度优先遍历，按从左到右的顺序访问节点的分支。当CSP实例不能满足要求，必须遍历整个搜索树时，深度优先搜索显然是最佳选择。然而，当已知或可以安全地假设CSP实例是可满足的时，其他搜索策略(如最佳优先搜索)就变得可行。在本节中，我将调查基于差异的搜索策...

翻译 4.7 Randomization and Restart Strategies

回溯算法在某些情况下是脆弱的，这一点已被广泛观察到。对一个变量或值排序启发式的看似很小的更改，例如打破连接方案的排序的更改，可能会导致运行时间上的巨大差异。对于这种现象的一种解释是，排序启发式会出错。根据错误的数量以及错误在搜索过程中出现的时间(因此需要付出多大的代价才能纠正错误)，不同的启发式之间的性能差异很大。为了利用这种可变性，提出了一种称为随机化和重新启动的技术。回溯搜索算法中的随机化...

翻译 4.6 Heuristics for Backtracking Algorithms回溯算法的启发式

当使用回溯搜索解决CSP时，必须对要分支或实例化的变量以及要给该变量的值做出一系列决策。这些决策称为变量和值排序。已有研究表明，对于许多问题，变量的选择和值的排序对于有效解决问题是至关重要的(如[5,50,55,63])。变量或值排序可以是静态的(排序在搜索之前是固定的并确定)，也可以是动态的(排序在搜索过程中确定)。动态变量排序在文献中得到了广泛的关注。它们早在1965年就提出了[57]，现...

翻译 4.5 Non-Chronological Backtracking非时间顺序回溯

在发现死端后，回溯算法必须撤销先前发布的一些分支约束。在回溯的标准形式中，称为时间回溯，只有最近发布的分支约束才会被撤销。然而，按时间顺序回溯可能无法解决僵局的原因。在非时间回溯中，该算法回溯并撤销了与之关系最紧密的分支约束，该分支约束对死端负有一定的责任。在Gaschnig[48]之后，我将此过程称为回跳。非时间回溯算法可以描述为(i)用于发现和使用nogoods进行回溯的策略和(ii)用于...

翻译 4.4 Nogood Recording

要提高CSP上回溯搜索的性能，最有效的技术之一是添加隐含约束。如果CSP的一组解在有约束和没有约束的情况下是相同的，那么就隐含了一个约束。将“正确的”隐含约束添加到CSP可以意味着从搜索树中删除许多死端，并且在更少的搜索工作之后发现其他死端。研究了添加隐含约束的三种主要技术。一种技术是在建模阶段手工添加隐含的约束(参见第11章)。第二种技术是通过应用约束传播算法自动添加隐含约束(参见4.3节)...

翻译 4.3 Constraint Propagation

改进csp回溯算法性能的一个基本观点是，局部不一致会导致大量的抖动或无效率的搜索[47,89]。局部不一致性是某些变量的实例化，这些变量满足相关约束，但不能扩展到一个或多个额外变量，因此不能成为任何解决方案的一部分。(局部不一致不是好事;参见4.4节)。如果我们使用回溯搜索来寻找解决方案，这种不一致性可能导致搜索中出现许多死区，并导致许多徒劳的搜索工作。这种见解导致:描述CSP局部一致性水平的...

翻译 4.2 Branching Strategies

在朴素回溯算法（BT）中，搜索树中的节点p = {x1 = a1，...，xj = aj}是一组赋值，并且通过选择变量x并将分支添加到a来扩展p。 新节点p∪{x = a}，对于每个a∈dom（x）。赋值x = a据说是沿分支发布的。 随着搜索在树中更深入地进行，附加的分配被发布，并且在回溯时，分配被撤回。 然而，这只是一种可能的分支策略，并且在文献中已经提出并检查了几种替代方案。更一般地，回...

翻译 Chapter 4 Backtracking Search Algorithms

求解约束满足问题的算法技术主要有三种:回溯搜索、局部搜索和动态规划。本章主要研究回溯搜索算法。基于动态规划[15]的算法——有时在文献中称为变量消除、综合或推理算法——是第7章的主题。局部或随机搜索算法是第五章的主题。约束满足问题的求解算法可以是完全的，也可以是不完全的。完整的，或系统的算法，如果存在一个解决方案就保证能找到，也可以用来表明一个CSP没有解决方案，或找到一个可证明的最优解决方案...

原创 弧一致性Arc consistency算法(AC3, AC4, AC6, AC2001)整理

AC3：再判断一致性时，会对前面已判断过的再次判断AC4：改进AC3，在初始化时会存储所有判断，在移除值后，不用进行constraint check，只需traversal S lists和update counter。在不牵扯约束具体内容的情况下，已经具有最优的最差时间复杂度AC5：将约束的形式具体化为几种常用函数。对于函数约束，每个弧只需进行一次判断，大大缩减判断次数AC6：优化A...

原创 Constraint propagation and arc consistency （约束传播与弧一致性算法）框架

翻译 3.8 Specific Constraints具体的约束

在前几节中，我以一种通用的方式介绍了约束传播和局部一致性，但没有说明当我们对约束的语义有一些特定信息时应该做什么。在本节中，我将开发一些可用的技术来考虑约束语义。3.8.1 Specific Propagators in Solvers 求解器中的特定传播器所有的约束求解器都将特定的传播算法附加到它们所包含的特定类型的约束上。此外，它们中的大多数允许用户为合并的新约束设计自己的传播器。算术约...