Integer Programming: Binary Decision Variables 73-220 Lecture 15
1
Agenda ●
Review of last class. – Sufficient and necessary conditions by binary decision variables. – Solutions to the four homework problems.
Binary decision variables. ● Next Class ●
2
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.
3
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
4
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.
5
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.
6
If-Then Constraints If you invest in stock 1, then you must invest in stock 2. Let yi = 1 if you invest in stock i, i=1,2 = 0 otherwise y2 > y1
7
Only If - Constraints Invest in stock 2 only if you invest in stock 1. Let yi = 1 if you invest in stock i, i=1,2 = 0 otherwise y1 > y2
8
If-and-only-if Constraints If you invest in stocks 1 and 2, you must invest in stock 3. In addition, you can invest in stock 3 only if you invest in stocks 1 and 2. Let yi = 1 if you invest in stock i, i=1,2,3 = 0 otherwise We can easily write a non-linear constraint as follows: y3 = y1(y2) Let us linearize this. We will need 2 constraints to linearize this. y3 < (y1 + y2)/2 y3 > y1 + y2 -1 9
Next Class ●
Do more questions from Chapter 8.
●
More applications of IP models YOU LEARN DECISION ANALYSIS BY DOING DECISION ANALYSIS!!
10