Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908515611705344 |
|---|---|
| author | Jordon, Addie Kolčák, Juri Merkle, Daniel |
| author_facet | Jordon, Addie Kolčák, Juri Merkle, Daniel |
| contents | Petri nets provide accurate analogues to chemical reaction networks, with places representing individual molecules (the resources of the system) and transitions representing chemical reactions which convert educt molecules into product molecules. Their natural affinity for modeling chemical reaction networks is, however, impeded by their computational complexity, which is at least PSpace-hard for most interesting questions, including reachability. Continuous Petri nets offer the same structure and discrete time as discrete Petri nets, but use continuous state-space, which allows them to answer the reachability question in polynomial time. We exploit this property to introduce a polynomial time algorithm for computing the maximal yield of a molecule in a chemical system. Additionally, we provide an alternative algorithm based on mixed-integer linear programming with worse theoretical complexity, but better runtime in practice, as demonstrated on both synthetic and chemical data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02371 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches Jordon, Addie Kolčák, Juri Merkle, Daniel Discrete Mathematics Data Structures and Algorithms Petri nets provide accurate analogues to chemical reaction networks, with places representing individual molecules (the resources of the system) and transitions representing chemical reactions which convert educt molecules into product molecules. Their natural affinity for modeling chemical reaction networks is, however, impeded by their computational complexity, which is at least PSpace-hard for most interesting questions, including reachability. Continuous Petri nets offer the same structure and discrete time as discrete Petri nets, but use continuous state-space, which allows them to answer the reachability question in polynomial time. We exploit this property to introduce a polynomial time algorithm for computing the maximal yield of a molecule in a chemical system. Additionally, we provide an alternative algorithm based on mixed-integer linear programming with worse theoretical complexity, but better runtime in practice, as demonstrated on both synthetic and chemical data. |
| title | Continuous Petri Nets for Fast Yield Computation: Polynomial-Time and MILP Approaches |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.02371 |