1、7 - 1Chapter 13: Integer ProgrammingPowerPoint Slides Prepared By:Alan Olinsky Bryant UniversityManagement Science: The Art of Modeling with Spreadsheets, 2eS.G. Powell K.R. Baker John Wiley and Sons, Inc.13 - 1Introduction w The optimal solution of a linear program may contain fractional decision v
2、ariables, and this is appropriateor at least tolerablein most applications. w In some cases, however, it may be necessary to ensure that some or all of the decision variables take on integer values. w Accommodating the requirement that variables must be integers is the subject of integer programming
3、. w In this chapter, we examine the formulation and solution of integer programs.2Integer Variables and the Integer Solver w Solver allows us to directly designate decision variables as integer values. w In the case of integer linear programs, Solver employs an algorithm that checks all possible ass
4、ignments of integer values to variables, although some of the assignments may not have to be examined explicitly. w This procedure may require the solution of a large number of linear programs, but because Solver can do this quickly and reliably with the simplex algorithm, it will eventually locate
5、a global optimum. w In the case of integer nonlinear programs, however, certain difficulties can arise, although Solver will always attempt to find a solution. w Because integer versions of nonlinear programs are particularly challenging, we concentrate here on integer linear programs. 3Designating
6、Variables as Integers 4Setting the Tolerance Parameter 5Solver Tip: Integer Optionsw The most important integer option is the Tolerance parameter.w The default value of the parameter is 5%, and we may leave this value undisturbed while we debug our model.w Once we are convinced that our model is run
7、ning correctly, we can set the Tolerance parameter to 0% so that an optimal solution is guaranteed. 6Binary Variables and Binary Choice Models w A binary variable, which takes on the values zero or one, can be used to represent a “go / no-go” decision. w We can think in terms of discrete projects, w
8、here the decision to accept the project is represented by the value 1, and the decision to reject the project is represented by the value 0. 7The Capital Budgeting Problem w Companies, committees, and even households often find themselves facing a problem of allocating a capital budget.w As the prob
9、lem arises in many firms, there is a specified budget for the year, to be invested in multi-year projects. w There are also several proposed projects under consideration.w The committees job is to determine how to maximize the value of the projects selected, subject to the limitation on expenditures
10、 represented by the capital budget.8The Capital Budgeting Problemw In the classic version of the capital budgeting problem, each project is described by two values: the expenditure required and the value of the project. w As a project is typically a multi-year activity, its value is represented by t
11、he net present value (NPV) of its cash flows over the project life. w The expenditure, combined with the expenditures of other projects selected, cannot be more than the budget available9Designating Variables as Binary Integers 10The Set Covering Problem w The set covering problem is a variation of
12、the covering model in which the variables are all binary. w In addition, the parameters in the constraints are all zeroes and ones.w In the classic version of the set covering problem, each project is described by a subset of locations that it “covers.”w The problem is to cover all locations with a
13、minimal number of projects.11Binary Variables and Logical Relationships w We sometimes encounter additional conditions affecting the selection of projects in problems like capital budgeting. w These include relationships among projects, fixed costs, and quantity discounts. 12Relationships among Proj
14、ects w Projects can be related in any number of ways. w We cover five types of relationships here:n at least m projects must be selectedn at most n projects must be selectedn exactly k projects must be selectedn some projects are mutually exclusiven some projects have contingency relationships13Rela
15、tionship:at least m projects must be selectedw y2 + y5 = 1w Project 2, or Project 5, or both, will be selected, thus satisfying the requirement of at least one selection. 14Relationship:at most n projects must be selectedw y4 + y5 = 0w If Project 5 is selected, then project 3 must be as well.17Linki
16、ng Constraints and Fixed Costs w We commonly encounter situations in which activity costs are composed of fixed costs and variable costs, with only the variable costs being proportional to activity level. w With an integer programming model, we can also integrate the fixed component of cost.18Incorp
17、orating a fixed cost into the model w We separate the fixed and variable components of cost. w In algebraic terms, we write cost as n Cost = Fy + cx, where F represents the fixed cost, and c represents the linear variable cost. w The variables x and y are decision variables, where x is a normal (con
18、tinuous) variable, and y is a binary variable. 19Linking Constraintw To achieve consistent linking of the two variables, we add the following generic linking constraint to the model:x = 0, these two constraints together force x to be zero. Thus, when y = 0, it will be consistent to avoid the fixed c
19、ost. w On the other hand, when y = 1, the right-hand side will be so large that Solver does not need to restrict x at all, permitting its value to be positive while we incur the fixed cost. Thus, when y = 1, it will be consistent to incur the fixed cost. Of course, because we are optimizing, Solver
20、will never produce a solution with the combination of y = 1 and x = 0, because it would always be preferable to set y = 0.21Solver Tip: Logical Functions and Integer Programmingw Unfortunately, the linear solver does not always detect the nonlinearity caused by the use of logical functions, so it is
21、 important to remember never to use an IF function in a model built for the linear solver.22Threshold Levels and Quantity Discounts wThreshold level requirement: a decision variable is either at least as large as a specified minimum, or else it is zero.w The existence of a threshold level does not d
22、irectly affect the objective function of a model, and it can be represented in the constraints with the help of binary variables. 23Threshold Levelsw Suppose we have a variable x that is subject to a threshold requirement. Let m denote the minimum feasible value of x if it is nonzero. Then we can ca
23、pture this structure in an integer programming model by including the following pair of constraints:x my = 0x My = 0where, as before, M is a large number that is greater than or equal to any value x could feasibly take. 24*The Facility Location Modelw The transportation model is typically used to fi
24、nd optimal shipping schedules in supply chains and logistics systems. w The applications of the model can be viewed as tactical problems, in the sense that the time interval of interest is usually short, say a week or a month. w Over that time period, the supply capacities and locations are unlikely
25、 to change at all, and the demands can be predicted with reasonable precision. 25*The Facility Location Modelw Over a longer time frame, a strategic version of the problem arises. In this setting, the decisions relate to the selection of supply locations as well as the shipment schedule. w These dec
26、isions are strategic in the sense that, once determined, they influence the system for a relatively long time interval. w The basic model for choosing supply locations is called the facility location model.26The Capacitated Problem w Conceptually, we can think of this problem as having two stages. w
27、 In the first stage, decisions must be made about how many warehouses to open and where they should be. w Then, once we know where the warehouses are, we can construct a transportation model to optimize the actual shipments. w The costs at stake are also of two types: fixed costs associated with kee
28、ping a warehouse open and variable transportation costs associated with shipments from the open warehouses. 27The Uncapacitated Problem w Once we see how to solve the facility location problem with capacities given, it is not difficult to adapt the model to the uncapacitated case.w Obviously, we cou
29、ld choose a virtual capacity for each warehouse that is as large as total demand, so that capacity would never interfere with the optimization. 28The Assortment Model w The facility location model, with or without capacity constraints, clearly has direct application to the design of supply chains an
30、d the choice of locations from a discrete set of alternatives.w But the model can actually be used in other types of problems because it captures the essential trade-off between fixed costs and variable costs.w An example from the field of Marketing is the assortment problem, which asks which items
31、in a product line should be carried, when customers are willing to substitute.29Summary w Integer programming problems are optimization problems in which at least one of the variables is required to be an integer. w Solvers solution to linear integer programs is reliable: a global optimal solution always occurs as long as the Tolerance parameter has been set to zero.w Binary variables can represent all-or-nothing decisions that allow only accept/reject alternatives. 30
