Naive approach: rounding The rounded solution is x*=(2,0). But this is not even feasible By enumeration, feasible x are(0,0)(0, 1)(0, 2) (0,3)(1,1)(1,0) The optimal integer solution x *is(0, 3)[value 33] which is nowhere near(13/7,0 In general, just finding a nearby feasible point is computationally challenging Solving Integer Programs Characteristics Fewer feasible solutions than lps Worst-case exponential in of variables Commercial software. plexNaïve approach: rounding • The rounded solution is x*=(2,0). But this is not even feasible! • By enumeration, feasible x are (0,0) (0,1) (0,2) (0,3) (1,1) (1,0) • The optimal integer solution x* is (0,3) [value = 33] which is nowhere near (13/7,0). • In general, just finding a nearby feasible point is computationally challenging Solving Integer Programs: Characteristics • Fewer feasible solutions than LPs. • Worst-case exponential in # of variables. • Commercial software: – Cplex