ETM 645-7 (Spring '14)Lesson: Integer ProgrammingObjectives:1. Solve IPs using implicit enumeration.2. Solve IPs using cutting plane method.3. Describe Traveling Salesman Problem (TSP).Assignment:1. Peruse Traveling Salesman Problem website.Homework:1. Use Implicit Enumeration to solve the following sequencing problem.Find the sequence of jobs from the set below which minimizes the sum of the trady times, toNiiT1.Where iC = completion time of job i, And id= the due date of job i,Then iT= max{ 0, iidC }.i pidi1 8 102 2 123 6 144 4 165 5 18Example using sequence 2-4-5-3-1Job 2 4 5 3 1Time 1 2 3 4 5 6 11 17 25i CidiTi1 25 10 152 2 12 03 17 14 34 6 16 05 11 18 0sum 18Over ->Homework cont:1 cont. a) Define and apply good upper bound.b) Define and apply a good lower bounding method.c) Using your upper bound and lower bound, show your implicit enumeration treeto find the optimal sequence.2. Use the cutting plane algorithm to solve the following IP:Max z = 14x1 + 18x2st -x1 + 3x2 <= 6 7x1 + x2 <= 35 X1, x2 >= 0; x1, x2 are integers.The optimal tableau for this IP’s linear programming relaxation is given below.z x1 x2 s1 s2 rhs1 0 0 56/11 2 8/11 126 0 0 1 7/22 1/22 3 1/2 0 1 0 - 1/22 3/22 4
View Full Document