  We propose relational linear programming, a simple framework for combing
linear programs (LPs) and logic programs. A relational linear program (RLP) is
a declarative LP template defining the objective and the constraints through
the logical concepts of objects, relations, and quantified variables. This
allows one to express the LP objective and constraints relationally for a
varying number of individuals and relations among them without enumerating
them. Together with a logical knowledge base, effectively a logical program
consisting of logical facts and rules, it induces a ground LP. This ground LP
is solved using lifted linear programming. That is, symmetries within the
ground LP are employed to reduce its dimensionality, if possible, and the
reduced program is solved using any off-the-shelf LP solver. In contrast to
mainstream LP template languages like AMPL, which features a mixture of
declarative and imperative programming styles, RLP's relational nature allows a
more intuitive representation of optimization problems over relational domains.
We illustrate this empirically by experiments on approximate inference in
Markov logic networks using LP relaxations, on solving Markov decision
processes, and on collective inference using LP support vector machines.
