Operations research
Myth vs fact
Can You Just Round an LP Answer?
Got 2.6 trucks from your LP? Rounding might wreck it.
Quick check · tap an answer to continue
Lesson notes
Key points
- Rounding a fractional LP solution can push the point outside the feasible region, breaking a constraint.
- Even when rounding stays feasible, the true integer optimum can sit at a completely different point, found by branch and bound.
Myth: Round the LP solution and you get the best integer solution.
Fact: Rounding can be infeasible or suboptimal; integer methods are needed.
Takeaway: Never trust rounding; integer problems need integer methods.
Quick check: Myth or fact: an integer program's optimum is never better than its LP relaxation's.
- Myth
- Fact
- Depends
Adding integer restrictions shrinks the feasible set, so it can't improve the optimum.
InfeasibilityBranch and bound
Lessons like this, for your syllabus.
Short narrated study videos written for your course, level and exam. Free to start.
Get lessons for your own syllabus