73 220 Lecture15 Soln

Integer Programming: Binary Decision Variables 73-220-F05 Lecture 15 – Solution

1

Set Covering Example There are 6 cities in Kilroy County. The county must determine where to build central fire stations. The county wants to build the minimum number of central fire stations needed to ensure that at least one fire station is within 15 minutes (driving time) of each city. The times (in minutes) required to drive between the cities in Kilroy county are given in the table. Formulate an IPP that will tell Kilroy how many fire stations should be built and where they should be located.

2

Set Covering Example contd. From City 1 City 2 City 3 City 4 City 5 City 6

To City 1 City 2 City 3 City 4 City 5 City 6 0 10 20 30 30 20 10 0 25 35 20 10 20 25 0 15 30 20 30 35 15 0 15 25 30 20 30 15 0 14 20 10 20 25 14 0

3

Formulation The first step is to determine the cities which are within 15 minutes of each of the cities. City 1: City 2: City 3: City 4: City 5: City 6:

1,2 1,2,6 3,4 3,4,5 4,5,6 2,5,6

4

Formulation Decision Variables

X(i) = 1 if a fire station is built in city i, i=1,2,3,4,5,6 = 0 otherwise

Objective Function

Minimize z = x(1) + x(2) + x(3) + x(4) + x(5) + x(6)

Constraints City 1: City 2: City 3: City 4: City 5: City 6:

x(1) + x(2) > 1 x(1) + x(2) + x(6) > 1 x(3) + x(4) > 1 x(3) + x(4) + x(5) > 1 x(4) + x(5) + x(6) > 1 x(2) + x(5) + x(6) > 1

x(i) - binary

5

Capacitated Lot Sizing Determine a production schedule given the following information Four-week demand: 20, 30, 40, 10 Setup cost: $200 Setup time: 6 hours Processing time: 1 hour/unit Holding cost: $15/unit/week Production capacity: 40 hours/week If you produce in week 4, you have to produce at least for 20 hours and not more than 30 hours.

6

Formulation Decision Variables: xi = quantity produced in week i, (i=1,2,3,4) yi = 1 if there is production in week i, (i=1,2,3,4) Ii = inventory remaining at the end of week i Objective Function: Min 200 (y1 + y2 + y3 + y) + 15(I0 + I1)/2 + 15(I2 + I3 + I4) Note: I0 is the starting inventory for the whole planning period. Constraints: Week 4 Production and inventory equations: x1 – I1 = 20 I1 + x2 –I2 = 30 I2 + x3 – I3 = 40 I3 +x4 – I4 = 10 Production capacity xi ≤ 34 yi i=1,2,3,4

x4 > 20 y4 x4 < 30 y4

7

Fixed Charge Problems Transportation from m warehouses to n customers. There is a unit transportation cost Cij between each warehouse i and customer j, and a fixed charge Fi if warehouse i is leased. Each warehouse has a fixed capacity, Ui. The problem is to decide which set of warehouses to lease to meet all customer demands, Dj.

8

Formulation ●

Decision variables – yi = 1 if warehouse i is leased; 0 otherwise – xij -- # units to ship from warehouse i to customer j.

●

Objective function – Min cost = ∑iFiyi + ∑ i∑j Cijxij

●

Constraints – Supply at warehouse i: ∑j xij < Uiyi – Demand at customer j: ∑i xij = Dj – Nonnegativity for xij, binary for yi.

9