The Extended Linear Complementarity Problem and Its Applications in Analysis and Control of Discrete-Event Systems

Bart Schutter ()
Additional contact information
Bart Schutter: Delft University of Technology

A chapter in Pareto Optimality, Game Theory And Equilibria, 2008, pp 541-570 from Springer

Abstract: In this chapter, we give an overview of complementarity problems with a special focus on the extended linear complementarity problem (ELCP) and its applications in analysis and control of discrete-event systems such as traffic signal controlled intersections, manufacturing systems, railway networks, etc. We start by giving an introduction to the (regular) linear complementarity problem (LCP). Next, we discuss some extensions, with a particular emphasis on the ELCP, which can be considered to be the most general linear extension of the LCP. We then discuss some algorithms to compute one or all solutions of an ELCP. Next, we present a link between the ELCP and max-plus equations. This is then the basis for some applications of the ELCP in analysis and model-based predictive control of a special class of discrete-event systems. We also show that — although the general ELCP is NP-hard — the ELCP-based control problem can be transformed into a linear programming problem, which can be solved in polynomial time.

Keywords: linear complementarity problem; extended linear complementarity problem; algorithms; control applications; discrete-event systems; maxplus-linear systems (search for similar items in EconPapers)
Date: 2008
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-0-387-77247-9_21

Ordering information: This item can be ordered from
http://www.springer.com/9780387772479

DOI: 10.1007/978-0-387-77247-9_21

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().