TL;DR
This paper introduces "Russian Doll Search" (RDS), a novel algorithm for solving Constraint Optimization Problems (COPs). RDS significantly improves upon traditional Depth First Branch and Bound (DFBB) by systematically reusing information from searches on nested subproblems, leading to much tighter lower bounds and drastically reduced search times, especially for difficult problems.
What Problem Does This Paper Address?
Constraint Satisfaction Problems (CSPs) are fundamental in AI for problems with strict requirements. However, many real-world scenarios involve preferences alongside requirements, leading to Constraint Optimization Problems (COPs). While extensions like Valued Constraint Satisfaction Problems (VCSPs) handle this, solving them is significantly harder than satisfaction. Traditional complete search methods like Depth First Branch and Bound (DFBB) struggle because the lower bounds on the quality of partial solutions are often too optimistic, leading to massive search spaces. This paper aims to bridge this gap by developing a more efficient search strategy for COPs.
Methods
The core innovation is the Russian Doll Search (RDS) algorithm. Instead of a single, potentially massive search, RDS breaks the problem down into $n$ successive searches on nested subproblems, where $n$ is the number of variables. These subproblems are structured like Russian dolls: the first involves only the last variable, the second involves the last two, and so on, up to the full problem.
Key aspects of RDS:
- Nested Subproblems: The problem is decomposed into $n$ subproblems, each defined by a subset of variables from a fixed ordering.
- Information Reuse: The crucial insight is that the results (optimal assignment valuation) from solving a smaller subproblem are used to improve the lower bound for larger subproblems.
- Improved Lower Bounds: RDS enhances the lower bound calculation (specifically, LB3) by incorporating the valuation of the previously solved subproblem. This makes the bounds much less optimistic, especially early in the search.
- Static Variable Ordering: RDS relies on a static variable ordering, which is a simplification compared to some DFBB approaches that use dynamic ordering.
- Dynamic Value Ordering (Heuristic): For each subproblem, RDS uses a heuristic: it first tries the value that the variable had in the optimal assignment of the previous subproblem.
Datasets
The paper evaluates RDS on two types of datasets:
- Small random VCSPs: These problems are generated with varying parameters like number of variables ($n$), domain size ($d$), connectivity ($c$), constraint tightness ($t$), and graph bandwidth ($b$).
- Large real scheduling problems: Specifically, daily management problems for an earth observation satellite, originally conceived for this research. These problems are cast as additive CSPs.
Key Insights and Ideas
- The "Optimism" of Bounds is the Bottleneck: The paper strongly emphasizes that the inefficiency of standard DFBB in COPs stems from overly optimistic lower bounds, which fail to prune the search space effectively.
- Decomposition and Reuse is Powerful: Breaking down a hard problem into a sequence of smaller, related problems and systematically reusing their solutions is a highly effective strategy.
- Nested Structure is Key: The "Russian Doll" structure allows for a natural progression of information transfer, where solutions to smaller problems directly inform bounds for larger ones.
- Bandwidth Matters: The efficiency of RDS is significantly influenced by the bandwidth of the variable ordering used. Smaller bandwidths lead to better performance.
- Inconsistency is Where RDS Shines: RDS demonstrates its greatest advantage over standard DFBB on highly inconsistent problems, where traditional methods struggle the most.
Key Results
- Dramatic Speedups: RDS consistently outperforms standard DFBB, especially on difficult and inconsistent problems. For example, on earth observation satellite scheduling problems, RDS solved all eight typical problems within a 1800-second time limit per subproblem, while standard DFBB solved none.
- Improved Pruning: The tighter lower bounds provided by RDS lead to significantly earlier pruning of the search tree.
- Scalability on Real Problems: RDS successfully tackles large, previously unsolvable scheduling problems.
- Trade-off with Number of Searches: While RDS performs $n$ searches, the efficiency gains from improved bounds often outweigh the overhead, leading to a net speedup. The ratio of terminal nodes examined can be significantly better for RDS in many cases.
Limitations and Future Work
- Static Variable Ordering: RDS uses a static variable ordering. The authors suggest that exploring dynamic variable ordering within the RDS framework could yield further improvements.
- Minimizing Bandwidth: The paper notes that minimizing the bandwidth of the variable ordering is crucial for RDS's performance and suggests this as an area for future work.
- Hybrid Approaches: The authors propose combining RDS with other techniques, such as using a Constraint Satisfaction algorithm for subproblems that are known to be consistent, or employing mixed static/dynamic variable ordering strategies.
- Theoretical Bounds: While RDS shows practical gains, the paper acknowledges that in some specific, highly constrained scenarios (like the "Ptight" example), the number of searches could lead to a worse worst-case complexity than standard DFBB. However, the practical synergy often overcomes this.
Summary updated