Relational linear programming

DOI10.1016/J.ARTINT.2015.06.009zbMATH Open1404.68109arXiv1410.3125OpenAlexW753617165MaRDI QIDQ511779FDOQ511779

Pavel Tokmakov, Martin Mladenov, Kristian Kersting

Publication date: 22 February 2017

Published in: Artificial Intelligence (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1410.3125

zbMATH Keywords

optimizationlinear programmingmachine learningsymmetrylifted probabilistic inferencestatistical relational learningrelational logicequitable partitions(fractional) automorphismcolor-refinementlifted linear programmingorbit partitions

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Linear programming (90C05) Logic programming (68N17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• CVXGEN: a code generator for embedded convex optimization
• Graphical Models, Exponential Families, and Variational Inference
• 10.1162/153244303322753643
• Applications of Stochastic Programming
• Probabilistic logic
• Handbook of applied optimization
• Mixed Integer Programming: Analyzing 12 Years of Progress
• Itemset mining: a constraint programming perspective
• Probabilistic inductive logic programming. Theory and applications
• Markov logic networks
• Linear Programming
• Exploiting symmetries for scaling loopy belief propagation and relational training
• Linear programming boosting via column generation
• Compact graphs and equitable partitions
• Logical and Relational Learning
• Linear programming support vector machines
• Algorithms for highly symmetric linear and integer programs
• Practical solution techniques for first-order MDPs
• Algebraic languages for mathematical programming
• Fractional isomorphism of graphs
• Embedding optimisation algorithms with Mosel
• 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
• Dimension Reduction via Colour Refinement
• A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing
• Detecting Orbitopal Symmetries

Cited In (1)

• Static Analysis

Uses Software

• AMPL
• Gurobi
• Pyomo
• Mosel
• AIMMS
• GAMS
• CVXGEN
• CVXPY
• NetKit
• Dyna
• Tuffy

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)