Optimizing Constraint Solving via Dynamic Programming

Shu Lin, Na Meng, Wenxin LiIJCAI 2019 · DOI

TL;DR

This paper introduces DPSolver, a novel approach that automatically identifies and reformulates constraint optimization problems (COPs) solvable by dynamic programming (DP). By transforming COPs into DP-oriented models, DPSolver significantly accelerates solving times, outperforming existing state-of-the-art constraint solvers on a benchmark of optimization tasks.

What Problem Does This Paper Address?

Constraint optimization problems (COPs) are common in various fields, and solving them often involves search algorithms. A significant challenge in these search processes is the occurrence of redundant computations when different branches of the search tree lead to the same subproblems. Existing methods like caching, symmetry breaking, and decomposition aim to mitigate this redundancy. However, the paper highlights that a powerful classical technique, dynamic programming (DP), has been largely underutilized for solving general constraint models, despite its effectiveness in breaking down complex problems into smaller, overlapping subproblems. The core problem addressed is how to automatically leverage DP to optimize the solving of a broad range of COPs.

Methods

DPSolver employs a three-phase approach:

  1. DP Problem Recognition: This phase automatically determines if a given COP, modeled in MiniZinc, exhibits the two key properties of DP:
  2. Optimal Substructures: An optimal solution to the problem can be constructed from optimal solutions to its subproblems.
  3. Overlapping Subproblems: The same subproblems are encountered multiple times during the decomposition process. DPSolver achieves this by identifying array variables, converting constraints and objective functions into recursive forms, and then formally checking for these properties using theorems and derivative analysis.

  4. DP-Oriented Model Generation: If a problem is identified as DP-solvable, DPSolver refactors the original model into a DP-oriented one. This involves creating a table-based structure (e.g., a 2D array dpvalue) to store and reuse intermediate results of subproblems. This transformed model is then passed to a general constraint solver (Gecode) to perform the DP search.

  5. DP-Oriented Model Selection: For problems where multiple DP-oriented models can be generated (e.g., by choosing different candidate variables or combinations), DPSolver estimates the time and space complexity of each model. It then selects the model that fits within user-specified memory limits and offers the best performance improvement.

The approach also includes handling for "aftereffects" (where a subproblem's solution depends on more than just the immediately preceding subproblem) by increasing table dimensions, and for problems with overlapping subproblems but no optimal substructures by still using memoization.

Datasets

The paper introduces a dataset of 9 representative COP tasks for evaluation:

  • 0-1 knapsack
  • Complete knapsack
  • Nested 0-1 knapsack
  • Shortest path
  • Longest increasing subsequence
  • Longest common subsequence
  • Radiation therapy
  • Modulus 0-1 knapsack
  • Blackhole

The first seven are identified as DP problems, while the last two (Modulus 0-1 knapsack and Blackhole) are non-DP problems that still exhibit overlapping subproblems (P2 property). The authors note that these problems were chosen for their distinct DP structures and representativeness.

Key Insights and Ideas

  • Automated DP Identification: The core innovation is the ability to automatically detect DP potential in general constraint models, rather than requiring manual reformulation by the user.
  • Leveraging DP for General Solvers: DPSolver doesn't reinvent constraint solvers; it transforms problems into a format that existing, powerful solvers can execute efficiently using DP principles.
  • Handling Non-Pure DP Problems: The approach extends beyond strictly DP problems, offering benefits for problems with overlapping subproblems even if they lack optimal substructures, by using memoization.
  • Model Selection for Efficiency: The ability to generate and select among multiple DP-oriented models based on complexity is crucial for practical application, especially under memory constraints.

Key Results

  • Significant Speedups: DPSolver achieved substantial performance improvements across the board. On average, it provided a 698x speedup over Gecode and a 790x speedup over a basic CHUFFED solver.
  • Outperforming Optimized Solvers: DPSolver significantly outperformed optimized solvers like CHUFFEDC (caching) and CHUFFEDL (Lazy Clause Generation), achieving a 345x speedup over CHUFFEDL on average for solvable problems and a 23x speedup over CHUFFEDC.
  • Negligible Analysis Overhead: The time spent by DPSolver on analyzing models and generating new ones was minimal (0.03-0.18 seconds), making the optimization cost negligible compared to the solving time saved.
  • Broad Applicability: DPSolver successfully optimized 9 representative COP tasks, including both DP and non-DP problems with overlapping subproblems.

Limitations and Future Work

  • Current Limitations:
    • DPSolver currently handles problems with array or set variables and constraints defined using built-in MiniZinc operations and non-recursive functions.
  • The applicability is also limited by available memory, as DP requires storing intermediate results. The paper provides a formula to estimate space complexity.
  • Future Work:
    • Extend support to other data structures like trees.
  • Develop capabilities to automatically create DP-oriented models from natural language problem descriptions.
  • Improve handling of more complex constraints and potentially non-DP problems with more sophisticated techniques.

Summary updated

BibTeX
@inproceedings{lin2019optimizing,
  author = {Shu Lin and Na Meng and Wenxin Li},
  title = {{Optimizing Constraint Solving via Dynamic Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/160},
}
Figure