Problem Detail:
- 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?
Asked By : Souradeep Nanda
Answered By : D.W.
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).
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/51951 Ask a Question Download Related Notes/Documents