An Implicit Enumeration Procedure for the General Linear Complementarity Problem,
GEORGIA INST OF TECH ATLANTA PRODUCTION AND DISTRIBUTION RESEARCH CENTER
Pagination or Media Count:
An algorithm is presented for solving a quadratic programming formulation of the linear complementarity problem. No assumptions on the problem data are required. The algorithm is designed to solve the problem by implicitly enumerating the 2 superscript n complementary cones. Geometrically, the procedure amounts to searching the extreme points of a sequence of faces of the constraint polyhedron of decreasing dimension. An extension to the procedure for finding all solutions of an arbitrary complementarity problem is also discussed. The procedure has been implemented and tested on forty randomly generated problems up to fifty dimensional having dense indefinite defining matrices. The results of these tests demonstrate the superiority of this approach over two competing methods.
- Theoretical Mathematics