Total dual integrality and integral solutions of the linear complementarity problem

This paper deals with the problem of finding an integer solution to a linear complementarity problem (LCP). Chandrasekaran et al. [1] introduced the class I of integral matrices for which the corresponding LCP has an integer solution for every integral vector q, for which it has a solution and proved that for some well-known matrix classes principal unimodularity forms a necessary and sufficient condition for inclusion in the class I. In this paper, we identify some more well-known matrix classes for which principal unimodularity forms a necessary and sufficient condition for inclusion in the class I. The concept of total dual integrality is utilized to obtain a necessary and sufficient condition for existence of an integer solution to LCP with a hiddenK-matrix. We interconnect the concept of Hilbert basis with principal unimodularity of a matrix and the corresponding complementary cones. A necessary and sufficient condition is given for the existence of an integer solution of a linear fractional programming problem by using its LCP formulation.