The extended linear complementarity problem and its applications in analysis and control of discrete-event systems

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.