Variable ordering heuristics for BDD based on minimal cutsets

Abstract

The Binary Decision Diagram technology is a good alternative to the classical minimal cutsets approach to assess Fault Trees and Event Trees issued from Probabilistic Safety Assessment studies of the nuclear industry. A key issue in the efficiency of this technique stands in the choice of a good variable ordering. In this article, we explore a new idea for the design of ordering heuristics: the use of minimal cutsets calculated with a classical algorithm in order to group variables. We propose several ordering heuristics to be applied on a sum-of-products. We discuss whether these heuristics could be extended to general formulae.

The Binary Decision Diagram technology is a good alternative to the classical minimal cutsets approach to assess Fault Trees and Event Trees issued from Probabilistic Safety Assessment studies of the nuclear industry. A key issue in the efficiency of this technique stands in the choice of a good variable ordering. In this article, we explore a new idea for the design of ordering heuristics: the use of minimal cutsets calculated with a classical algorithm in order to group variables. We propose several ordering heuristics to be applied on a sum-of-products. We discuss whether these heuristics could be extended to general formulae.