First-Order Mixed Integer Linear Programming

Geoffrey J. Gordon, Sue Ann Hong, Miroslav Dudík

Abstract: Mixed integer linear programming (MILP) is a powerful representation often used to formulate decision-making problems under uncertainty. However, it lacks a natural mechanism to reason about objects, classes of objects, and relations. First-order logic (FOL), on the other hand, excels at reasoning about classes of objects, but lacks a rich representation of uncertainty. While representing propositional logic in MILP has been extensively explored, no theory exists yet for fully combining FOL with MILP. We propose a new representation, called first-order programming or FOP, which subsumes both FOL and MILP. We establish formal methods for reasoning about first order programs, including a sound and complete lifted inference procedure for integer first order programs. Since FOP can offer exponential savings in representation and proof size compared to FOL, and since representations and proofs are never significantly longer in FOP than in FOL, we anticipate that inference in FOP will be more tractable than inference in FOL for corresponding problems.

Introduction

In artificial intelligence, researchers often face a trade-off between two powerful formalisms: First-Order Logic (FOL) and Mixed Integer Linear Programming (MILP). FOL is highly effective for "lifted" reasoning, allowing for rules that apply to entire classes of objects (e.g., "All vehicles must obey traffic laws"). However, it struggles with numerical uncertainty and optimization, typically treating statements as strictly true or false. Conversely, MILP is the industry standard for optimization and decision-making under uncertainty but lacks a native way to handle object-oriented structures. To apply a rule to 1,000 objects in MILP, one must manually generate 1,000 separate constraints—a process known as "grounding" that becomes impossible if the number of objects is unknown or infinite.

This paper introduces First-Order Programming (FOP), a novel framework that bridges this expressivity gap. FOP is a representation that subsumes both FOL and MILP, allowing for complex reasoning over object-oriented worlds where numerical constraints and optimization are central.

First-Order Programming (FOP)

FOP extends the syntax and semantics of traditional logic by allowing predicates to return real or integer values instead of simple boolean truth values. This allows the framework to represent both logical conditions and numerical quantities within a unified mathematical structure.

A key aspect of FOP is its ability to translate standard logical constructs into numerical representations suitable for optimization. As shown in the table below, logical operators like conjunction, disjunction, and negation can be mapped to numerical operations. This mapping allows the system to treat logical quantifiers ($\forall, \exists$) as optimization operators (infimum and supremum, or $\wedge$ and $\vee$ in a lattice context).

Translation of First-Order Logic (FOL) constructs into numerical representations (Trans. A and Trans. B).

Lifted Inference and Normal Forms

The technical core of FOP involves a pipeline to transform complex sentences into a "Reduced Normal Form," which essentially functions as a collection of first-order linear constraints. The paper's most significant algorithmic contribution is the introduction of Lifted Gomory Cuts.

In standard MILP, Gomory cuts are used to prune the search space by adding new linear inequalities that exclude non-integer solutions. The authors "lift" this concept to the first-order level. By utilizing variable substitution and unification—techniques borrowed from symbolic logic—they can derive a single "lifted" constraint that applies to an entire family of objects simultaneously. This allows for efficient reasoning that can be independent of the total number of objects involved.

Theoretical Advantages

FOP offers several theoretical advantages over traditional grounding-based methods:

  • Subsumption: FOP is a true superset of both FOL and MILP. Any FOL sentence or MILP problem can be translated into FOP without an increase in representation size.
  • Exponential Compression: FOP can be exponentially more compact than FOL. For instance, expressing that "at least $k$ out of $n$ objects have property $P$" requires a massive disjunction in FOL, but is a simple linear inequality in FOP: $\sum P(x_i) \ge k$.
  • Soundness and Completeness: The authors prove that their lifted inference procedure is sound and complete for the integer fragment of FOP. This ensures that the system will always find a valid proof if one exists and will never reach a false conclusion.

Conclusion and Future Work

While FOP establishes a robust foundation for merging logic and optimization, several challenges remain. The current system is optimized for purely integer problems; extending "entailment" to mixed-integer problems involving continuous variables may require "approximate entailment" strategies. Additionally, while FOL benefits from decades of research into search-control heuristics, FOP currently lacks these specialized guides for rule application. Future work will focus on developing these heuristics and extending the language to natively handle object equality and summation quantifiers.

Summary updated

Abstract

Mixed integer linear programming (MILP) is a powerful representation often used to formulate decision-making problems under uncertainty. However, it lacks a natural mechanism to reason about objects, classes of objects, and relations. First-order logic (FOL), on the other hand, excels at reasoning about classes of objects, but lacks a rich representation of uncertainty. While representing propositional logic in MILP has been extensively explored, no theory exists yet for fully combining FOL with MILP. We propose a new representation, called first-order programming or FOP, which subsumes both FOL and MILP. We establish formal methods for reasoning about first order programs, including a sound and complete lifted inference procedure for integer first order programs. Since FOP can offer exponential savings in representation and proof size compared to FOL, and since representations and proofs are never significantly longer in FOP than in FOL, we anticipate that inference in FOP will be more tractable than inference in FOL for corresponding problems.
BibTeX
@inproceedings{gordon2009first,
  author = {Geoffrey J. Gordon and Sue Ann Hong and Miroslav Dudík},
  title = {{First-Order Mixed Integer Linear Programming}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=Q1jxBWfcdR},
}
Figure