约束编程求解器并行化的分区方法及QBD-M过程的谱展开解法

### 约束编程求解器并行化的分区方法及QBD - M过程的谱展开解法 #### 约束编程求解器并行化 在对约束编程求解器进行并行化时，需要考虑以下几个关键因素： - **使用的核心数量**：不同数量的核心会对求解效率产生影响。 - **核心之间的通信类型**：合适的通信类型有助于提高并行计算的效率。 - **约束是否在核心之间共享**：这关系到各个核心的计算任务分配。 大多数用于解决约束问题的算法会将搜索空间构建成搜索树的形式，通过探索搜索树来获取第一个或所有可能的解。搜索树由三种类型的节点组成：根节点、内部节点和叶子节点。根节点代表包含所有约束的原始问题，内部节点代表原始问题的部分解，满足部分约束，叶子节点则要么是解，要么是失败节点（即从该节点无法找到解，至少有一个约束永远无法满足）。 为了对搜索树进行并行化，通常使用两种方法： - **静态分区**：在执行前对搜索空间进行分区，然后将每个子树分配到一个核心上。 - **动态分区**：在算法执行过程中选择搜索空间的分区和分配。 ##### 静态分区 静态分区方法首先探索搜索树的前几层，以获取足够数量的节点（每个节点代表一个待探索的子树的根）。然后将这些节点分配到不同的核心上进行搜索。这种方法实现简单，且机器核心之间的通信较少。不过，搜索树通常是不平衡的，很难甚至不可能估计从一个节点可访问的子树的大小。这就导致有时只有一个计算核心几乎承担了所有的搜索任务，其他核心需要等待该核心完成。 ##### 动态分区（工作窃取） 动态分区的原理是机器的不同核心通过全局优先级队列共享工作。搜索树根据需求进行分区并分配给核心。线程使用OR - Tools求解器在本地顺序执行搜索。当一个线程完成其所在子树的搜索后，它会从全局优先级队列中获取新的任务。如果全局优先级队列为空，该线程将声明自己为待处理线程。正在搜索子树的其他线程会检查是否有待处理线程存在。如果存在，会停止左分支的搜索，创建一个BOB节点，将其插入全局优先级队列，然后继续在右节点上进行搜索。待处理线程会因新BOB节点插入优先级队列而被激活。 在OR - Tools库中，当节点n从求解器1迁移到求解器2时，求解器1会停止在节点n上的搜索，将从根节点到节点n的路径保存到BOB节点中，将BOB节点传递给求解器2。求解器2会重新执行从根节点到节点n的路径以设置所有内部数据，然后继续在以节点n为根的子树上进行搜索。 然而，每次节点从一个求解器迁移到另一个求解器时，会产生一些冗余节点，这会给每次负载均衡操作带来额外开销。为了减少冗余节点的数量，需要最小化每个创建的BOB节点必须重新执行的路径长度，为此使用了一个阈值来限制BOB节点的最大深度。选择合适的阈值是一个难题，较小的阈值会使算法接近静态分区方法，而较大的阈值会使算法类似于没有阈值的动态版本。当前算法在搜索开始时静态确定阈值。 以下是迁移测试的算法： ```plaintext Require: S, the dynamic partitioning threshold Let P, the depth of the current node if ∃at least one pending thread AND P < S then Stop the search on the left branch Create a BOB - node Insert the BOB - node in the global queue Restart the search on the right sub - tree else Continue the sequ ```