Integer solutions of system of linear inequalities and its aplication to find the extremes of linear and concave functions on the set of integer points of a finite convex polyhedron

Abstract

While the theory of system of linear inequalities has been well studied, the integer solution of
system of linear inequalities has not been properly investigated. One of the main reasons is that this
problem is very complicated and it is an NP-hard problem. In this paper we describe a polynomial time
algorithm for finding the integer solutions for a system of linear inequalities Ax ? b, where A is (r x n)
integer matrix of rank r. From this general case, we come to the algorithm for the paricular case, which
is to find a general formula for the integer points in convex cones defined by n linear inequalities. We
then propose the procedure of finding integer points in a finite convex polyhedron D, and then develop a
method for solving linear integer programming problem over a finite convex polyhedron D. Next, we
study the problem of minimizing a concave function on the set of integer points of a finite convex
polyhedron D. The problem of finding the minimum of a concave function on the set of integer points of
a finite convex polyhedron is a very difficult problem. As far as we know, there is currently no general
method to solve this problem. The algorithm proposed here is theoretical, difficult to apply to large
problems, except for some problems with special structures.