Implementation of a Solver for Parametric Linear Complementarity Problems for Model Predictive Control

Sebastiano Columbano, Diploma Thesis, Summer 2006

Supervisors: Dr. Colin Jones, Dr. Marco Laumanns, Rico Zenklusen

Model Predictive Control (MPC) is an effective paradigm for the control of constrained systems and currently the only advanced control methodology in widespread industrial use. It is standard practice to implement a model predictive controller by solving online an optimization problem where the decision variables provide the control action. In recent years, it has become well-known that the optimal input for a large class of systems is a piecewise affine function (PWA) defined over a polyhedral partition of the feasible states. By precomputing this PWA function off-line, the online calculation of the control input then becomes one of evaluating the PWA function at the current measured state, which allows for significant improvements in sampling speed.

The linear complementarity problem is a general problem that unifies linear and quadratic programs and bimatrix games. Recent work has shown that many useful model predictive controllers (MPC) can be posed as parametric linear complementarity problems (pLPC) and therefore the offline computation of the PWA control laws requires the solution to a pLCP. Furthermore, several fundamental problems such as polyhedral projection, parametric linear and quadratic programming and Minkowski addition of polytopes can be formulated as pLCPs.

A relatively new application of MPC is in supply chain management, where it can be used for controlling the flow of material through production/distribution networks. By regarding the demand (orders) of the end customers (sinks in the network) as external, random disturbances, we can formulate the so-called constrained robust optimal control problem, which can be solved by a combination of MPC and dynamic programming. Unfortunately, the specific structure of these supply network models often leads to highly degenerate pLPs. The availability of a pLPC solver that can handle degenerate problems without numerical problems will increase the applicability of this approach for realistic supply networks.

In this project a pLPC solver was implemented in C, together with a Matlab interface. The solver is being considerably faster than the one that has been used so far and can handle degenerate problems as the ones arising in the considered supply chain control problems. To increase the numerical stability of the implemented solver, an application of LU factorization in the pivot steps was proposed and implemented. Furthermore, the supply chain model was extended to allow the option of back-orders.