Enumeration-based approach to solving parametric linear complementarity problems

This paper presents a solution method for parametric linear complementarity problems (PLCP) that relies on an enumeration technique to discover all feasible bases. The enumeration procedure is based on evaluating all possible combinations of active constraints and testing for feasibility. Although the enumeration approach is known to grow exponentially in the number of constraints, the formulation of the PLCP allows incorporation of cheap rank tests to quickly prune the infeasible directions in the exploration. The motivation for the development of the enumeration based PLCP solver is that it represents a direct method to solve parametric linear and quadratic optimization problems as well as their mixed-integer counterparts. These types of problems often arise in the field of model predictive control for linear and hybrid systems. The enumeration based PLCP solver offers another alternative to compute explicit solutions in the field of hybrid model predictive control that can be extremely effective in some important cases.