Enumeration of all solutions of a combinatorial linear inequality system arising from the polyhedral homotopy continuation method

An interesting combinatorial (enumeration) problem arises in the initial phase of the polyhedral homotopy continuation method for computing all solutions of a polynomial equation system in complex variables. It is formulated as a problem of finding all solutions of a specially structured system of linear inequalities with a certain additional combinatorial condition. This paper presents a computational method for the problem fully utilizing the duality theory and the simplex method for linear programs, and reports numerical results on a single cpu implementation and a parallel cpu implementation of the method.