Direct Minimal Empty Siphon Computation Using MIP

Abstract

We propose a revised mixed-integer programming (MIP) method to directly compute unmarked siphons with a minimal number of places. This eliminates the need to deduce a minimal siphon from an unmarked maximal siphon obtained from the traditional MIP method proposed by Chu et al. The revised MIP test reports smaller siphons earlier than larger siphons and adds monitors to basic siphons before compound siphons. This results in adding fewer monitors and reaching more states.