The Constrainedness of Search

AAAI 1996

TL;DR

This paper introduces a general parameter, "constrainedness" (κ), to quantify how "hard" a set of combinatorial problems is, unifying existing measures across different problem classes. This measure not only helps predict phase transitions where problems shift from easily solvable to insoluble but also forms the basis for a powerful new heuristic that outperforms traditional methods in guiding search.

What Problem Does This Paper Address?

Researchers in Artificial Intelligence have long grappled with understanding why some combinatorial problems are easy to solve while others are incredibly difficult. This difficulty often manifests as a "phase transition" – a sharp boundary where a slight change in problem parameters (like size or complexity) causes a dramatic shift from a state where solutions are abundant and easily found to a state where solutions are rare or non-existent. Predicting and understanding these phase transitions is crucial for developing effective search algorithms and heuristics. While various measures have been proposed for specific problem classes (like satisfiability or graph coloring), there's been a lack of a unifying concept that can compare the difficulty across these diverse problem types. This paper aims to bridge that gap by introducing a general measure of "constrainedness."

Methods

The core contribution is the definition of a parameter, κ (kappa), which quantifies the "constrainedness" of an ensemble of combinatorial problems. This parameter is derived from the expected number of solutions (Sol) within a problem's state space (|S|). Specifically, κ is defined as:

$ \kappa = 1 - \frac{\log_2(\text{Sol})}{N} $

where N is the number of bits required to represent a state in the problem's search space (N = log₂|S|). The intuition is that if problems are over-constrained, they have few solutions (Sol is small), leading to a high κ. Conversely, under-constrained problems have many solutions (Sol is large), resulting in a low κ.

The paper demonstrates how this general definition can be applied to various problem classes, showing that it unifies existing parameters used in satisfiability, constraint satisfaction problems (CSPs), graph coloring, and number partitioning. A key application of κ is as a heuristic for guiding search. The proposed heuristic aims to minimize κ at each step of the search process, effectively choosing the branch that leads to the least constrained subproblem. This is tested against established heuristics like the "fail-first" (FF) principle.

Datasets

The paper does not introduce new datasets. Instead, it uses randomly generated problem instances from established classes to evaluate its proposed methods. These include:

  • Satisfiability (SAT): Random boolean expressions.
  • Constraint Satisfaction Problems (CSPs): Random binary CSPs with parameters (n, m, p₁, p₂) controlling the number of variables, domain size, constraint density, and constraint tightness.
  • Graph Coloring: Random graphs.
  • Number Partitioning: Random numbers drawn from (0,1].
  • Asymmetric Traveling Salesman Problem (ATSP): Inter-city distances drawn from a normal distribution.

Key Insights and Ideas

  • Unified Measure of Difficulty: The concept of "constrainedness" (κ) provides a single, general parameter to compare the difficulty of diverse combinatorial problems, moving beyond class-specific measures.
  • Predicting Phase Transitions: κ is shown to be a reliable indicator of phase transitions, with a value around 1 often marking the shift from soluble to insoluble problem instances. This allows for a more direct comparison of transition points across different problem domains.
  • "Minimize κ" Heuristic: The paper proposes a novel search heuristic that actively seeks to minimize κ at each decision point. This heuristic is shown to be highly effective, outperforming traditional methods like the "fail-first" principle, especially near the phase transition.
  • Reinterpreting Existing Heuristics: Many existing heuristics for CSPs and other problems can be understood as proxies or direct attempts to minimize κ, providing a unified theoretical foundation for these diverse strategies.

Key Results

  • The proposed parameter κ successfully generalizes and unifies existing "order parameters" used in satisfiability, CSPs, graph coloring, and number partitioning.
  • The paper demonstrates that phase transitions in these different problem classes often occur around κ ≈ 1.
  • Experiments with randomly generated binary CSPs show that the "minimize κ" heuristic significantly outperforms the "fail-first" heuristic in terms of search effort (consistency checks and trial instantiations), particularly around the phase transition. For example, paired-sample t-tests showed strong statistical evidence in favor of the minimize-κ heuristic.
  • In the Asymmetric Traveling Salesman Problem (ATSP), κ is used to model the probability of finding a tour of a certain length, and finite size scaling techniques, using κ as a temperature-like parameter, accurately predict the behavior of the phase transition.

Limitations and Future Work

  • Computational Cost of κ: The paper acknowledges that computing κ directly can be computationally expensive, especially for complex problems. This leads to the exploration of "proxies" for κ, such as variable domain size, which are cheaper to compute.
  • Heuristic Nature of Ensemble Definition: The calculation of κ relies on defining an "ensemble" of problems. For real-world problems, defining the appropriate ensemble and thus the relevant κ can be challenging.
  • Further Exploration of Proxies: While proxies like domain size are discussed, further research into more sophisticated and efficient proxies for κ is suggested.
  • Application to Real-World Problems: The paper highlights the need for further work in applying these concepts to real-world problems, where the ensemble from which a problem is drawn might not be clearly defined.
  • Connections to Markov Processes: The authors suggest exploring the connections between constrainedness and the transition probabilities of abstracted Markov processes for modeling search.

Summary updated

BibTeX
@inproceedings{1996constrainedness,
  title = {{The Constrainedness of Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure