A Petri Net Approach to Generate Integer Linear Programming Problems
Summary :
This paper proposes a Petri net based mathematical programming approach to combinatorial optimization, in which we generate integer linear programming problems from Petri net models instead of the direct mathematical formulation. We treat two types of combinatorial optimization problems, ordinary problems and time-dependent problems. Firstly, we present autonomous Petri net modeling for ordinary optimization problems, where we obtain fundamental constraints derived from Petri net properties and additional problem-specific ones. Secondly, we propose a colored timed Petri net modeling approach to time-dependent problems, where we generate variables and constraints for time management and for resolving conflicts. Our Petri net approach can drastically reduce the difficulty of the mathematical formulation in a sense that (1) the Petri net modeling does not require deep knowledge of mathematical programming and technique of integer linear model formulations, (2) our automatic formulation allows us to generate large size of integer linear programming problems, and (3) the Petri net modeling approach is flexible for input parameter changes of the original problem.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.2 pp.389-398
- Publication Date
- 2019/02/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E102.A.389
- Type of Manuscript
- Special Section PAPER (Special Section on Mathematical Systems Science and its Applications)
- Category
Authors
Morikazu NAKAMURA
University of the Ryukyus
Takeshi TENGAN
Meio University
Takeo YOSHIDA
University of the Ryukyus
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Morikazu NAKAMURA, Takeshi TENGAN, Takeo YOSHIDA, "A Petri Net Approach to Generate Integer Linear Programming Problems" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 2, pp. 389-398, February 2019, doi: 10.1587/transfun.E102.A.389.
Abstract: This paper proposes a Petri net based mathematical programming approach to combinatorial optimization, in which we generate integer linear programming problems from Petri net models instead of the direct mathematical formulation. We treat two types of combinatorial optimization problems, ordinary problems and time-dependent problems. Firstly, we present autonomous Petri net modeling for ordinary optimization problems, where we obtain fundamental constraints derived from Petri net properties and additional problem-specific ones. Secondly, we propose a colored timed Petri net modeling approach to time-dependent problems, where we generate variables and constraints for time management and for resolving conflicts. Our Petri net approach can drastically reduce the difficulty of the mathematical formulation in a sense that (1) the Petri net modeling does not require deep knowledge of mathematical programming and technique of integer linear model formulations, (2) our automatic formulation allows us to generate large size of integer linear programming problems, and (3) the Petri net modeling approach is flexible for input parameter changes of the original problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.389/_p
Copy
@ARTICLE{e102-a_2_389,
author={Morikazu NAKAMURA, Takeshi TENGAN, Takeo YOSHIDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Petri Net Approach to Generate Integer Linear Programming Problems},
year={2019},
volume={E102-A},
number={2},
pages={389-398},
abstract={This paper proposes a Petri net based mathematical programming approach to combinatorial optimization, in which we generate integer linear programming problems from Petri net models instead of the direct mathematical formulation. We treat two types of combinatorial optimization problems, ordinary problems and time-dependent problems. Firstly, we present autonomous Petri net modeling for ordinary optimization problems, where we obtain fundamental constraints derived from Petri net properties and additional problem-specific ones. Secondly, we propose a colored timed Petri net modeling approach to time-dependent problems, where we generate variables and constraints for time management and for resolving conflicts. Our Petri net approach can drastically reduce the difficulty of the mathematical formulation in a sense that (1) the Petri net modeling does not require deep knowledge of mathematical programming and technique of integer linear model formulations, (2) our automatic formulation allows us to generate large size of integer linear programming problems, and (3) the Petri net modeling approach is flexible for input parameter changes of the original problem.},
keywords={},
doi={10.1587/transfun.E102.A.389},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - A Petri Net Approach to Generate Integer Linear Programming Problems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 389
EP - 398
AU - Morikazu NAKAMURA
AU - Takeshi TENGAN
AU - Takeo YOSHIDA
PY - 2019
DO - 10.1587/transfun.E102.A.389
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2019
AB - This paper proposes a Petri net based mathematical programming approach to combinatorial optimization, in which we generate integer linear programming problems from Petri net models instead of the direct mathematical formulation. We treat two types of combinatorial optimization problems, ordinary problems and time-dependent problems. Firstly, we present autonomous Petri net modeling for ordinary optimization problems, where we obtain fundamental constraints derived from Petri net properties and additional problem-specific ones. Secondly, we propose a colored timed Petri net modeling approach to time-dependent problems, where we generate variables and constraints for time management and for resolving conflicts. Our Petri net approach can drastically reduce the difficulty of the mathematical formulation in a sense that (1) the Petri net modeling does not require deep knowledge of mathematical programming and technique of integer linear model formulations, (2) our automatic formulation allows us to generate large size of integer linear programming problems, and (3) the Petri net modeling approach is flexible for input parameter changes of the original problem.
ER -
English
