7
$\begingroup$
  • 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?

$\endgroup$
4
  • $\begingroup$ Dumb answer: because then P = NP which is still open. So clearly the technique can not always work. $\endgroup$
    – Raphael
    Commented Oct 23, 2016 at 22:03
  • $\begingroup$ Not really. There is no reason why P cannot be NP. Also, read pseudo polynomial. en.wikipedia.org/wiki/Pseudo-polynomial_time $\endgroup$ Commented Oct 24, 2016 at 7:53
  • 2
    $\begingroup$ There is no reason, true; but believe me, if rounding LPs was the answer it would have been figured out decades ago. This is not a new idea. $\endgroup$
    – Raphael
    Commented Oct 24, 2016 at 10:51
  • $\begingroup$ You are looking at trivial cases. Yes, if T ≥ 2.5 and T must be an integer, then T ≥ 3. And if W ≤ 3.7 and W must be an integer, then W ≤ 3. But now take two variables, say 0.136x + 0.049y ≤ 10, and find integers x, y to make 0.136x + 0.049y as large as possible. Have fun. And that's still very, very simple. $\endgroup$
    – gnasher729
    Commented Oct 24, 2016 at 18:04

3 Answers 3

7
$\begingroup$

If there are only constraints that place a lower bound on the number of trucks, but no constraints that place an upper limit on the number of trucks, then of course you can round up. That will still give you a solution.

However, there are multiple caveats:

  • First, this isn't always possible. Sometimes there are both constraints that place lower limits and constraints that place upper limits. It can happen that taking a solution and rounding gives you something that is no longer a solution.

  • Even if the result of the rounding is a solution, there is no guarantee that it is the best out of all solutions that uses integers. There may be some other way to choose integers for all the variables that is better than the solution you got by rounding.

If you want solutions that are all integer, then you have an integer linear programming problem. Integer linear programming (ILP) is harder than linear programming (LP). In particular, there are polynomial-time algorithms for LP, but ILP is NP-hard, so there is most likely no polynomial-time algorithm for ILP (unless P=NP, which is considered unlikely).

$\endgroup$
3
  • 1
    $\begingroup$ Could you give an example where the rounded solution is sub optimal to the integer solution while both are in solution space? $\endgroup$ Commented Jan 17, 2016 at 4:46
  • 5
    $\begingroup$ Trivial: Assume there is a condition x+y = 1, with both x=0, y=1 and x=1, y=0 valid, but with different values of the goal function. There are two ways to round a non-integer solution to a valid solution, and since the goal function will have two different values, one cannot be optimal. $\endgroup$
    – gnasher729
    Commented Oct 23, 2016 at 15:46
  • 3
    $\begingroup$ @gnasher729 And that also demonstrates a case where rounding a valid solution ($x=y=\tfrac12$) can lead to an invalid solution ($x=y=1$). $\endgroup$ Commented Oct 24, 2016 at 11:13
9
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

Here is a 2d region where rounding the optimal continuous solution (top right) will always give an invalid integer solution:

1.4x-1.1\ <\ y\ <\ 1.1x+0.2

Here is a 2d region where rounding the optimal continuous solution (green vertex) may give you a valid integer solution 0,1, but will never give you the optimal integer solution 2,1 (blue vertex). Maximizing y+5x for positive x, y.

4x-8<y<-0.4x+1.9

$\endgroup$

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.