文档介绍：1 Lecture 18 Integer Programming If the LP relaxation is infeasible, then the ILP is infeasible. If the optimal solution to the LP is integer, then this is the optimal solution to the ILP also. optimum for both LP and ILP 2 Problem P: max cx . Ax =b0<x<ux j integer for allj Problem LP: max cx . Ax =b0<x<u Let x 1 be feasible for P. Then cx 1 isa lower bound for problem P. Let x 2 be an optimum for LP. Then cx 2 is an upper bound for P. 3 gap = (120-100)/120 = % When constructing anLP model, we usually try to use the smallest number of constraints and variables. ----------------------------------------------- When constructing an ILP model, we usually try to make the optimal objective value of the LP relaxation as small as possible. This may involve using more constraints than is absolutely necessary. Obj Value cx LP optimum 120 ILP optimum 100 ILP feasible 80 gap: from LP to ILP 4 Consider a problem with constraints of the form: select xor y, select xor z, select yorz max x+y+z . x+y<1x+z<1y+z<1 x, y,z binary LP relaxation yields (1/2, 1/2, 1/2) with objective value of 3/2. -------------------------------------------- max x+y+z . x+y<1x+z<1y+z<1x+y+z<1 x, y,z binary 5 LP relaxation yields (1,0,0) with objective value of1 (a better relaxation). We used a redundant constraint to obtain an improved relaxation. The gap between the LP and ILP is smaller. I'm working ona design problem where customers for wireless phone service are assigned to towers and channels are assigned to customer-binations. Denotes a customer site tower 2 tower 1 SMU 6 Assumptions 1. Customers can be assigned to either tower 2. tower #1 capacity = 800 customers, cost = $300,000 3. tower #2 capacity = 750 customers, cost = $288,888 4. revenue per customer each year = $750 ----------------------------------------------- Determine which tower(s) to build and which customers to assign to the towers. 7 Run #1 printf"Model1\n\n"; var C1T1 >= 0; var C1T2 >= 0; var C2T1 >= 0; v