INTRODUCTION TO INTEGER LINEAR PROGRAMMING WAREHOUSE LOCATION Prof. Stephen Graves A firm wants to decide where to locate its warehouses to best serve its customer base. It has aggregated the customer base according to three-digit zip code regions; for each aggregate customer, the firm has estimated the annual product demand for that region. The firm has also generated a list of candidate warehouse sites; for each candidate site, the firm has estimated the annual fixed cost for opening and operating the warehouse, the per-unit transportation costs for supplying the warehouse from the firm's production facilities, and the per-unit transportation costs for supplying each aggregate customer from this warehouse. In addition to minimizing costs for distribution, the firm insists that the warehouse service to each customer meet some minimum service threshold, e. g., delivery within 24 hours. 15.066J Summer 2003 59A SPARE PARTS PROBLEM An office equipment company has a crew of field representatives who provide service to the company's customers. When an installed piece of equipment (a photocopier) fails, a field representative is sent to attempt to diagnose and repair the equipment. In order to be able to complete the repair on site, the field representative carries an inventory of spare parts. If the repair requires the replacement of parts that the field rep does not have on hand, then the field rep must return to the local sales office or warehouse for the part and then turn around and return to the customer site. This greatly increases the amount of time the customer is inconvenienced due to the failed copier. However, since the field representative must carry the spare parts in his/her vehicle, there is a physical limit on how many different types of spare parts can be carried. Furthermore, it is very hard to anticipate what parts are needed on any particular repair job; in most instances the customer is not able to provide very helpful diagnostic information when reporting a failure. Suppose that there are 100 replaceable parts in the copier, and that pj, j = 1, 2, ... 100, is the probability that part j is needed to complete a repair, given that the copier has failed. For simplicity, assume that the probability of requiring part i is independent of the probability of requiring part j, for all pairs i, j. Let sj be the space consumed by part j, and suppose that the field rep's vehicle can carry 40 cubic feet of spare parts. 15.066J Summer 2003 60FIXED CHARGE PROBLEM The cost function for many production activities consists of a fixed component and a variable component. If there is no production activity, the cost is zero. If there is any production activity at all, then a fixed cost is incurred; this often will correspond to a setup or changeover cost. Beyond the fixed cost, there may be a variable cost that is proportional to the amount of production. Sometimes, if we talk about the production cost function for a production department or line, there may be several fixed charges depending upon the number of shifts to be run (or some other measure of activity). There may be a fixed charge for operating the first shift; this would include overhead and indirect costs required to keep the facility open and operate the department. If two shifts are to be run, there will be a fixed charge for each shift, with the charge for the second shift usually smaller than for the first. Similarly, there are three fixed charges if three shifts are running. To this, we need add the variable production costs, where the variable cost rate may also depend upon the shift. Here it would be common to expect that the variable cost rate for the first shift to be lower than for the second, which is lower than the third shift. 15.066J Summer 2003 61APPROXIMATING NON LINEAR FUNCTIONS Suppose we wish to minimize a piece-wise linear cost function; let x denote the decision variable and c(x), the cost function, is specified as follows: dc(x)dx = 2 for 0 ≤ x ≤ 5; dc(x)dx = 1 for 5 ≤ x ≤ 12; dc(x)dx = 3 for 12 ≤ x ≤ 18. We can model c(x) with integer variables so that the minimization of c(x), subject to various constraints on x, can be solved as an integer program. c(x) = 2x1 + x2 + 3x3 x = x1 + x2 + x3 5y1 <= x1 <= 5 ; 7y2 <= x2 <= 7y1 ; 0 <= x3 <= 6y2 and y1 = 0 or 1; y2 = 0 or 1. 15.066J Summer 2003 62LOGICAL CONSTRAINTS 1. Mutually exclusive alternatives - pick at most one from a set: ixi=1n∑ ≤ 1 2. contingent decisions: if j then must have i: xi >= xj if j, then cannot have i: 1 - xj >= xi 3. set covering - at least one from a set must be chosen: ixi=1n∑ ≥ 115.066J Summer 2003 63ROUTING AND SCHEDULING PROBLEMS The best-known routing/scheduling problem is the so-called traveling salesman problem - given N cities to visit, create a minimum-cost or minimum-length tour that originates in a given city, visits each city exactly once and returns to the city of origin. This problem, while quite important in its own right, is the fundamental sub-problem for more complex vehicle-routing and machine-scheduling problems. The traveling salesman problem is also the standard benchmark for testing and evaluating new combinatorial-optimization algorithms. 15.066J Summer 2003 64CUTTING STOCK PROBLEM A firm that manufactures oil-drilling rigs purchases steel beams from a steel supplier. The steel supplier will deliver a batch of beams at a time. The steel beams come in varying lengths that range from 38 feet to 42 feet, and will vary both within a batch and from batch to batch. The firm uses the beams to make brackets, and the first step in the fabrication process is to cut the beams to the bracket length. The bracket lengths can be 6 feet, 7 feet, 8 feet, or 10 feet. Given a batch of beams and given a set of requirements for brackets, the firm must decide how to cut the beams so as to minimize trim loss. As a simple example, suppose we have on hand 10 forty-foot beams and we need to produce the following: 10 6' brackets 8 7' brackets 15 8' brackets 8 10' brackets How should the beams be cut to minimize material usage? 15.066J Summer 2003 65FORWARD PLANNING FOR AUTOMOBILE COMPONENTS [From Michael J. Chrzanowski’s LFM thesis, Development of a Manufacturing and Business Planning Tool to Aid in Forward Planning, 1993] Consider a manufacturing enterprise that produces a