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.