Characterizing Boundedness and Solution Size in Rational Linear Programming and Polyhedrall Optimization

Abstract

This paper investigates the boundedness conditions and solution size constraints in rational linear programming (LP) and polyhedral optimization. We establish necessary and sufficient conditions under which the optimization of linear functions over rational polyhedral remains bounded and derive explicit bounds on the numerical size of optimal solutions, when they exist. Central to our analysis is the equivalence of boundedness between a rational polyhedron and its integer hull, providing new insights into the structure of feasible regions. We also present size bounds for solutions in terms of the bit-length of rational data, demonstrating how these results impact the complexity and numerical stability of LP solvers. The theoretical framework builds upon polyhedral geometry, sub-determinants, and the properties of rational systems, and is supported by rigorous proofs. Applications are explored in mixed-integer programming, convex hull computation, and production scheduling, where our results enhance both theoretical understanding and computational efficiency. These findings contribute to the deeper interplay between discrete and continuous optimization, offering valuable implications for algorithm design and numerical analysis.