Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 60 On Boundedness and Solution Size in Rational Linear Programming and Polyhedral Optimization Mark Laisin, Collins Edike & R. N. Ujumadu Abstract This paper delves into the theoretical and practical aspects of boundedness and structural properties in rational linear programming (LP) and polyhedral optimization. It provides a comprehensive analysis of conditions under which the optimization of linear functions over rational polyhedra remains bounded and establishes explicit constraints on solution size when optimal solutions exist. By exploring the interplay between polyhedral geometry, integer hulls, and rational LP systems, this study sheds light on fundamental principles that underlie modern optimization techniques. Key findings include equivalence conditions for boundedness between rational polyhedra and their integer hulls, as well as precise bounds on the numerical representation of optimal solutions. These results not only enhance the theoretical understanding of LP and polyhedral optimization but also have significant implications for computational efficiency, algorithm design, and numerical stability in solving real-world optimization problems. The discussion is rooted in rigorous mathematical foundations and extends to practical applications in areas such as mixed-integer programming, computational geometry, and combinatorial optimization. Keywords: rational linear programming, polyhedral optimization, boundedness conditions, integer hull, solution size bounds, rational coefficients, computational geometry, optimization algorithms, numerical stability. I. Introduction Linear programming (LP) has had a significant and enduring influence, deeply connected with the evolution of optimization theory and computational methodologies. Scholars have extensively traced the origins of LP back to the 1930s, highlighting Leonid Kantorovich’s groundbreaking work in formulating optimization problems to address resource allocation challenges in economic planning (Kantorovich, 1939). Kantorovich’s pioneering contributions established the foundation of linear optimization and Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 61 were later recognized with the Nobel Prize in Economics, underscoring the lasting impact of his work. The practical relevance of LP has surged during and after World War II. Researchers, notably George Dantzig, have developed the simplex algorithm to optimize military logistics and supply chains, a milestone in the application of mathematical optimization (Dantzig, 1947). The simplex algorithm has remained a cornerstone in solving LP problems, celebrated for its practical efficiency and ease of implementation, despite its potential exponential time complexity in the worst-case scenarios. The study of rational linear programming, characterized by constraints and objectives expressed using rational coefficients, has gained prominence with advancements in computational methodologies. Researchers have extensively analyzed rational LP systems, focusing on their numerical properties, solution size, and computational feasibility. During the 1980s, Karmarkar’s introduction of the polynomial-time interior-point method has revolutionized the field, providing an alternative to the simplex algorithm and emphasizing the significance of numerical stability in optimization (Karmarkar, 1984). Polyhedral optimization, a core area of mathematical optimization, has bridged critical concepts in combinatorics, geometry, and optimization. Scholars have explored the geometric properties of feasible regions defined by linear inequalities, offering theoretical and practical insights for solving complex problems. The study of polyhedra has uncovered deep structural relationships essential for various optimization tasks, including vertex enumeration and facet identification. Among the impactful concepts in polyhedral optimization is the integer hull, representing the convex hull of all integer solutions within a polyhedron. This concept has substantially advanced the theory and algorithms of integer programming and mixed-integer programming, as emphasized by Nemhauser and Wolsey (1999). By enabling the transition from an infinite search space to a finite and structured geometric framework, the integer hull has simplified the analysis of discrete variable problems. Recent advancements in polyhedral optimization include the construction and analysis of rational polyhedra on boards. Laisin et al. (2024) have demonstrated the practical effectiveness of polyhedral techniques in modeling and solving problems involving integral polyhedra, offering applications in combinatorial optimization and computational geometry. Their work has exemplified how modern techniques can address both theoretical challenges and real-world applications. This paper examines two fundamental aspects of rational LP and polyhedral Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 62 optimization: i. Conditions under which the optimization of a linear function over a rational polyhedron is bounded. ii. Bounds on the size of optimal solutions. Building on classical results from Schrijver (1998) and others, the analysis provides refined bounds and structural insights critical for advancing both theoretical understanding and practical applications in optimization. II. Preliminaries and Definitions Definition 2.1: Sub-determinant Let 𝑨 be an integral matrix. A sub-determinant of 𝑨 is |𝑩| for some square sub-matrix 𝑩 of 𝑨 (defined by arbitrary row and column indices). We write𝚡(𝑨) for the maximum absolute value of the sub-determinants of 𝑨. Definition 2.2: Polyhedron Linear Programming deals with optimizing a linear objective function of finitely many variables subject to finitely many linear inequalities. So the set of feasible solutions is the intersection of finitely many half spaces. Such a set is called a polyhedron. Definition 2.3: Polyhedron in ℝ𝒏 It is a set of type 𝑷 = {𝒙 ∈ ℝ𝒏: 𝑨𝒙 ≀ 𝒃} for some matrix 𝑨 ∈ β„π’ŽΓ—π’and some vector 𝒃 ∈ β„π’Ž. If A and b are rational, then P is a rational polyhedron. A bounded polyhedron is also called a polytope. We denote the rank of a matrix A by π’“π’‚π’π’Œ(𝑨). The dimension dim X of a nonempty set: 𝒙 βŠ† ℝ𝒏 is defined to be 𝒏 βˆ’ 𝐦𝐚𝐱 π’“π’‚π’π’Œ(𝑨) {π’“π’‚π’π’Œ(𝑨): 𝑨 𝐒𝐬 𝐚𝐧 𝒏 Γ— 𝒏 βˆ’ 𝐦𝐚𝐭𝐫𝐒𝐱 𝐰𝐒𝐭𝐑 𝑨𝒙 = π‘¨π’š 𝐟𝐨𝐫 𝐚π₯π₯ 𝒙, π’š ∈ 𝑿} A polyhedron 𝑷 βŠ† ℝ𝒏 is called full-dimensional if 𝐝𝐒𝐦 𝑷 = 𝒏 Equivalently, a polyhedron is full-dimensional if and only if there exist a point π’™βˆ— in its interior. (Genova and Guliashki, 2011). Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 63 Proposition 2.1: Nonempty polyhedron: Let 𝑃 = {π‘₯ ∢ 𝐴π‘₯ ≀ 𝑏} be a nonempty polyhedron. If c is a nonzero vector for which 𝜹 ∢= 𝐦𝐚𝐱 {𝒄𝒙 ∢ 𝒙 ∈ 𝑷} is finite, then {𝒄𝒙 ∢ 𝒙 = 𝜹} is called a supporting hyperplane of P. A face of P is P itself or the intersection of P with a supporting hyperplane of P. A point x for which {x} is a face is called a vertex of P, and also a basic solution of the system 𝑨𝒙 ≀ 𝒃 (Genova and Guliashki, 2011). Proposition 2.2: Let 𝑃 ∢= {π‘₯ ∢ 𝐴π‘₯ ≀ 𝑏} be a polyhedron and 𝑭 βŠ† 𝑷. Then the following statements are equivalent: (a) F is a face of P. (b) There exists a vector c such that 𝜹 ∢= 𝐦𝐚𝐱 {𝒄𝒙 ∢ 𝒙 ∈ 𝑷} is finite and 𝑭 = {𝒄𝒙 = 𝜹 ∢ 𝒙 ∈ 𝑷} (c) 𝑭 ∢= {𝒙 ∈ 𝑷: 𝑨′𝒙 = 𝒃′} β‰  βˆ…; for some subsystem 𝑨′𝒙 ≀ 𝒃′ of 𝑨𝒙 ≀ 𝒃 (Genova and Guliashki, 2011). Corollary 2.1: Let 𝑃 be a polyhedron and 𝐹 a face of 𝑃. Then 𝐹 is again a polyhedron. Furthermore, a set 𝐹′ βŠ† 𝐹 is a face of 𝑃 if and only if it is a face of 𝐹 (Genova and Guliashki, 2011). Proposition 2.3: Let 𝑷 = {𝒙: 𝑨𝒙 ≀ 𝒃} be a polyhedron. A nonempty subset 𝑭 βŠ† 𝑷 is a minimal face of 𝑷 if and only if it is a face of; 𝑭 = {𝒙: 𝑨′𝒙 = 𝒃′} for some subsystem 𝑨′𝒙 ≀ 𝒃′ of 𝑨𝒙 ≀ 𝒃 (Akif and Cihan, 2008) Proposition 2.4: For any rational square matrix A we have 𝑠𝑖𝑧𝑒 𝑑𝑒𝑑 𝐴 ≀ 2𝑠𝑖𝑧𝑒(𝐴) Proposition 2.5: If 𝒙, π’š ∈ β„šπ’ are rational vectors, then π’”π’Šπ’›π’†(𝒙 + π’š) ≀ 𝟐(π’”π’Šπ’›π’†(𝒙) + π’”π’Šπ’›π’†(π’š)) π’”π’Šπ’›π’†(π’™π‘»π’š) ≀ 𝟐(π’”π’Šπ’›π’†(𝒙) + π’”π’Šπ’›π’†(π’š))(π‹πšπ’π¬π’π§ 𝒆𝒕 𝒂𝒍. , πŸπŸŽπŸπŸ’). Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 64 Definition 2.4: Integer programming problem (IPP) The IPP is a special class of linear programming problem (LPP) where all or some of the variables in the optimal solution are restricted to assume non- negative-integer values. Thus the general IPP can be stated as follows: Optimize the linear function 𝐎𝐩𝐭𝐒𝐦𝐒𝐳𝐞 𝒁 = βˆ‘ π’„π’Šπ’™π’Š 𝒏 π’Š=𝟏 … (𝟏) Subject to the constraints. βˆ‘ π’‚π’Šπ’‹π’™π’Š 𝒏 π’Š=𝟏 ≀ π’ƒπ’Š, 𝒋 = 𝟏, 𝟐, … , π’Ž … (𝟐) π’™π’Š β‰₯ 𝟎 and some π’™π’Š are integers. There are two types of the Integer Programming Problems (Elmuti, 2003; Genova and Guliashki, 2011). Definition 2.5: All integer programming problem An IPP. is termed as all IPP or pure IPP if all the variables in the optimal solution are restricted to assume non-negative integer values. Definition 2.6: Mixed integer programming problem (MIPP) An IPP is termed as mixed MIPP if only some variables in the optimal solution are restricted to assume non-negative integer values while the remaining variables are free to take any non-negative values (Gupta et al., 2014). Importance of IPP Quite often, in business and industry, we require the discrete nature or values of the variables involved in many decision making situations. For example, in a factory manufacturing trucks or cars etc. the quantity or number manufactured can be a whole discrete number only as a fraction of truck or car is not required. In assignment problems and travelling salesman problems etc. the variables involved can assume integer values only. In allocation of goods, a shipment must involve a discrete number of trucks etc. in sequencing and routing decisions we require the discrete values of variables. Thus we come across many integer programming problems and hence need some systematic procedure for obtaining the exact optimal integer solution to such problems (Elmuti, 2003; Genova and Guliashki, 2011). Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 65 III. Main Results Lemma: (Boundedness equivalence) Let 𝑷 = {𝒙: 𝑨𝒙 ≀ 𝒃} be some rational polyhedron whose integer hull is nonempty, and let 𝒄 be some vector (not necessarily rational). Then 𝐦𝐚𝐱 {𝒄𝒙: 𝒙 ∈ 𝑷} is bounded if and only if 𝐦𝐚𝐱 {𝒄𝒙: 𝒙 ∈ π‘·πŸ} is bounded. Proof: Suppose 𝐦𝐚𝐱 {𝒄𝒙: 𝒙 ∈ 𝑷}is unbounded. Then Corollary 3.2.8 says that the system π’šπ‘¨ = 𝒄. π’š β‰₯ 𝟎 has no solution. By Corollary 3.26 there is a vector 𝒛. With 𝒆𝒛 < 0 and 𝑨𝒛 β‰₯ 𝟎. Then the 𝑳𝑷 𝐦𝐒𝐧 {𝒄𝒛: 𝑨𝒛 β‰₯ 𝟎, βˆ’βˆ₯≀ 𝒛 ≀βˆ₯} is feasible. Let π’›βˆ— be an optimum basic solution of this 𝑳𝑷. π’›βˆ— is rational as it is a vertex of a rational polytope. Multiply π’›βˆ— by a suitable natural number to obtain an integral vector 𝝎 with π‘¨πŽ β‰₯ 𝟎 and π’„πŽ < 0. Let 𝒗 ∈ π‘·πŸ be some integer vector. Then 𝒗 βˆ’ π’ŒπŽ ∈ π‘·πŸ for all π’Œ ∈ β„•, and thus 𝐦𝐚𝐱 {𝒄𝒙: 𝒙 ∈ π‘·πŸ} is unbounded. The other direction is trivial. Theorem (Rational matrices and vertices of polytopes) Consider the rational linear programming (LP) problem: 𝑳𝑷: π’Žπ’‚π’™ {𝒄𝑻𝒙: 𝑨𝒙 ≀ 𝒃} where A and b are rational. Suppose this LP has an optimum solution. Then the following hold: (i) Bounded Size Solution: There exists an optimum solution x such that: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)) (ii) Special Case (Unit Vector b): If 𝒃 = π’†π’Š 𝒐𝒓 𝒃 = βˆ’π’†π’Š for some unit vector π’†π’Š there exists a nonsingular submatrix 𝑨′ of A and an optimum solution x such that: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)) with each component of x satisfying: π’”π’Šπ’›π’†(π’„π’π’Žπ’‘π’π’π’†π’π’• 𝒐𝒇 𝒙) ≀ πŸ’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)) Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 66 (iii) Reduced Submatrix Case: If 𝒃 = π’†π’Š 𝒐𝒓 𝒃 = βˆ’π’†π’Š for some unit vector π’†π’Š , then there exists a non-singular submatrix 𝑨′ of A and an optimum solution x such that: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’ β‹… π’”π’Šπ’›π’†(𝑨′) Proof The proof of Theorem 4.3 relies on these definitions 2.1, 2.2, 2.3, 2.4 and 2.5 respectively, to analyse the structure and properties of the LP problem. Task 1: to show that, for a given LP, there exists a Solution with Bounded Size. By the fundamental theorem of linear programming, there exists an optimum solution π’™βˆ— at a vertex of the feasible polytope {𝒙: 𝑨𝒙 ≀ 𝒃}. o Vertex Characterization: A vertex π’™βˆ— corresponds to a subset of constraints in 𝑨𝒙 ≀ 𝒃 that are active (i.e., satisfied as equalities). By Corollary 2.1. the maximum is attained in a face 𝑭 of {𝒙 ∢ 𝑨𝒙 ≀ 𝒃}. Let 𝑰 βŠ† {𝟏, 𝟐, … , π’Ž} denote the indices of active constraints, and let 𝑨𝑰 denote the submatrix of A corresponding to these constraints. At a vertex, the system can be written as: 𝑨𝑰𝒙 = 𝒃𝑰 where 𝒃𝑰is the corresponding sub vector of b. o Non-Singularity of 𝑨𝑰: For π’™βˆ— to be a vertex, the matrix 𝑨𝑰 must be non-singular (invertible), and ∣ 𝑰 ∣= 𝒏. o Size of Solution: Solving 𝑨𝑰𝒙 = 𝒃𝑰 𝒙 = 𝑨𝑰 βˆ’πŸπ’ƒπ‘° Using bounds on the size of 𝑨𝑰 and 𝒃𝑰, and the fact that 𝑨𝑰 is rational, the entries of are bounded in terms of π’”π’Šπ’›π’†(𝑨𝑰). Specifically, the size of x is bounded by: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)). Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 67 Task 2: to show that for a give LP has a Special Case (𝒃 = π’†π’Š 𝒐𝒓 𝒃 = βˆ’π’†π’Š ) If 𝒃 = π’†π’Š 𝒐𝒓 𝒃 = βˆ’π’†π’Š , whereπ’†π’Š is a unit vector, the LP corresponds to finding the maximum value of 𝒄𝑻𝒙 along a specific axis defined by π’†π’Š. o Existence of a Non-singular Submatrix: As in task 1, there exists a vertex solution π’™βˆ—, and the active constraints correspond to a nonsingular submatrix 𝑨′ of A. o Bound on Solution Size: Similar to the general case, the size of x is bounded by: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)), with the size of each component of x further bounded by: π’”π’Šπ’›π’†(π’„π’π’Žπ’‘π’π’π’†π’π’• 𝒐𝒇 𝒙) ≀ πŸ’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)). Task 3: to show that for a give LP has reduced submatrix: Let 𝑭′ βŠ† 𝑭 be a minimal face. By corollary 2.1𝑭′ = {𝒙 ∢ 𝑨′𝒙 = 𝒃′} for some subsystem 𝑨′𝒙 ≀ 𝒃′ 𝐨𝐟 𝑨𝒙 ≀ 𝒃. Then, in the special case where 𝒃 = π’†π’Š 𝒐𝒓 𝒃 = βˆ’π’†π’Š , let 𝑨′ denote the nonsingular submatrix corresponding to the active constraints at the optimum. Now, we may assume that the rows of 𝑨′ are linearly independent. We then take a maximal set of linear independent columns (call this matrix 𝑨”) and set all other components to zero. Then 𝒙 = (𝑨")βˆ’πŸπ’ƒβ€², filled up with zeros, is an optimum solution to our LP. By Cramer’s rule the entries of 𝒙 are given by π’™π’Š = 𝐝𝐞𝐭 𝑨′′′ 𝐝𝐞𝐭 𝑨′′ , where 𝑨′′′ arises from 𝑨′′ by replacing the 𝒋 βˆ’ 𝒕𝒉 column by 𝒃′. By propositions 2.4 and 2.5 respectively, we obtain π’”π’Šπ’›π’†(𝒙) ≀ 𝒏 + πŸπ’(π’”π’Šπ’›π’†(𝑨′′′) + π’”π’Šπ’›π’†(𝑨′′)) ≀ πŸ’π’(π’”π’Šπ’›π’†(𝑨′′) + π’”π’Šπ’›π’†(𝒃′)). If 𝒃 = Β±π’†π’Š then | 𝐝𝐞𝐭(𝑨′′′) | is the absolute value of a sub determinant of 𝑨′′. The size of x can then be further bounded as: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’ β‹… π’”π’Šπ’›π’†(𝑨′). This follows because 𝑨′ has fewer rows and columns compared to the full matrix A, reducing the maximum size contribution. Q.E.D. Utilizing results from Schrijver (1998) and Cook et al., (1986), we derive Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 68 bounds on the size of optimal solutions by analyzing the bit-length of vertices of and properties of rational systems. IV. Applications: Production Scheduling Problem i) Integer Programming: The equivalence of boundedness conditions simplifies complexity analyses for mixed-integer programming problems Problem Setup A factory produces two products, A and B, using two resources, labor and material. The available resources are limited to 100 hours of labor and 80 units of material. The profit for producing one unit of A is $50, and for B, it's $40. The problem is to determine the production quantities π’™πŸ (units of A) and π’™πŸ (units of B) to maximize profit, subject to the following constraints: Labor constraint: πŸπ’™πŸ + πŸπ’™πŸ ≀ 𝟏𝟎𝟎, Material constraint: πŸπ’™πŸ + πŸπ’™πŸ ≀ πŸ–πŸŽ. This is a linear programming (LP) problem. However, if the production quantities π’™πŸ and π’™πŸ must be integers (e.g., you cannot produce fractional units), the problem becomes a mixed-integer programming (MIP) problem. Rational Polyhedron and Integer Hull ο‚· The feasible region defined by the constraints is a rational polyhedron P, containing all real-valued solutions that satisfy the constraints. ο‚· The integer hull 𝑷𝑰 is the convex hull of all integer solutions within P. It represents the feasible region for the MIP problem. Boundedness Analysis 1. Boundedness of P: The polyhedron P is bounded since it is enclosed by the constraints πŸπ’™πŸ + πŸπ’™πŸ ≀ 𝟏𝟎𝟎 and π’™πŸ + πŸπ’™πŸ ≀ πŸ–πŸŽ, which intersect in the positive quadrant. 2. Boundedness of 𝑷𝑰: The integer hull 𝑷𝑰, being a subset of P, is also bounded. This follows from the equivalence of boundedness conditions: if π’Žπ’‚π’™ {𝒄𝑻𝒙: 𝒙 ∈ 𝑷} is bounded, then π’Žπ’‚π’™ {𝒄𝑻𝒙: 𝒙 ∈ 𝑷𝑰, } is bounded. Simplifying the Analysis Instead of analyzing the MIP problem directly, the equivalence of boundedness conditions allows us to focus on the polyhedron P to verify boundedness. Once P is confirmed to be bounded, we can conclude that 𝑷𝑰, Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 69 is bounded, avoiding the need for exhaustive checks over all integer solutions. Solving the Problem The integer solutions can then be obtained by applying integer programming techniques, such as branch-and-bound or cutting planes, which operate within the bounded integer hull 𝑷𝑰, . Thus, reducing the boundedness check to P, the analysis simplifies significantly, saving computational effort and making the problem more tractable. ii) Computational Geometry: Solution size bounds assist in designing efficient algorithms for convex hull and vertex enumeration. Application Context Consider the problem of computing the convex hull of a set of points in ℝ𝒏. Convex hull algorithms, such as QuickHull or Graham's scan, rely on numerical representations of the points and may involve large computations when the coordinates of the points have a high bit-length. Efficient algorithms benefit from guarantees about the size of intermediate and final solutions, which directly impacts computation time and memory usage. Problem Setup Let 𝑷 = {𝒙 ∈ ℝ𝒏: 𝑨𝒙 ≀ 𝒃} be a rational polyhedron defined by m linear inequalities, where 𝑨 ∈ β„šπ’ŽΓ—π’. The goal is to compute the convex hull of the integer points in P, denoted 𝒄𝒐𝒏𝒗(𝑷𝑰). Solution Size Bounds From theoretical results, if an optimal solution x to a linear program over P exists, its size is bounded as: π’”π’Šπ’›π’†(𝒙) ≀ πŸ’π’(π’”π’Šπ’›π’†(𝑨) + π’”π’Šπ’›π’†(𝒃)). This means each vertex of the convex hull 𝒄𝒐𝒏𝒗(𝑷𝑰)has coordinates with a bit-length constrained by this bound. Application to Convex Hull Algorithms a. Numerical Stability: o Algorithms like QuickHull require operations on vertex coordinates, such as comparing slopes or calculating determinants. Knowing the bounds on the size of x ensures that these operations remain numerically stable and feasible on finite-precision systems. Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 70 b. Efficient Data Structures: o Solution size bounds guide the choice of data structures. For example, if the bound indicates small bit-lengths, lightweight data structures (e.g., arrays with fixed-width integers) can be used, reducing memory overhead. c. Algorithm Design: o When enumerating vertices of 𝒄𝒐𝒏𝒗(𝑷𝑰), solution size bounds restrict the search space, enabling pruning strategies in branch-and-bound algorithms. For example, if a candidate vertex exceeds the size bounds, it can be discarded without further computation. Application in β„πŸ Suppose P is a polygon defined by: 𝑷 = {𝒙 ∈ β„πŸ: πŸπ’™πŸ + π’™πŸ ≀ 𝟏𝟎,β€‰π’™πŸ + πŸ‘π’™πŸ ≀ πŸπŸ“,β€‰π’™πŸ, π’™πŸ β‰₯ 𝟎}. The integer points in P are (𝟎, 𝟎), (𝟏, 𝟎), (𝟐, 𝟎), … , (πŸ’, πŸ‘). ο‚· The convex hull of these points forms a polygon whose vertices are subsets of the integer points. ο‚· Using the size bounds, we confirm that all integer solutions 𝒙 = (π’™πŸ, π’™πŸ) satisfy π’”π’Šπ’›π’†(𝒙) ≀ πŸ’(𝟐 + 𝟐) = πŸπŸ”, ensuring efficient computations. iii) Impact on Algorithms: With these bounds: ο‚· Vertex Enumeration: We avoid considering infeasible points with excessively large coordinates. ο‚· Convex Hull Computation: Ensures that the algorithm’s runtime is proportional to the actual feasible vertices, reducing unnecessary overhead. This example demonstrates how solution size bounds provide theoretical guarantees that directly improve the efficiency and practicality of convex hull and vertex enumeration algorithms. Thus, it improves the bounds that contribute to better prerecession and numerical stability in LP solvers. V. Conclusion This paper establishes critical theoretical results in rational linear programming and polyhedral optimization, emphasizing boundedness equivalence and solution size constraints. By proving the equivalence of boundedness between rational polyhedra and their integer hulls, as well as Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 71 deriving explicit bounds on the size of optimal solutions, this work contributes to a deeper understanding of the structural and numerical properties of optimization problems. These findings are not only of theoretical interest but also pave the way for advancements in computational optimization, particularly in improving algorithmic efficiency and ensuring numerical stability. VI. Recommendations Future work may explore extensions to non-convex settings, where the feasible regions are no longer polyhedral, presenting new challenges in understanding boundedness and solution representation. Another promising direction involves generalizations to cases with irrational coefficients, which require advanced techniques to address the complexities introduced by non- rational systems. Furthermore, integrating these theoretical insights into practical optimization software and exploring their impact on real-world applications, such as logistics, network design, and machine learning, could significantly enhance the utility and scope of rational LP and polyhedral optimization. Such efforts would bridge the gap between theoretical advancements and their practical implementations, fostering innovation in both academic and industrial domains. References Akif, M B. and Cihan, A. (2008). A 0-1 integer programming approach to a university timetabling problem. Hacettepe Journal of Mathematics and Statistics, 37: 41-55. Cook, W., Cunningham, W. H., Pulleyblank, W. R., & Schrijver, A. (1986). Combinatorial Optimization. Wiley. Dantzig, G. B. (1947). Linear Programming and Extensions. Princeton University Press. Dantzig, G. B. (1947). Maximization of a linear function of variables subject to linear inequalities. In T. C. Koopmans (Ed.), Activity Analysis of Production and Allocation (pp. 339-347). Wiley. Elmuti, D. (2003). The perceived impact of outsourcing on organizational performance. American Journal of Business, 18: 33-42. Genova, K. and Guliashki, V. (2011). Linear integer programming methods and approaches - a survey. Journal of Cybernetics and Information Technologies. Vol 11. Gupta, Prem Kumar (Er.) and D. S. Hira (2014); Operations Research seventh Global Online Journal of Academic Research (GOJAR), Vol. 4, No. 1 February 2025 72 revised edition. By Rajendra Ravindra Pvt Ltd, ram Nagar New Delhi- 110055 and published by S. Chand & Company Pvt Ltd, India Kantorovich, L. V. (1939). Mathematical Methods in the Organization and Planning of Production. Leningrad State University. Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Combinatorica, 4(4), 373-395. Laisin, M., Edike, C. and Bright O. Osu (2024); The construction of rational polyhedron on an 𝒏 Γ— 𝒏 board with some application on integral polyhedral. TIJER, Vol 11, Issue 11, www.tijer.org Nemhauser, G. L., & Wolsey, L. A. (1999). Integer and Combinatorial Optimization. Wiley. Schrijver, A. (1998). Theory of Linear and Integer Programming. Wiley. Author Information: Prof. Mark Laisin is of the Department of Mathematics, Chukwuemeka Odumegwu Ojukwu University, Uli, Anambra State, Nigeria. Email: laisinmark@gmail.com Collins Edike is of the Department of Mathematics, Chukwuemeka Odumegwu Ojukwu University, Uli, Anambra State, Nigeria. Email: edikecollins505@gmail. com Dr R. N. Ujumadu is of the Department of Mathematics, Chukwuemeka Odumegwu Ojukwu University, Uli, Anambra State, Nigeria. Email: rozyngujmadu@yahoo. com APA Laisin, M., Edike, C., & Ujumadu, R. N. (2025). On Boundedness and Solution Size in Rational Linear Programming and Polyhedral Optimization. Global Online Journal of Academic Research (GOJAR), 4(1), 60-72. https://klamidas.com/gojar-v4n1-2025-04/. MLA Laisin, Mark, Edike, Collins, & Ujumadu, R. N. β€œOn Boundedness and Solution Size in Rational Linear Programming and Polyhedral Optimization”. Global Online Journal of Academic Research (GOJAR), vol. 4, no. 1, 2025, pp. 60-72. https://klamidas.com/gojar- v4n1-2025-04/.