General linear complementarity problems: algorithms and models

Linear complementarity problems (LCP) are usually NP-hard problems. The largest matrix class where the interior point algorithms (IPA) are polynomial is the class of P*(κ)-matrices, for given nonnegative real parameter κ. The union for all possible κ parameters of P*(κ)-matrices forms the class of P*-matrices. This class of matrices has been introduced by Kojima et al. in 1991. Cottle et al. (1989) defined the class of sufficient matrices (SU). It has been proved that several variants of the criss-cross algorithm are finite for LCPs with sufficient matrices. After all of these, it is a natural question: What is the relation between the sufficient and P*-matrices? Valiaho (1996) proved that the P*-matrices are exactly those which are sufficient. Using the concept of EP-theorem of Cameron and Edmonds (1990) and the LCP duality theorem of Fukuda and Terlaky (1992), Fukuda et al. (1998) were able to generalize the criss-cross algorithm for LCP problems with arbitrary matrices. The generalized criss-cross algorithm for LCPs with rational data stops in finite number of iterations with one of the following stopping criteria: (i) primal LCP has been solved and the encoding size of the solution has a polynomial bound, (ii) dual LCP has been solved and the encoding size of the solution has a polynomial bound, (iii) the matrix of the problem is not sufficient matrix and there is a certificate whose encoding size has a polynomial bound. Since 1998, it was an interesting open question whether the result of Fukuda et al. can be obtained using some generalization of IPAs or not? We modified some IPAs such that their stopping criteria are the same as those of the generalized criss-cross algorithm. The modified interior point algorithms running time is still polynomial, but does not give in all cases a solution for solvable LCPs [third stopping criterion, the matrix is not sufficient, but the LCP might have a solution]. Some of our interior point algorithms that solve LCPs with arbitrary matrices in the sense of the EPtheorem have been published. Goal of this talk is to introduce algorithms that may solve general LCPs and to show their computational performance on the well-known exchange market model of Arrow and Debreu.