This paper presents a polynomial-time algorithm for solving the integer linear programming problem with a fixed number of variables. The problem is to determine whether there exists a vector $ x \in \mathbb{Z}^n $ satisfying the system $ Ax \leq b $, where $ A $ is an $ m \times n $ matrix with integer coefficients and $ b \in \mathbb{Z}^m $. The algorithm is based on methods from the geometry of numbers and is shown to be polynomial in the length of the input data, which is defined as $ n \cdot m \cdot \log(a + 2) $, where $ a $ is the maximum absolute value of the coefficients of $ A $ and $ b $.
The algorithm is described in several sections. Section 1 outlines the algorithm, which involves transforming the problem into an equivalent one with certain properties. Section 2 describes an algorithm to verify the conditions of the problem and construct the transformation. Section 3 presents a reduction process for n-dimensional lattices, which is used to simplify the problem. Section 4 shows that the integer linear programming problem with a fixed number of constraints is also polynomially solvable. Section 5 discusses the mixed integer linear programming problem, which is shown to be polynomially solvable for any fixed number of integer variables.
The algorithm is designed for theoretical purposes and may not be optimal for practical use. It is expected to be effective only for small values of $ n $. The paper also discusses the implications of the results for related problems and references several key results in the field of integer programming and computational complexity.This paper presents a polynomial-time algorithm for solving the integer linear programming problem with a fixed number of variables. The problem is to determine whether there exists a vector $ x \in \mathbb{Z}^n $ satisfying the system $ Ax \leq b $, where $ A $ is an $ m \times n $ matrix with integer coefficients and $ b \in \mathbb{Z}^m $. The algorithm is based on methods from the geometry of numbers and is shown to be polynomial in the length of the input data, which is defined as $ n \cdot m \cdot \log(a + 2) $, where $ a $ is the maximum absolute value of the coefficients of $ A $ and $ b $.
The algorithm is described in several sections. Section 1 outlines the algorithm, which involves transforming the problem into an equivalent one with certain properties. Section 2 describes an algorithm to verify the conditions of the problem and construct the transformation. Section 3 presents a reduction process for n-dimensional lattices, which is used to simplify the problem. Section 4 shows that the integer linear programming problem with a fixed number of constraints is also polynomially solvable. Section 5 discusses the mixed integer linear programming problem, which is shown to be polynomially solvable for any fixed number of integer variables.
The algorithm is designed for theoretical purposes and may not be optimal for practical use. It is expected to be effective only for small values of $ n $. The paper also discusses the implications of the results for related problems and references several key results in the field of integer programming and computational complexity.