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 so- lutions 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 monotonic- ity, 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.
*This paper applies the technique mentioned above in the context of CS education. Namely, we provided PDL as a problem description language for students to use when they try to program for CPs. With PDL, students only need to describe or model a CP; then they can rely on the PDL compiler (i.e., SoGen engine) to automatically generate the solution program. Different from the project mentioned above, this project does not propose any new technique or new tool. Instead, it reuses the existing tool, and assesses how the tool can helps students improve their problem-solving skills via programming.
Programming tasks provide an opportunity for students to improve their problem-solving skills (PSS). However, when programming tasks are challenging, students could become demotivated and lose the opportunity to improve PSS in the process. To scaffold the difficulty of programming tasks and better motivate students to enhance PSS via coding, this paper introduces PDL (Problem Description Language). Given the natural-language description of a combinatorial optimization problem (COP), PDL requires students to describe (i) inputs, (ii) constraints, (iii) the optimization objective, and (iv) outputs, based on their problem comprehension. PDL then validates each problem description by (1) compiling a solution program from the description and (2) executing the generated program with predefined test cases. Based on the compiling and testing results, PDL provides feedback to students, and assists students to adjust their problem comprehension and improve problem descriptions. To evaluate PDL's effectiveness in motivating students to fulfill challenging programming tasks, we conducted a user study with 185 undergraduates and asked the students to solve COPs with or without PDL. We found that the students with PDL were less likely to give up than students without PDL. By using PDL, students solved more COPs and spent less time on each problem; they became more confident and motivated in handling COPs after using PDL.
Constraint optimization problems (COP) on finite domains are typically solved via search. Many problems (e.g., 0-1 knapsack) involve redundant search, making a general constraint solver revisit the same subproblems again and again. Existing approaches use caching, symmetry breaking, subproblem dominance, or search with decomposition to prune the search space of constraint problems. In this paper, we present a different approach--DPSolver--which uses dynamic programming (DP) to efficiently solve certain types of constraint optimization problems (COPs). Given a COP modeled with MiniZinc, DPSolver first analyzes the model to decide whether the problem is efficiently solvable with DP. If so, DPSolver refactors the constraints and objective functions to model the problem as a DP problem. Finally, DPSolver feeds the refactored model to Gecode--a widely used constraint solver--for the optimal solution. Our evaluation shows that DPSolver significantly improves the performance of constraint solving.