MKTG 2030 Lecture Notes - Linear Programming Relaxation, Integer Programming, Linear Programming
18 Mar 2014
School
Department
Course
Professor
Document Summary
Integer programming (ilp: linear programming allows us to solve large-scale problems. Integrality conditions are easy to state but make the problem much more difficult (and sometimes impossible) to solve. When solving an lp relaxation, sometimes you get lucky and obtain an integer feasible solution. It is tempting to simply round a fractional solution to the closest integer solution. How rounding down can result in an infeasible solution. Example: all-integer lp: consider the following all-integer linear program: 3x1 + x2 < 9 x1 + 3x2 < 7. From the graph we see that the optimal solution to the linear program is: x1 = 2. 5, x2 = 1. 5, z = 10. 5. If we round up the fractional solution (x1 = 2. 5, x2 = 1. 5) to the lp relaxation problem, we get x1 = 3 and x2 = 2. From the graph we see that this point lies outside the feasible region, making this solution infeasible.
