An Instantiation-Based Theorem Prover for First-Order Programming

Erik Zawadzki, Geoffrey J. Gordon, André Platzer

Introduction

Automated reasoning often faces a dichotomy between the expressive power of First-Order Logic (FOL) and the computational efficiency of Mixed-Integer Linear Programming (MILP). While MILP is the gold standard for solving large-scale optimization problems involving arithmetic and inequalities, it is inherently propositional. To model a statement like "all agents must adhere to a constraint," a MILP solver requires an explicit enumeration of every agent, a process known as grounding. This approach fails when the domain is extremely large or potentially infinite. Conversely, FOL allows for "lifted" reasoning over classes of objects but typically struggles with the linear arithmetic essential for real-world engineering and planning.

This paper introduces a new theorem prover for First-Order Programming (FOP), a language designed to bridge this gap by merging the optimization power of MILP with the expressive reasoning of FOL.

The FOP Framework

In FOP, predicates are not limited to boolean values; they can represent integer values. Formulas are structured in a "$\wedge$-normal form," utilizing operations such as minimization ($\wedge$), maximization ($\vee$), and addition. This structure allows for the representation of complex logical relationships intertwined with numerical constraints, providing a framework for lifted inference without the need to enumerate every possible object in a universe.

Methodology: Iterative Refinement

The authors propose an instantiation-based methodology. Rather than attempting to solve a full first-order problem directly, the system iteratively refines a simplified propositional model using a novel "Semantic Instance Generation" rule.

1. Propositionalization and the MILP Oracle

The process begins by creating a "ground" version of the first-order formula. Variables are initially replaced with a special constant, resulting in a standard MILP. This ground version is then passed to a MILP solver, which acts as a "black box" oracle to find a candidate solution for this simplified version.

2. Semantic Instance Generation (SIG)

The core innovation of this work is the Semantic Instance Generation (SIG) rule. When the MILP solver returns a solution, the prover examines it for "discordant pairs." A discord occurs when the solver assigns different values to two terms that are logically unifiable (i.e., they could represent the same object in the first-order domain). In a purely propositional solver, these terms are treated as distinct entities, effectively "cheating" the logic by ignoring their potential identity.

3. Refinement Loop

Upon identifying a discord, the SIG rule generates specific constraints (instances) to resolve the discrepancy. These new constraints are added back into the MILP, and the solver is invoked again. This loop continues until one of two conditions is met:

  • The MILP solver proves the problem is infeasible.
  • The solver finds a model that is consistent with the first-order logic (a "lifted" model).

Key Results and Evaluation

The primary contribution of the paper is the mathematical proof that this Feasibility Algorithm is both sound (it will never return a false positive) and refutationally complete (if no solution exists, the algorithm will eventually prove it) for the integer fragment of FOP.

To demonstrate the practical utility of the prover, the authors applied it to a synthetic vehicle routing problem involving eight equivalence classes of locations. The prover successfully demonstrated the non-existence of a path between certain classes. Notably, because the prover reasons about classes rather than individual objects, the proof remains valid even if the domain contains an infinite number of objects within those classes. This ability to prove non-existence in unbounded domains is a significant advantage over traditional propositional planners, which often rely on a fixed "horizon" and fail to provide definitive proofs of impossibility.

Limitations and Future Work

While the FOP prover represents a significant step forward, several challenges remain for future research:

  • Heuristics for Selection: The current iteration requires a "fair rule" for instance selection. In complex scenarios, the number of potential instances grows quadratically ($O(n^2)$), necessitating sophisticated automated heuristics to maintain efficiency.
  • Redundancy Management: The algorithm can generate redundant clauses. Future work will explore "restriction criteria" to prune the search space, drawing inspiration from classical FOL theorem provers.
  • Theory Expansion: The current implementation is limited to the integer fragment. Extending the framework to handle real numbers or more complex background theories (such as equality) is a priority.
  • Computational Optimization: The authors suggest that "warm-starting" the MILP solver—using the solution from a previous iteration to initialize the next—could significantly reduce computation time.

Conclusion

By treating theorem proving as the iterative refinement of a numerical optimization problem, the authors provide a powerful new tool for lifted inference. The FOP prover combines the strengths of MILP and FOL, offering a path toward solving structured, large-scale problems that were previously computationally intractable.

Summary updated

BibTeX
@article{zawadzki2011instantiation,
  author = {Erik Zawadzki and Geoffrey J. Gordon and André Platzer},
  title = {{An Instantiation-Based Theorem Prover for First-Order Programming}},
  journal = {AISTATS},
  year = {2011},
}
Figure