Relational linear programming
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 5296741 (Why is no real title available?)
- scientific article; zbMATH DE number 43398 (Why is no real title available?)
- scientific article; zbMATH DE number 710106 (Why is no real title available?)
- scientific article; zbMATH DE number 1391397 (Why is no real title available?)
- 10.1162/153244303322753643
- A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing
- Algebraic languages for mathematical programming
- Algorithms for highly symmetric linear and integer programs
- Applications of Stochastic Programming
- CVXGEN: a code generator for embedded convex optimization
- Compact graphs and equitable partitions
- Detecting orbitopal symmetries
- Dimension reduction via colour refinement
- Embedding optimisation algorithms with Mosel
- Exploiting symmetries for scaling loopy belief propagation and relational training
- Fractional isomorphism of graphs
- Global inference for sentence compression: an integer linear programming approach
- Graphical models, exponential families, and variational inference
- Handbook of applied optimization
- Itemset mining: a constraint programming perspective
- Linear Programming
- Linear programming boosting via column generation
- Linear programming support vector machines
- Logical and Relational Learning
- Markov logic networks
- Mixed integer programming: analyzing 12 years of progress
- Network flows. Theory, algorithms, and applications.
- Practical solution techniques for first-order MDPs
- Probabilistic inductive logic programming. Theory and applications
- Probabilistic logic
- Relational dependency networks
- Sets and indices in linear programming modelling and their integration with relational data models
- Sherali-Adams relaxations and indistinguishability in counting logics
- Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
Cited in
(3)
This page was built for publication: Relational linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511779)
