Reference
B. De Schutter, "The extended linear complementarity problem and its
applications in analysis and control of discrete-event systems," in
Pareto Optimality, Game Theory and Equilibria (A.
Chinchuluun,
P. M. Pardalos, A. Migdalas,
and L. Pitsoulis, eds.), vol. 17 of
Springer Optimization and
Its Applications, New York, New York: Springer, ISBN 978-0-387-77246-2,
pp. 541-570, 2008.
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.
Publisher page
Downloads
BibTeX
@incollection{DeS:07-010,
author = {De Schutter, Bart},
title = {The Extended Linear Complementarity Problem and Its
Applications in Analysis and Control of Discrete-Event
Systems},
booktitle = {Pareto Optimality, Game Theory and Equilibria},
series = {Springer Optimization and Its Applications},
volume = {17},
editor = {Chinchuluun, Altannar and Pardalos, Panos M. and Migdalas,
Athanasios and Pitsoulis, Leonidas},
publisher = {Springer},
address = {New York, New York},
pages = {541--570},
year = {2008}
}