First-Order Mixed Integer Linear Programming

cooperative control, we can use MILPs for task allocation under uncertainty [Alighanbari and How, 2005]. 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. Many decision problems naturally contain objects, classes of objects, and relations among them. In such problems, there are many benefits to reasoning about entire classes of objects at once—so-called lifted reasoning. One benefit is representational: it is much simpler to state a single lifted constraint such as “all cars must follow the speed limit” than to state the constraint for each car separately. Another is computational: if we can derive a conclusion for all class members at once, then we don’t need to derive it separately for each individual object. Lifted inference may incur some initial overhead, but its cost is independent of the number of objects involved, even when this number is infinite. A final benefit is statistical: if we can share parameters among members of a class, we can often reduce the number of parameters we need to estimate, increasing the level of accuracy we can attain for a given amount of data.

Authors

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

Keywords

No keywords are indexed for this paper.