Relational Linear Programs

Abstract : 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.
Complete list of metadatas

Cited literature [72 references]  Display  Hide  Download

https://hal.inria.fr/hal-01131726
Contributor : Thoth Team <>
Submitted on : Sunday, March 15, 2015 - 3:26:06 PM
Last modification on : Monday, March 23, 2015 - 2:02:03 PM
Long-term archiving on : Tuesday, June 16, 2015 - 10:11:06 AM

File

1410.3125v1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01131726, version 1
  • ARXIV : 1410.3125

Citation

Kristian Kersting, Martin Mladenov, Pavel Tokmakov. Relational Linear Programs. 2015. ⟨hal-01131726⟩

Share

Metrics

Record views

129

Files downloads

426