Integer programming (intro)
General · Mathematics
Study notes
Q: Solve: max x+2y s.t. 3x+2y ≤ 7, x,y ≥ 0 integers. Compare with LP optimum. LP (ignore integers): corner (0, 3.5), z = 7. But y = 3.5 is not an integer! Try integer points: (0,3): 3(0)+2(3) = 6 ≤ 7 ✓, z = 0+6 = 6. (1,2): 3+4 = 7 ≤ 7 ✓, z = 1+4 = 5. (2,0): z = 2. IP optimum: (0,3) with z = 6, strictly less than LP's 7! Naive rounding of (0,3.5) to (0,4) would be infeasible (8 > 7). Lesson: rounding LP solutions is unsafe — use branch and bound!