Generating efficient solvers from constraint models

Combinatorial problems (CPs) arise in many areas, and people use constraint solvers to automatically solve these problems. However, the state-of-the-art constraint solvers (e.g., Gecode and Chuffed) have overly complicated software architectures; they compute solutions inefficiently. This paper presents a novel and model-driven approach-SoGen-to synthesize efficient problem-specific solvers from constraint models. Namely, when users model a CP with our domain-specific language PDL (short for Problem Description Language), SoGen automatically analyzes various properties of the problem (e.g., search space, value boundaries, function monotonicity, and overlapping subproblems), synthesizes an efficient solver algorithm based on those properties, and generates a C program as the problem solver. SoGen is unique because it can create solvers that resolve constraints via dynamic programming (DP) search.

For evaluation, we compared the solvers generated by SoGen with two state-of-the-art constraint solvers: Gecode and Chuffed. SoGen's solvers resolved constraints more efficiently; they achieved up to 6,058x speedup over Gecode and up to 31,300x speedup over Chuffed. Additionally, we experimented with both SoGen and the state-of-the-art solver generator-Dominion. We found SoGen to generate solvers faster and the produced solvers are more efficient.