by D Jain, P Maier and G Wylezich
Abstract:
Many real-world problems, for example resource allocation, can be formalized as soft constraint optimization problems. A fundamental issue is the compact and precise declaration of such problems. We propose Markov logic networks (MLNs), a representation formalism well-known from statistical relational learning, as a simple yet highly expressive modelling framework, for MLNs enable the representation of general principles that abstract away from concrete entities in order to achieve a separation between the model and the data to which it is applied. MLNs provide the full power of first-order logic and combine it with probabilistic semantics, thus allowing a flexible representation of soft constraints. We introduce an automatic conversion of maximum a posteriori (MAP) inference problems in MLNs to weighted constraint satisfaction problems to leverage a large body of available solving methods, and we make our software suite available to the public. We demonstrate the soundness of our approach on a real-world room allocation problem, providing experimental results.
Reference:
Markov Logic as a Modelling Language for Weighted Constraint Satisfaction Problems (D Jain, P Maier and G Wylezich), In Eighth International Workshop on Constraint Modelling and Reformulation, in conjunction with CP2009, 2009.
Bibtex Entry:
@inproceedings{jain_markov_2009,
author = {D Jain and P Maier and G Wylezich},
title = {Markov Logic as a Modelling Language for Weighted Constraint Satisfaction
Problems},
booktitle = {Eighth International Workshop on Constraint Modelling and Reformulation,
in conjunction with {CP2009}},
year = {2009},
abstract = {Many real-world problems, for example resource allocation, can be
formalized as soft constraint optimization problems. A fundamental
issue is the compact and precise declaration of such problems. We
propose Markov logic networks ({MLNs)}, a representation formalism
well-known from statistical relational learning, as a simple yet
highly expressive modelling framework, for {MLNs} enable the representation
of general principles that abstract away from concrete entities in
order to achieve a separation between the model and the data to which
it is applied. {MLNs} provide the full power of first-order logic
and combine it with probabilistic semantics, thus allowing a flexible
representation of soft constraints. We introduce an automatic conversion
of maximum a posteriori ({MAP)} inference problems in {MLNs} to weighted
constraint satisfaction problems to leverage a large body of available
solving methods, and we make our software suite available to the
public. We demonstrate the soundness of our approach on a real-world
room allocation problem, providing experimental results.},
}