The sufficient matrix class was defined related to Linear complementarity problems. This is the widest class for which the criss-cross and the interior point algorithms (IPM) for solving LCPs are efficient in some sence. It is an NP-complete problem to decide whether a matrix belongs to this class. Therefore, we build a library of sufficient matrices to provide a test set for algorithms solving such LCPs. We show different techniques to generate such matrices. Furthermore, we present results about the handicap, which matrix parameter is important for the theoretical complexity of the IPM.
Linear Complementarity Problems (LCP) belong to the class of NP-complete problems. Darvay et al. (2018) showed that predictor-corrector (PC) interior point algorithms (IPA) using algebraic equivalent transformation (AET) solves sufficient LCPs in polynomial time. Our aim is to construct new PC IPAs based on AETs which in polynomial time either give an ε-optimal solution of the general LCP or detect the lack of sufficiency property. In the latter case, the algorithms give a polynomial size certificate depending on parameter κ, the initial interior point and the input size of the (LCP).
joint work with Janez Povh, Tibor Illés
In this talk we present new necessary and sufficient conditions for testing matrix sufficiency, which is an NP-hard problem. We discuss methods for testing matrix sufficiency based on the new characterizations and propose an algorithm with exponential complexity which in its kernel solves many simple instances of linear programming problems. Numerical results confirm relevance of this algorithm.