Gradient-Based Variable Ordering of Decision Diagrams for Systems with Structural Units

This paper presents Gradient- \$\$\backslashvarPi \$\$ , a novel heuristics for finding the variable ordering of Decision Diagrams encoding the state space of Petri net systems. Gradient- \$\$\backslashvarPi \$\$ combines the structural informations of the Petri net (either the set of minimal P-semiflows or, when available, the structure of the net in terms of ``Nested Units'') with a gradient-based greedy strategy inspired by methods for matrix bandwidth reduction. The value of the proposed heuristics is assessed on a public benchmark of Petri net models, showing that Gradient- \$\$\backslashvarPi \$\$ can successfully exploit the structural information to produce good variable orderings.