Integer Programming Lecture Notes PDF

Chapter 1 Integer programming Dr Kaouther Mohamed Ghacham College of engineering Industrial and systems department 1 The outlines Introduction 1 B...

Chapter 1 Integer programming Dr Kaouther Mohamed Ghacham College of engineering Industrial and systems department 1 The outlines Introduction 1 Branch and Bound (B&B) solution algorithm 5 Integer programming model 2 and formulations Integer programming 4 3 algorithms Illustrative applications 2 Dr Kaouther Ghacham Introduction Upon completing the course, student should: 1. Define more deterministic models in operations research using integer linear programming (K1) 2. Formulate and solve industrial and engineering problems using integer linear programming (S1) 3. Use an optimization software and spreadsheet-based interface to formulate and solve a real-life engineering and industrial applications problem. (S4) 3 Dr Kaouther Ghacham Introduction 4 Introduction We saw several examples of the numerous and diverse applications of linear programming (LP). However, one key limitation that prevents many more applications is the assumption of divisibility ,which requires that non-integer values be permissible for decision variables. In many practical problems, the decision variables actually make sense only if they have integer values. For example, it is often necessary to assign people, machines, and vehicles to activities in integer quantities. If requiring integer values is the only way in which a problem deviates from a linear programming formulation, then it is an integer programming (IP) problem. The mathematical model for integer programming is the linear programming model with the one additional restriction that the variables must have integer values. If only some of the variables are required to have integer values (so the divisibility assumption holds for the rest), this model is referred to as mixed integer programming (MIP). When distinguishing the all-integer problem from this mixed case, we call the former pure integer programming. 5 Dr Kaouther Ghacham  I- introduction-Examples One assumption of linear programming is that decision variables can take on fractional values such as X1 = 0.33 or X3 = 1.57. Yet many business problems can be solved only if variables have integer values When an airline decides how many planes to purchase, it cannot place an order for 5.38 aircraft, it must order 4, 5, 6, or some other integer amount. 6 Dr Kaouther Ghacham I- introduction Integer Nonlinear Goal programming programming programming is the extension is the extension is the case in of LP that solves of LP that permits which objectives problems more than one or constraints are requiring integer objective to be nonlinear. solutions. stated. All three above mathematical programming models are used when some of the basic assumptions of LP are made (more or less) restrictive. 7 Dr Kaouther Ghacham I- introduction An Integer Programming model is a linear programming problem where some or all the variables are required to be non-negative integers These models are in general substantially harder than solving linear programming models Network models are special cases of integer programming models and are very efficiently solvable We will discuss several applications of integer programming models. We will study the branch and bound technique, one of the most popular algorithm to solve integer programming models 8 Dr Kaouther Ghacham II- the integer programming models 1- The Pure Integer Programming problems are cases in which all variables are required to have integer values (see next slide) 2- The Mixed-Integer Programming problems are cases in which some, but not all, of the decision variables are required to have integer values (see next slide) 3- The Zero–One Integer Programming problems are special cases in which all the decision variables must have integer solution values of 0 or 1(see next slide) The most common algorithm here is the Branch & Bound method 9 Dr Kaouther Ghacham  I-Examples An IP in which all variables are An IP in which only some of the An integer programming problem in required to be integers is called a pure variables are required to be integers is which all the variables must equal 0 or integer programming problem. called a mixed integer programming 1 is called a 0-1 IP. The following is an For example, example of a 0-1 IP: problem. For example, max z  3x1  2 x2 max z  3x1  2 x2 max z  x1  x2 s.t. x1  x2  6 s.t. x1  x2  6 s.t. x1  2 x2  2 x1 , x2  0, x1 , x2 integer x1 , x2  0, x1 integer 2 x1  x2  1 x1 , x2  0 or 1 is a pure integer programming is a mixed integer programming problem. problem. 10 Dr Kaouther Ghacham I-Applications of linear programming 11 Dr Kaouther Ghacham  Step 1 How to formulate an integer problem? 12 I-The Pure Integer Programming problems Suppose a machine shop obtaining new presses and lathes. Marginal profitability: each press $100/day; each lathe $150/day. Resource constraints: $40,000 budget, 200 sq. ft. floor space. Machine purchase prices and space requirements: Required Machine Floor Space (ft.2) Purchase Price Press 15 $8,000 Lathe 30 4,000 Question: Formulate the problem 13 I- The Pure Integer Programming problems x1 = number of presses x2 = number of lathes The equations: Maximize Z = $100x1 + $150x2 subject to: $8,000x1 + 4,000x2  $40,000 15x1 + 30x2  200 ft2 x1, x2  0 and integer 14 II- (0-1) or Binary Integer Model (1 of 2) Recreation facilities selection to maximize daily usage by residents. Resource constraints: $120,000 budget; 12 acres of land. Selection constraint: either swimming pool or tennis center (not both). Expected Usage Land Requirement Recreation (people/day) Cost ($) (acres) Facility Swimming pool 300 35,000 4 Tennis Center 90 10,000 2 Athletic field 400 25,000 7 Gymnasium 150 90,000 3 15 II- 0-1 Integer Model (2 of 2) x1 = construction of a swimming pool x2 = construction of a tennis center x3 = construction of an athletic field x4 = construction of a gymnasium Maximize Z = 300x1 + 90x2 + 400x3 + 150x4 subject to: $35,000x1 + 10,000x2 + 25,000x3 + 90,000x4  $120,000 4x1 + 2x2 + 7x3 + 3x4  12 acres x1 + x2  1 facility x1, x2, x3, x4 = 0 or 1 16 III- Mixed Integer Model (1 of 2) $250,000 available for investments providing greatest return (profit) after one year. We have these available data: 1. Condominium cost $50,000/unit; $9,000 profit if sold after one year. 2. Land cost $12,000/ acre; $1,500 profit if sold after one year. 3. Municipal bond cost $8,000/bond; $1,000 profit if sold after one year. 4. Only 4 condominiums, 15 acres of land, and 20 municipal bonds available. 17 III- Mixed Integer Model (1 of 2) x1 = condominiums purchased x2 = acres of land purchased x3 = bonds purchased Maximize Z = $9,000x1 + 1,500x2 + 1,000x3 subject to: 50,000x1 + 12,000x2 + 8,000x3  $250,000 x1  4 condominiums x2  15 acres x3  20 bonds x2  0 x1, x3  0 and integer 18  Step 2 graphical solution for IP 19  H A R R I S O N E L E C T R I C C O M PA N Y E X A M P L E O F I N T E G E R P RO G R A M M I N G ( 1 O F 6 ) Company produces two products, old-fashioned chandeliers and ceiling fans Both require a two-step production process involving wiring and assembly It takes about 2 hours to wire each chandelier and 3 hours to wire a ceiling fan Final assembly of the chandeliers and fans requires 6 and 5 hours, respectively Only 12 hours of wiring time and 30 hours of assembly time are available Each chandelier produced nets the firm $7 and each fan $6 Step 1: formulate the problem Step 2: solve graphically the problem as a linear problem 20  H A R R I S O N E L E C T R I C C O M PA N Y E X A M P L E O F I N T E G E R P RO G R A M M I N G ( O F 6 ) Step 1: problem formulation Production mix LP formulation Maximize profit = $7X1 + $6X2 subject to 2X1 + 3X2 ≤ 12 (wiring hours) 6X1 + 5X2 ≤ 30 (assembly hours) X1, X2 ≥ 0 where X1 = number of chandeliers produced X2 = number of ceiling fans produced 21  H A R R I S O N E L E C T R I C C O M PA N Y E X A M P L E O F I N T E G E R P RO G R A M M I N G ( 3 O F 6 ) Step 2: graphical solution of the problem 22  H A R R I S O N E L E C T R I C C O M PA N Y E X A M P L E O F I N T E G E R P RO G R A M M I N G ( 4 O F 6 ) Production planner recognizes this is an integer problem First attempt at solving it is to round the values to X1 = 4 and X2 = 2 However, this is not feasible Rounding X2 down to 1 gives a feasible solution, but it may not be optimal This could be solved using the enumeration method (Generally not possible for large problems) 23  24 Harrison Electric Company Example of Integer Programming (6 of 6) CHANDELIERS (X1) CEILING FANS (X2) PROFIT ($7X1 + $6X2) 0 0 $0 1 0 7 2 0 14 3 0 21 4 0 28 5 0 35 Optimal solution to integer TABLE programming problem 0 1 6 Integer solutions to the Harrison 1 1 13 Electric Company Problem 2 1 20 3 1 27 4 1 34 Solution if rounding is used 0 2 12 1 2 19 The optimal integer solution is less than 2 2 26 the optimal LP solution of $35.25 3 2 33 0 3 18 An integer solution can never be better 1 3 25 than the LP solution and is usually a 0 4 24 lesser value