|
MAX-PLUS-ALGEBRAIC PROBLEMS AND THE EXTENDED LINEAR COMPLEMENTARITY PROBLEM — ALGORITHMIC ASPECTS
B. De Schutter* W.P.M.H. Heemels** A. Bemporad***
* Control Systems Engineering, Fac. ITS, Delft University of
Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands,
b.deschutter@its.tudelft.nl
** Dept. of Electrical Eng., Eindhoven Univ. of Technology, P.O. Box
513, 5600 MB Eindhoven, The Netherlands,
w.p.m.h.heemels@tue.nl
*** Dip. Ingegneria dell’Informazione, Università di Siena, Via Roma
56, 53100 Siena, Italy, bemporad@dii.unisi.it &
Automatic Control Laboratory, Swiss Federal Institute of Technology,
ETH-Z, Physikstrasse 3, 8092 Zurich, Switzerland,
bemporad@aut.ee.ethz.ch
Many fundamental problems in the max-plus-algebraic system theory for discrete event systems — among which the minimal state space realization problem — can be solved using an Extended Linear Complementarity Problem (ELCP). We present some new, more efficient methods to solve the ELCP. We show that an ELCP with a bounded feasible set can be recast as a standard Linear Complementarity Problem (LCP). Our proof results in three possible numerical solution methods for a given ELCP: regular ELCP algorithms, mixed integer linear programming algorithms, and regular LCP algorithms. We also apply these three methods to a basic max-plus-algebraic benchmark problem.
Keywords: discrete event dynamic systems, optimization problems, complementarity problems, algorithms, mathematical programming
Session slot T-We-M02: Performance Issues in Discrete Event Systems/Area code 3c : Discrete Event Dynamic Systems
 |
