3
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – prubin
    May 12, 2023 at 15:04
  • $\begingroup$ I think it is obviously implied that number encoding is a degree of freedom when representing the solution. $\endgroup$ May 13, 2023 at 10:42
  • 1
    $\begingroup$ @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. $\endgroup$ May 13, 2023 at 19:36

3 Answers 3

5
$\begingroup$

Based on the clarification that we are assuming exact arithmetic, and assuming $m>1,$ I think the bound is likely to be $m\cdot (k + \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\times (m+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 + \log_2(m!).$ Since $\log_2(m!)$ is bounded by $m\log_2(m),$ the overall bound on the number of bits is $m\cdot (k + \log_2(m)).$ (The bound can perhaps be tightened a bit using Stirling's approximation for the log of the factorial.)

$\endgroup$
6
  • $\begingroup$ So the vector $c$ has no effect at all on the length of the output? $\endgroup$ May 14, 2023 at 4:48
  • $\begingroup$ Correct. It selects the optimal corner of the feasible region, but not the coordinates of that corner. $\endgroup$
    – prubin
    May 14, 2023 at 13:03
  • $\begingroup$ I just corrected my answer. Due to a brain cramp applying Cramer's rule in the original answer, I underestimated the number of bits. $\endgroup$
    – prubin
    May 14, 2023 at 13:21
  • $\begingroup$ As you say, the determinant is bounded by $m! 2^{mk}$; the logarithm of that is $mk + \log_2(m!}$, and not $mk \cdot \log_2(m!}$. So the overall bound should be $mk + m\log_2(m)$, right? $\endgroup$ Apr 3 at 14:07
  • 1
    $\begingroup$ Correct on both counts. I've corrected the answer. Apparently I accidentally drank decaf that morning. $\endgroup$
    – prubin
    Apr 3 at 15:36
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$ May 13, 2023 at 19:34
0
$\begingroup$

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[1])^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[1]*s[2])
# 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)$

enter image description here This might be the most amplying square matrix. It assumes without loss of much generality that $|\min G| \leq \max G$.

$\endgroup$
2
  • $\begingroup$ What is $s$? And why is $d/s$ an integer? $\endgroup$ May 14, 2023 at 7:14
  • $\begingroup$ $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. $\endgroup$ May 14, 2023 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.