Integer programming applied to rule based systems

Abstract

Abstract. In this paper we show how to represent a set of logic propositions as an integer linear program and how to use its solution to determine the truth value of all the proposition given only a subset of their truth values. Thus a rule–based expert system might use this approach as inference engine. When we model an expert system knowledge base as an integer linear program, we can ask for what is a minimum set of premises needed in order to have an specific conclusion as true. Furthermore we can ask for what propositions become true once a subset of propositions are known to be true. Once the integer restriction is dismissed, we can ask for what conditions are necessary in order that a conclusion holds with certain probability. Thus we can have both a deterministic and stochastic model using practically the same paradigm.

Resumen. En este artículo mostramos cómo representar un conjunto de proposiciones lógicas como un programa lineal entero y cómo usar su solución para determinar el valor de verdad de todas las proposiciones dado solo un subconjunto de sus valores de verdad. Por tanto, un sistema experto basado en reglas podría utilizar este enfoque como motor de inferencia. Cuando modelamos una base de conocimientos de un sistema experto como un programa lineal entero, podemos preguntar cuál es el conjunto mínimo de premisas necesarias para tener una conclusión específica como verdadera. Además, podemos preguntar qué proposiciones se vuelven verdaderas una vez que se sabe que un subconjunto de proposiciones es verdadera. Una vez descartada la restricción de enteros, podemos preguntar qué condiciones son necesarias para que una conclusión se cumpla con cierta probabilidad. Por tanto, podemos tener un modelo tanto determinista como estocástico utilizando prácticamente el mismo paradigma.