Max-plus-algebraic problems and the extended linear complementarity problem - algorithmic aspects

B. Schutter, de, W.P.M.H. Heemels, A. Bemporad

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 15th Triennial World Congress of the International Federation of Automatic Control(IFAC202), 21-26 June 2002, Barcelona, Spain
Number of pages6
Publication statusPublished - 2002
Event15th World Congress of the International Federation of Automatic Control, 2002 - Barcelona, Spain
Duration: 21 Jul 200226 Jul 2002
Conference number: 15

Conference

Conference15th World Congress of the International Federation of Automatic Control, 2002
Abbreviated titleIFAC 2002
CountrySpain
CityBarcelona
Period21/07/0226/07/02

Fingerprint Dive into the research topics of 'Max-plus-algebraic problems and the extended linear complementarity problem - algorithmic aspects'. Together they form a unique fingerprint.

  • Cite this

    Schutter, de, B., Heemels, W. P. M. H., & Bemporad, A. (2002). Max-plus-algebraic problems and the extended linear complementarity problem - algorithmic aspects. In Proceedings of the 15th Triennial World Congress of the International Federation of Automatic Control(IFAC202), 21-26 June 2002, Barcelona, Spain [728]