Projection, Inference, and Consistency

John N. HookerIJCAI 2016

Abstract: This paper establishes a theoretical bridge between logical inference and constraint programming by framing both as projection problems. By standardizing the concept of projection, the author introduces J-consistency—a generalization of domain consistency—and provides efficient algorithms for projecting common global constraints. This unified perspective leads to more powerful pruning techniques and identifies deep connections between optimization methods like Benders decomposition and logical deduction.

Introduction

Automated reasoning has traditionally been divided into two distinct disciplines: logic, which focuses on deducing new facts through inference, and constraint programming (CP), which focuses on pruning search spaces via consistency maintenance. While logic-based methods often look for global implications, CP consistency is frequently limited to "domain consistency," which examines variables in isolation. In this work, J. N. Hooker argues that these two fields are fundamentally linked by the mathematical concept of projection: reducing a high-dimensional solution set to a lower-dimensional one.

Inference as a Projection Problem

The paper demonstrates that deducing all information about a subset of variables is equivalent to computing a projection of the constraint set onto those variables. A key insight is the role of Logic-based Benders Decomposition. While typically viewed as a large-scale optimization technique, it can be re-envisioned as a logic-based inference engine that "learns" nogoods (logical clauses excluding infeasible regions) to compute projections more efficiently than traditional resolution methods.

Figure 1: A search tree illustrating the relationship between variable assignments and the inference of logical clauses.

J-Consistency and Global Constraints

To bridge the gap between simple domain consistency and full inference, Hooker proposes J-consistency. This concept involves projecting a constraint set onto a specific subset of variables $J$. When $J$ is a single variable, J-consistency reduces to standard domain consistency. However, by choosing larger subsets, solvers can capture complex inter-variable dependencies.

The core technical contribution lies in specific "recipes" for projecting common global constraints:

  • among: Uses recursive formulas to project bounds.
  • sequence: Employs an adaptation of Fourier-Motzkin elimination for 0-1 variables, achieving $O(kq)$ complexity.
  • regular: Involves truncating the state transition graph of the finite automaton defining the constraint.
  • all-different: Results in a disjunction of simpler "at most" constraints, highlighting the inherent complexity of projecting this common requirement.
Figure 2: Projection of a `regular` constraint by truncating its underlying state transition graph.

Beyond the Domain Store

Traditional CP solvers rely on a "domain store" to track possible values for each variable. Hooker argues that J-consistency is most effective when paired with Multi-valued Decision Diagrams (MDDs). Unlike simple lists, MDDs can represent the intricate relationships discovered through projection, preventing the "expression swell" that can occur with complex constraints like all-different.

Conclusion

By unifying inference and consistency under the banner of projection, this work provides a rigorous foundation for developing next-generation solvers. The proposed algorithms for global constraints offer a path toward more efficient pruning, particularly in scheduling and routing problems where variables are tightly coupled. Future research will focus on the full integration of these J-consistency techniques into MDD-based solvers to evaluate their impact on large-scale practical applications.

Summary updated

BibTeX
@inproceedings{hooker2016projection,
  author = {John N. Hooker},
  title = {{Projection, Inference, and Consistency}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure