Reduction of Max-Plus Algebraic Equations to Constraint Satisfaction Problems for Mixed Integer Programming

Hiroyuki GOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.2   pp.427-430
Publication Date: 2017/02/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section LETTER (Special Section on Mathematical Systems Science and its Applications)
Category: 
Keyword: 
max-plus algebra,  linear constraint,  mixed integer programming,  constraint satisfaction problem,  scheduling,  

Full Text: PDF(90.4KB)
>>Buy this Article


Summary: 
This letter presents a method for solving several linear equations in max-plus algebra. The essential part of these equations is reduced to constraint satisfaction problems compatible with mixed integer programming. This method is flexible, compared with optimization methods, and suitable for scheduling of certain discrete event systems.