TY - GEN
T1 - Petri net representation for 0-1 integer programming problems
AU - Kodama, Akito
AU - Nishi, Tatsushi
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - 0-1 integer programming problem
KW - discrete event systems
KW - optimal firing sequence problem
KW - Petri nets
KW - traveling salesman problem
KW - vehicle routing problems
UR - http://www.scopus.com/inward/record.url?scp=84988298068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84988298068&partnerID=8YFLogxK
U2 - 10.1109/IEEM.2014.7058734
DO - 10.1109/IEEM.2014.7058734
M3 - Conference contribution
AN - SCOPUS:84988298068
T3 - IEEE International Conference on Industrial Engineering and Engineering Management
SP - 729
EP - 733
BT - IEEM 2014 - 2014 IEEE International Conference on Industrial Engineering and Engineering Management
PB - IEEE Computer Society
T2 - 2014 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2014
Y2 - 9 December 2014 through 12 December 2014
ER -