Petri net representation for 0-1 integer programming problems
Akito Kodama, Tatsushi Nishi · 2014
Petri net is a mathematical modeling tool that represents wide variety of discrete event systems. Given an initial marking and final marking for a Petri net, an optimal firing sequence problem is defined as the problem to And an optimal transition sequence to minimize the objective function. For the purpose of analysis of 0-1 integer programming problems, we propose a general algorithm to convert general 0-1 integer programming problem into an optimal firing sequence problem of Petri net. By utilizing the proposed algorithm, general 0-1 integer programming problems can be visualized and analyzed by Petri net theory. The property of solutions derived by solving the original 0-1 integer programming and the optimal firing sequence problem is discussed. The solution of 0-1 integer programming problem and that of the optimal firing sequence problem of Petri net are compared. The results show that the solutions for both problems are identical for traveling salesman problem and vehicle routing problems.