





























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/.  

 

 

 


