Generalized Linear Complementarity Problems as Linear Programs

Abstract

A generalized linear complementarity problem which is equivalent to finding a root of a piecewise-linear system of equations is shown to be solvable if and only if a related linear programming problem is solvable. Furthermore, each solution of the linear programming problem solves the generalized linear complementarity problem and is a root of the equivalent piecewise-linear system of equations.