Accelerating Discrete Facility Layout Optimization: A Hybrid CDCL and CP-SAT Architecture
This work addresses scalability challenges in facility layout optimization for industrial applications, representing an incremental improvement through a novel hybrid method.
The paper tackles the combinatorial optimization problem of discrete facility layout design by developing a hybrid architecture that combines Conflict-Driven Clause Learning (CDCL) for rapid feasibility detection with CP-SAT for optimization, resulting in accelerated exact optimization that bridges the gap between satisfiability and optimality.
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.