Factor Join Trees in Systems Exploration

Shahan Yang and John Baras

23rd International Conference on Software and Systems Engineering and their Applications (ICSSEA 2011)

Abstract:

The interaction of connected components creates
complexity impeding the analysis of large systems. Thorough
exploration, appearing as formal verification, optimization or
constraint satisfaction typically has a complexity that is either a
high order polynomial or an exponential function of system size.
However, for a large class of systems the essential complexity is
linear in system size and exponential in treewidth which makes
the previous notion of exponential complexity in system size an
accidental overestimate.
In this paper, we demonstrate how this reduced complexity
can be achieved using summary propagation on factor graphs. We
describe summary propagation in terms of operations belonging
to a commutative semiring-weighted relational algebra. We show
how by appropriate selection of the commutative semiring, the
same solution applies to propositional satisfiability, inference on
Bayesian networks and a mixed integer linear optimization problem
motivated by the power restoration problem for distributed,
autonomous networks. This solution leads to a non-iterative
distributed algorithm that operates on local data.
While weighted relational algebraic operators are used as the
basic means of calculation, the algorithm presented works only
on factor graphs that are trees. This requires the calculation
of a non-unique structure called a join tree, which can be
trivially generated from a unique structure called a cliqueseparator
graph, which can be computed in linear time from a
SysML Parametric Diagram description of the system for chordal
systems1. Interesting artifacts arise from this structural analysis
which may be interpreted as interfaces and components. The
framework also contains mathematical artifacts that may be
interpreted as hierarchy and abstraction.
We develop a tool to assist in the structural analysis described
and implementations of the described algorithms.