Computation of an emptiable minimal siphon in a subclass of Petri nets using mixed-integer programming

Shouguang Wang, Wenli Duo, Xin Guo, Xiaoning Jiang, Dan You, Kamel Barkaoui, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


Deadlock resolution strategies based on siphon control are widely investigated. Their computational efficiency largely depends on siphon computation. Mixed-integer programming MIP can be utilized for the computation of an emptiable siphon in a Petri net PN . Based on it, deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity. Due to this reason, various MIP methods are proposed for various subclasses of PNs. This work proposes an innovative MIP method to compute an emptiable minimal siphon EMS for a subclass of PNs named S4PR. In particular, many particular structural characteristics of EMS in S4PR are formalized as constraints, which greatly reduces the solution space. Experimental results show that the proposed MIP method has higher computational efficiency. Furthermore, the proposed method allows one to determine the liveness of an ordinary S4PR.

Original languageEnglish (US)
Article number9106877
Pages (from-to)219-226
Number of pages8
JournalIEEE/CAA Journal of Automatica Sinica
Issue number1
StatePublished - Jan 2021

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Artificial Intelligence
  • Information Systems
  • Control and Systems Engineering


Dive into the research topics of 'Computation of an emptiable minimal siphon in a subclass of Petri nets using mixed-integer programming'. Together they form a unique fingerprint.

Cite this