15.053 Lecture Notes - Lecture 11: Royal Netherlands Academy Of Arts And Sciences, Hacks At The Massachusetts Institute Of Technology, Fathom
Document Summary
How linear programming can help with solving integer programs. Divide and conquer: splitting a hard problem into two hard (but smaller) problems. Make a list of all 2 possible choices of the variables. Suppose that we could evaluate 1 billion solutions per second. Let n equal the number of binary variables. Solution times for evaluating 2 solutions n = 30 n = 40 n = 50 n = 60 n = 70. An integer program and its linear program relaxation. Relaxing constraints makes the feasible region larger, thus z z. Note: if the optimal solution for the linear program relaxation is feasible for the integer program, then z = z. 5x + 7x + 4x + 3x + 4x + 6x 18 x {0, 1} for each j = 1 to 6. 0 x 1 for each j = 1 to 6. Sometimes you just get lucky and the solution is integer.
