INTEGER SOLUTION FOR LINEAR COMPLEMENTARITY-PROBLEM

We consider the problem of finding an integer solution to a linear com plementarity problem. We introduce the class I of matrices for which t he corresponding linear complementarity problem has an integer complem entary solution for every vector, q, for which it has a solution. Stro ng principal unimodularity forms a sufficient condition for inclusion in the class I. It is also shown to be necessary for some well-known c lasses of matrices, including the class of positive semidefinite matri ces. This is used in deriving necessary and sufficient conditions for a convex quadratic program to have an integer optimal solution for all b and c for which it has an optimal solution. Characterizations are a lso derived for some other well-known classes of matrices in linear co mplementarity to belong to the class I. In the end, a peeling algorith m for finding integer solution for linear complementarity problems is given and related results are derived.