Abstract: First-Order Programming (FOP) is a novel framework that integrates the expressive power of First-Order Logic (FOL) with the optimization capabilities of Mixed Integer Linear Programming (MILP). Traditional automated reasoning often forces a choice between the relational expressivity of FOL and the numerical decision-making of MILP. FOP bridges this gap by allowing predicates to return bounded real or integer values and introducing "lifted" inference procedures. Specifically, the authors propose lifted Gomory cuts, which allow solvers to derive constraints for entire classes of objects simultaneously. This approach achieves exponential compactness in representation and provides a sound and complete inference procedure for the integer fragment of FOP.
Introduction
In the landscape of automated reasoning, two dominant paradigms exist: First-Order Logic (FOL) and Mixed Integer Linear Programming (MILP). FOL is adept at reasoning about complex relationships and universal properties (e.g., "every vehicle must have a license"). However, it is fundamentally binary and struggles with numerical optimization and uncertainty. Conversely, MILP is the industry standard for decision-making under constraints but is inherently "propositional." To model a system with 1,000 entities, a MILP modeler must manually define 1,000 separate sets of constraints, a process known as "grounding."
This paper introduces First-Order Programming (FOP) to address the lack of "lifted reasoning" in optimization—the ability to derive conclusions for entire classes of objects without grounding them into massive, individual constraints.
The First-Order Programming Framework
FOP generalizes FOL by allowing predicates to return values in a bounded range of reals or integers, rather than just boolean truth values. This shift transforms logical formulas into linear expressions. The framework introduces quantifiers such as the infimum ($\bigwedge$, analogous to $\forall$) and the supremum ($\bigvee$, analogous to $\exists$).
As shown in the translation table above, FOP can accommodate different semantic interpretations. For instance, "Trans. A" maps truth to 1 and falsehood to -1, while "Trans. B" uses a 0/1 mapping. These translations allow logical operators like negation ($\neg P$) to be expressed as linear transformations (e.g., $1-P$), effectively embedding logic within a continuous or discrete optimization space.
Lifted Inference and Gomory Cuts
The core technical innovation of FOP is the "lifted Gomory cut." In standard MILP, Gomory cuts are a method for pruning the search space by generating linear constraints that exclude non-integer solutions from the linear relaxation. The authors "lift" this concept to the first-order level. Instead of generating a cut for a single variable, the FOP solver generates a single constraint that applies to an entire family of related variables. This is conceptually similar to resolution in FOL, where a single inference step can apply to all objects satisfying a predicate.
Key Insights and Results
FOP offers several advantages over traditional methods:
- Exponential Compactness: Certain logical requirements, such as "at least $k$ out of $n$ objects must satisfy property $P$," require complex disjunctions in FOL but can be represented as a simple linear sum in FOP.
- Scale Independence: The cost of lifted inference is often independent of the domain size. A single lifted cut can address a constraint for 10 objects or 10,000 objects with equal complexity.
- Soundness and Completeness: The authors prove that their lifted inference procedure is sound and complete for the integer fragment of FOP. This ensures that if a solution exists, the algorithm will find it through a finite sequence of lifted cuts.
Conclusion and Future Work
FOP represents a significant step toward unifying logic and optimization. While the framework is robust for integer problems, extending full completeness to mixed-integer problems remains a challenge. Future research will focus on developing search heuristics for selecting optimal lifted cuts, similar to the decades of research on resolution strategies in FOL. Additionally, incorporating native equality predicates and summation quantifiers will be essential for applying FOP to real-world domains like entity resolution and stochastic programming.
Summary updated