# Upper bound on length of solution of linear program

Consider the linear program: $$\text{maximize} ~~ c\cdot x \\ \text{subject to} ~~ A\cdot x\leq b, ~~x\geq 0.$$ Suppose $$A$$ is an $$m\times n$$ matrix, $$b$$ an $$m\times 1$$ vector and $$c$$ an $$n\times 1$$ vector, and all their elements are integers with at most $$k$$ bits.

Suppose the program is feasible and bounded. What is an upper bound on the number of bits in the binary representation of the optimal solution value, as a function of $$m, n, k$$?

Since linear programming can be solved in polynomial time, I would guess that there is some upper bound that is polynomial in $$m, n, k$$. But what polynomial exactly?

EDIT: as there are many ways to represent numbers, I have to clarify that I mean: a representation of the solution as (numerator)/(denominator), where the numerator and the denominator are integers that are represented in binary. Note that a linear program always has a rational solution.

• Are you asking about a theoretical solution with infinite precision, or a numerical solution using a computer? The latter would be $64n$ assuming double-precision arithmetic.
– prubin
May 12 at 15:04
• I think it is obviously implied that number encoding is a degree of freedom when representing the solution. May 13 at 10:42
• @prubin as far as I know, a linear program with integer coefficients always has a solution that is a rational number. A rational number can be represented precisely as: numerator/denominator, and this representation is quite common in mathematical software. May 13 at 19:36

Based on the clarification that we are assuming exact arithmetic, and assuming $$m>1,$$ I think the bound is likely to be $$k \cdot m^2\cdot \log_2(m)$$ bits ... but the following bears careful checking.

Let's make a minor change (inserting slack variables) and write the constraint matrix as $$Ax = b,$$ where $$A$$ is now $$(m+n)\times n$$ and $$b$$ is still $$m\times 1.$$ The optimal solution is $$x=B^{-1} \cdot b$$ where $$B$$ is the $$m\times m$$ basis matrix.

Now use Cramer's rule to solve $$B\cdot x = b.$$ According to Cramer's rule, each element of $$x$$ is the ratio of two determinants, both coming from $$m \times m$$ matrices. Each determinant is the sum of $$m!$$ terms, with each term being the product of $$m$$ matrix elements. If each element is bounded in magnitude by $$2^k,$$ then each product is bounded by $$2^{mk}$$ and the determinant is bounded by $$m! \cdot 2^{mk}.$$ So the number of bits to express either numerator or denominator of any element of $$x$$ is bounded by $$k\cdot m \cdot \log_2(m!).$$ Since $$\log_2(m!)$$ is bounded by $$m\log_2(m),$$ the overall bound on the number of bits is $$k\cdot m^2\cdot \log_2(m).$$ (The bound can perhaps be tightened a bit using Stirling's approximation for the log of the factorial.)

• So the vector $c$ has no effect at all on the length of the output? May 14 at 4:48
• Correct. It selects the optimal corner of the feasible region, but not the coordinates of that corner.
– prubin
May 14 at 13:03
• I just corrected my answer. Due to a brain cramp applying Cramer's rule in the original answer, I underestimated the number of bits.
– prubin
May 14 at 13:21

Consider the linear program $$maximize\ x\ s.t. 3x = 1$$. It can be easily transformed into the standard form in your question. The optimal solution to this lp is $$x = \frac{1}{3}$$ with an objective value of $$\frac{1}{3}$$. The binary representation is $$0.010101010101...$$, repeating infinitely. Thus there is no upper bound on the length of the binary representation of the optimal value of an LP in general.

• Every rational number can be represented as: numerator/denominator. This representation is quite common in mathematical software in which precise output is wanted. In this representation, the binary length of 1/3 is (binary length of 1) + (binary length of 3). May 13 at 19:34

Let's consider $$\max_{x\in \mathbb{R}} x$$ subject to $$x*3=1$$. We know optimal value will be $$\in \mathbb{R}^1$$ and further based on properties of the polytope formed by the constraints, without being aware of the objective we can find that the polytope is $$\{1/3\}$$ so given the constraints we actually need 0 bits to represent the solution which is a far cry from $$\infty$$ bits. Let's consider $$0<=x*3<=1$$ similarily unaware of the objective. There are 3 possible solutions depending on the objectives. $$x=0$$, $$x=1/3$$ or $$x\in [0,1/3]$$ the third case reflects that the objective is orthogonal to the facet of the symplex holding the optimal solution or the objective weighted by $$\vec 0$$ face. Luckily you didn't ask for an encoding to all the solutions but of the encoding of one solution which we can do with just one bit.

This is not a pathology of one dimensional case. If there is a feasible and optimal point there has to be one on the vertices of the polytope. Also for any vertex of a polytope there exists an objective for which that corner is uniquely among the optimal point. So we need atleast $$\log_2(\#\text{vertices count})$$ bits. Formula for maximum vertex count. For fixed dimension this grows $$\log_2(\text{polynomial}(k))$$ where the order of the polynomial depends $$n$$. This encoding is not very useful though. One property would want from an encoding is to read of the solution from the encoding.

### A finite information componentwise interpretable encoding

The next construction rests on two claims:

• Given a bounded $$G \subset \mathbb{Z}$$ any polytope $$Ax<=b$$ with $$A\in G^{m\times n}$$ and $$b \in G^n$$ which is bounded all its vertices are rational. There is a finite number of distinct rational numbers which appear in those vertices. There exist a largest $$s$$ rational number whose integers multiples can represent any of rational numbers appearing in the vertices.

• Given a bounded $$G \subset \mathbb{Z}$$ any polytope $$Ax<=b$$ with $$A\in G^{m\times n}$$ and $$b \in G^n$$ projected on any axis results is an interval. These intervals have a bounded length $$d \in \mathbb{Q}^+$$ depending on $$(m,n,G)$$.

$${d\over s} \in \mathbb{Z}$$ by construction. Any vertex of $$Ax<=b$$ is $$\in ([-|{d\over s}|, |{d\over s}|] \cap \mathbb{Z} )^n * s$$ which we can represent with $$n \lceil \log_2 ({2*d\over s}) \rceil$$ bits.

### How large are $$d$$ and $$s$$?

$$(\prod_{g \in G} |g|)^{(m+1) n}$$ is a valid $$1 \over s$$. There are way tighter bounds though.

For bounding $$d$$ i don't have a formula, however we can calculate $$d \over 2$$ using a MINLP program.

It involves insections of the most slightly non parallel hyper planes being as far away from each other as possible using integers available as coefficients from $$G$$. The maximum objective of this program in the JuMP modeling language calculates $$d\over 2$$ in for $$n=2$$, $$m=2$$ by finding a pairs of equality constraints in $$\mathbb{R}^2$$ such that the point defined by the pairs intersection has a maximal squared first component.

using JuMP, Gurobi

l =-2
u = 1
M = max(l^2, u^2)

m = Model(Gurobi.Optimizer)
set_attribute(m, "Presolve", 2)
set_attribute(m, "NonConvex", 2)

set_attribute(m, "FeasibilityTol", 1.1e-9)

@variable(m, -1.0e11 <= x[1:2] <= 1.0e11)
#mess with this bound and Gurobi cries. It obviously limits the validity of the program, but those errors are dominated by Gurobis minimal "FeasibilityTol" of 1.0e-9. Don't trust it to be correct for large numbers.

@variable(m, l<= b[1:2] <= u,Int)
@variable(m, l<= a[1:2,1:2] <= u,Int)

@constraint(m, a[:,:]*x[:] == b[:])  # Two linear inequalities

@objective(m, Max, (x)^2)

@variable(m, 0 <= s[1:2] <= M *2, Int)
for j in 1:2 @constraint(m, s[j] == sum( a[j,:].* a[j,:])) end

@variable(m, M *-2 <= c <= M *2, Int)
@constraint(m, c == sum( a[1,:].* a[2,:])) # scalar product between the equations
@constraint(m, c*c + 1 <= s*s)
# We want them not being colinear, so we impose <a[1,:], a[2,:]>^2 < ||a[1,:]||^2*||a[2,:]||^2, since all coefficients are integer +1 is actually a safe epsilon to impose this.

optimize!(m)


For $$G = \mathbb{Z} \cap [-1,0]$$ $$d=2$$ holds. For $$G = \mathbb{Z} \cap [-1,1]$$ $$d=8$$ holds. For $$G = \mathbb{Z} \cap [-2,1]$$ $$d=8$$ holds. For $$G = \mathbb{Z} \cap [-8,7]$$ $$d=28800$$ holds. Beyond this (and maybe also earlier) you will need a rational solver to get accurate results. I am not aware of such a solver. I hope you can discover a structure which let's you build an upper bound for $$d$$ with this. Representing the $$\{0, 1, 2, 5\}$$ requires additional binary variables.

### An idea for a $$d(m,m,G)$$ This might be the most amplying square matrix. It assumes without loss of much generality that $$|\min G| \leq \max G$$.

• What is $s$? And why is $d/s$ an integer? May 14 at 7:14
• $1/s$ is a rational number when we scale the polyhedra by it all vertices are have integer coordinates. $s$ is the "fineness" of the lattice which can represent all the vertices $Ax \leq b$ can reach given $(m,n,G)$. $d$ since it is the maximum width of the polyhedra projected onto an axis, it is the difference between components of vertices. By scaling by $d$ by $1/s$ those components are in $\mathbb{Z}$ the distance between integers is an integer. May 14 at 11:47