Integer Programming Lecture Notes PDF

Chapter 1 Integer programming Session 3-4-5 Dr Kaouther Mohamed Ghacham College of engineering Industrial and systems department 25  How to formulate various applications based on ILP problem? Case of Binary Integer...

Chapter 1 Integer programming Session 3-4-5 Dr Kaouther Mohamed Ghacham College of engineering Industrial and systems department 25  How to formulate various applications based on ILP problem? Case of Binary Integer Problems 26 Example 1- (textbook Hiller p475) The CALIFORNIA MANUFACTURING COMPANY is considering expansion by building a new factory in either Los Angeles or San Francisco, or perhaps even in both cities. It also is considering building at most one new warehouse, but the choice of location is restricted to a city where a new factory is being built. The net present value (total profitability considering the time value of money) of each of these alternatives is shown in the fourth column of Table 12.1. The rightmost column gives the capital required (already included in the net present value) for the respective investments, where the total capital available is $10 million. The objective is to find the feasible combination of alternatives that maximizes the total net present value. 27 Dr Kaouther Ghacham Example 1- (textbook Hiller p475) 28 Dr Kaouther Ghacham Example 1- (textbook Hiller p475) 29 Dr Kaouther Ghacham Example 1- (textbook Hiller p475) 30 Dr Kaouther Ghacham Example 1- (textbook Hiller p475) Except for its small size, this example is typical of many real applications of integer programming where the basic decisions to be made are of the yes-or-no type. Like the second pair of decisions for this example, groups of yes-or-no decisions often constitute groups of mutually exclusive alternatives such that only one decision in the group can be yes. Each group requires a constraint that the sum of the corresponding binary variables must be equal to 1 (if exactly one decision in the group must be yes) or less than or equal to 1 (if at most one decision in the group can be yes). Occasionally, decisions of the yes-or-no type are contingent decisions, i.e., decisions that depend upon previous decisions. For example, one decision is said to be contingent on another decision if it is allowed to be yes only if the other is yes. This situation occurs when the contingent decision involves a follow-up action that would become irrelevant, or even impossible, if the other decision were no. The form that the resulting constraint takes always is that illustrated by the third and fourth constraints in the example. 31 Dr Kaouther Ghacham Example 2: Capital Budgeting Problem (p 360-361,T.Hamdy) 32 Example 2: Capital Budgeting Problem (p 360-361,T.Hamdy) 33 Example 2: Capital Budgeting Problem (Excel solver) input data x1 x2 x3 x4 x5 totals constraints limits objective 20 40 20 15 30 1 5 4 3 7 8 19