Integer Linear Programming - IntroductionPowerPoint PresentationSlide 3Classifications of IP ModelsClassifications of IP Models (contd.)Slide 6Simple Approaches for Solving IPInteger feasible vs. LP feasible soultionsRounding an LP solutionIP and LP RelaxationCapital Budgeting ProblemExerciseSolutionSolution – contd.Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Set Covering ProblemsFormulation of Set Covering ProblemsA Capital Budgeting Problem:solutionSlide 29Sol contd.exercisesExercises - contdSlide 33Slide 34Slide 35Slide 36Example of IP: Facility LocationSlide 38Extra restrictionsSlide 40Slide 41Slide 42Modeling Technique: Restrictions on the number of optionsSlide 44Contingent DecisionsSlide 46Slide 47Slide 48Slide 49Slide 50Integer Linear Programming - IntroductionIn many network planning problems the variables can take only integer values, because they represent choices among a finite number of possibilities.Such a mathematical program is known as integer program.Often the variables can only take two values, 0 and 1. Then we speak about 0-1 programming.If the problem, apart from the restriction that the variables are integer valued, has the same formulation as a linear program, then it is called an integer linear program (ILP).Sometimes it happens that only a subset of the variables are restricted to be integer valued, others may vary continuously. Then we speak about a mixed programming task. If it is also linear, then it is a mixed ILP.1Model2maximize c1x1+c2x2+…+cnxn(objective function)subject to (functional constraints) a11x1+a12x2+…+a1nxn b1 a21x1+a22x2+…+a2nxn b2….am1x1+am2x2+…+amnxn bm (set constraints) x1, x2 , …, xn Z+Z denotes the set of integersNote: Can also have equality or ≥ constraint in non-standard form.34Classifications of IP ModelsPure IP Model: Where all variables must take integer values.Maximize z = 3x1 + 2x2subject to x1 + x2 6 x1, x2 0, x1 and x2 integerMixed IP Model: Where some variables must be integer while others can take real values.Maximize z = 3x1 + 2x2subject to x1 + x2 6x1, x2 0, x1 integer0-1 IP Model: Where all variables must take values 0 or 1 .Maximize z = x1 - x2subject to x1 + 2x2 2 2x1 - x2 1, x1, x2 = 0 or 15Classifications of IP Models (contd.)LP Relaxation: The LP obtained by omitting all integer or 0-1 constraints on variables is called the LP relaxation of IP.IP:Maximize z = 21x1 + 11x2subject to 7x1 + 4x2 13x1, x2 0, x1 and x2 integerLP Relaxation:Maximize z = 21x1 + 11x2subject to 7x1 + 4x2 13x1, x2 0Result:Optimal objective function value of IP Optimal obj. function value of LP relaxationOne might think that since there are fewer solutions for an ILP (finitely many, if the solution set is bounded) than for its relaxation, that it is easier to find a solution for the ILP; this is not the case. In fact, it is in general much more difficult to solve an ILP than to solve an LP of similar size. This is because LP-solving algorithms take advantage of the fact that an optimal solution of an LP is a basic solution of the LP and a corner point of the feasible region. The feasible region for an ILP is not continuous, so these methods cannot be applied.Often we have to apply heuristic or approximative approaches, because finding the exact global optimum for a large problem is rarely feasible.67Simple Approaches for Solving IPApproach 1: Enumerate all possible solutionsDetermine their objective function valuesSelect the solution with the maximum (or, minimum) value.Any potential difficulty with this approach?Approach 2: Solve the LP relaxationRound-off the solution to the nearest feasible integer solutionAny potential difficulty with this approach?Integer feasible vs. LP feasible soultionsFeasible solutions8X1X2Integer Feasible Solutions001 2 34123Rounding an LP solutionRounding can lead to infeasible solution:9X1X2001 2 3 4123optimal relaxed solutioninfeasible solution obtained by rounding down10IP and LP Relaxationx x xxxxxxx1x21 231327x1 + 4x2= 1311Capital Budgeting ProblemStockco Co. is considering four investmentsIt has $14,000 available for investmentFormulate an IP model to maximize the NPV obtained from the investmentsIP:Maximize z = 16x1 + 22x2 + 12x3 + 8x4subject to 5x1 + 7x2 + 4x3 + 3x4 14x1, x2,,x3, x4 0, 1Investmentchoice1 2 3 4Cashoutflow$5000 $7000 $4000 $3000NPV $16000 $22000 $12000 $8000ExerciseConsider a US company with Separate East coat and West coast networks that are not presently connected. The west coast network consists of switches (nodes) in Seattle (1), San Fransisco (2), Lost Angeles (3). The east coast network consists of switches in New York (4) Washington DC (5) and Atlanta (6).A decision is made to connect the two networks through a single transcontinental link that will originate in one of the west coast cities, pass through a hub in either Chicago (A) or Dallas (B), and continue on to one of the east coast cities.Draw a map of this situation. Let cij be the cost of a link from coast city i (note the ID numbers) to hub city j(j = A or B). Let xij be 1 if there is a link from coast city i(i=0,1,…6) to hub city j (j=A, B) and 0 otherwise.Write a mathematical program that minimizes the cost of single transcontinental route and satisfies the constraints above12SolutionFirst we draw a map of the situation:13123465ABA Potential Layout of the Transcontinental LinkSolution – contd.14Solution – contd.15ExerciseAssume that in an integer linear programming problem we have n variables. Each variable can only take the value 0 or 1Express each of the conditions a.), b.), c.) given below, such that you can only use linear equations or inequalities, nothing else.a) At least one variable must take the value 0.b) At most one variable can take the value 0.c) Either all variables are 0, or none of them.16Solutiona) At least one variable must take the value 0.This means, they cannot be all 1, so their sum is at most n − 1:x1 + x2 + . . . + xn ≤ n − 1orx1 + x2 + . . . + xn < n17Solution – contd.b) At most one variable can take the value 0.This means, at least n − 1 of them is 1, so their sum is at least n − 1:x1 + x2 + . . . + xn ≥ n − 118Solution – contd.c) Either all variables are 0, or none of them.This means, they all must be equal:x1 = x2 = . . . = xnor,
View Full Document
Unlocking...