用CDCL快速判断布局可行性，再用CP-SAT高效求最优解。
Accelerating Discrete Facility Layout Optimization: A Hybrid CDCL and CP-SAT Architecture
- 先用CDCL快速判断布局是否可行，利用冲突驱动学习加速搜索。
- 在高约束密度下，CDCL求解可行性比其他方法快数十倍。
- 提出混合架构，用CDCL生成提示，显著提升CP-SAT优化速度。
离散设施布局设计需在满足严格安全与空间约束的前提下最小化搬运成本，属于组合优化难题。传统方法如混合整数线性规划（MILP）和约束编程（CP）在约束密度升高时面临可扩展性挑战。本文系统评估了基于VSIDS启发式的冲突驱动子句学习（CDCL）作为替代计算引擎的潜力。通过统一基准测试框架，在不同网格尺寸和约束密度下对比了CDCL、CP-SAT与MILP的表现。实验显示明显性能分化：尽管CDCL因成本无感知分支在优化目标上表现不佳，但在可行性检测方面展现出无与伦比的优势，处理高约束实例的速度比其他范式快数个数量级。基于此发现，我们提出一种新型“热启动”混合架构，利用CDCL快速生成有效可行性提示，并将其注入CP-SAT优化器。结果表明，该分层方法通过SAT驱动剪枝，成功弥合了快速可满足性与严格最优性之间的差距，显著加速精确优化。
原文摘要 · Abstract (English)
Discrete facility layout design involves placing physical entities to minimize handling costs while adhering to strict safety and spatial constraints. This combinatorial problem is typically addressed using Mixed Integer Linear Programming (MILP) or Constraint Programming (CP), though these methods often face scalability challenges as constraint density increases. This study systematically evaluates the potential of Conflict-Driven Clause Learning (CDCL) with VSIDS heuristics as an alternative computational engine for discrete layout problems. Using a unified benchmarking harness, we conducted a controlled comparison of CDCL, CP-SAT, and MILP across varying grid sizes and constraint densities. Experimental results reveal a distinct performance dichotomy: while CDCL struggles with optimization objectives due to cost-blind branching, it demonstrates unrivaled dominance in feasibility detection, solving highly constrained instances orders of magnitude faster than competing paradigms. Leveraging this finding, we developed a novel "Warm-Start" hybrid architecture that utilizes CDCL to rapidly generate valid feasibility hints, which are then injected into a CP-SAT optimizer. Our results confirm that this layered approach successfully accelerates exact optimization, using SAT-driven pruning to bridge the gap between rapid satisfiability and proven optimality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。