Incremental Integer Linear Programming Models for Petri Nets Reachability Problems
Thomas Bourdeaud’huy, Saïd Hanafi, Pascal Yim · 2008
In this chapter, we present techniques for solving reachability problems in PN and TPN based on mathematical programming. The approach is based on an incremental search using step sequences that represent parallel and reentrant firings of transitions. The mathematical model used allows the formulation and verification of reachability-based analysis problems. Concerning PNs, we have proposed two formulations of the reachability problem, leading to integer and/or binary programming models. For each of them, we have developped some additional procedures, relaxation techniques and objective functions in order to improve the computational efficiency of the resolution. Numerical experiments have demonstrated the efficiency of our approach compared to standard ones from Artificial Intelligence and Petri nets community. Several promising tracks will be considered in the future, such that: ? To develop rules to adjust dynamically the amplitudes of jump search, for example by exploiting information from the previous iterations and/or from the structure of the considered PN; ? To use heuristic methods to speed up the search or find a good bound on