patternMinor
Why can't we round results of linear programming to get integer programming?
Viewed 0 times
linearwhycanprogramminggetroundresultsinteger
Problem
-
If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed?
-
If linear programming suggests we can afford only $3.7$ workers, then why can't we just round down to $3$ workers?
When can we not use this rounding technique?
If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed?
-
If linear programming suggests we can afford only $3.7$ workers, then why can't we just round down to $3$ workers?
When can we not use this rounding technique?
Solution
In $\mathbb R$, one can simply round down or round up to obtain an element of $\mathbb Z$. Only two choices!
However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding.
Of course, one can round all entries of an $n$-dimensional vector down or up, but do note that the Euclidean distance between the two farthest vertices of the hypercube $[0,1]^n$ is $\sqrt n$. If $n=100$, then $\sqrt{100} = 10$.
Unfortunately, to the best of my knowledge, there is no guarantee that the solution to the integer program will be found via one of the $2^n$ possible rounding schemes.
Fortunately, some linear programs have integer solutions and, thus, no rounding is required.
However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding.
Of course, one can round all entries of an $n$-dimensional vector down or up, but do note that the Euclidean distance between the two farthest vertices of the hypercube $[0,1]^n$ is $\sqrt n$. If $n=100$, then $\sqrt{100} = 10$.
Unfortunately, to the best of my knowledge, there is no guarantee that the solution to the integer program will be found via one of the $2^n$ possible rounding schemes.
Fortunately, some linear programs have integer solutions and, thus, no rounding is required.
Context
StackExchange Computer Science Q#51951, answer score: 9
Revisions (0)
No revisions yet.