Integer Programming
IE 8030
Prof. Emily Tucker
Oct. 31, 2024
What’d we cover last time?
• Integer programming intro
– What is it?
– Examples Binary variables 𝑥1 and 𝑥2
• Class scheduling Come up with a constraint that states:
• Knapsack problem you must pick at most one of the two
options
– Constraints that enforce
logical conditions
Today
• Exam return
• IP models
– Facility location
– Discounting (if time)
Exam Return
• Overall
– Average 78%
– Standard deviation of 16%
• Do remember
– This is only one grade (of many) we have this term.
– If score is lower than desired, please come talk to me – we can
come up with a plan to help you be successful.
Next Steps
• Solutions on Canvas
• Who to ask about grading?
– Me!
– Don’t ask Martha about grading; you may ask her about content
• If you think there’s an error in the grading, submit a written
request for a regrade via Canvas
– Note: I will not regrade in office hours
Facility Location
Disney World
Disney World
• Disney has an EMT station that handles all
health emergencies it the park
• They would like to reevaluate where it
should be placed
– The primary consideration is the distance from
rides to the response station
– Rides are grouped in “population centers”
Disney World
• There are 3 candidate
locations for the EMT
station (1-3)
• There are 5 population
centers (A-E)
• The lines represent the
pathway system
Aim to locate exactly 1 EMT
station
Disney World
• We can calculate the “response time”
from any population center to location 𝑖
Table of response times (𝑐𝑖𝑗 )
Disney World
• Formulate an IP
– To minimize the average response time across all population
centers
– We must make sure that every population center is assigned to
the EMT
Disney World
• Sets
𝐼 Set of candidate locations, 𝐼 = {1,2,3}
𝐽 Set of population centers, 𝐽 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}
• Decision variables
– 𝑦𝑖 if EMT station is built at location 𝑖 ∈ 𝐼
– 𝑥𝑖𝑗 if population center 𝑗 ∈ 𝐽 is assigned to station 𝑖 ∈ 𝐼
Disney World
Response time to 𝑗 =
Minimize average 1 σ𝑖∈𝐼 𝑐𝑖𝑗 𝑥𝑖𝑗
min 𝑐𝑖𝑗 𝑥𝑖𝑗
response time 𝐽
𝑗∈𝐽 𝑖∈𝐼
Assign all population
𝑥𝑖𝑗 = 1 , ∀𝑗 ∈ 𝐽
centers to EMT site
𝑖∈𝐼
Select one EMT site 𝑦𝑖 = 1
𝑖∈𝐼
Don’t assign to EMT 𝑥𝑖𝑗 ≤ 𝑦𝑖 ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
site if not open
𝑥𝑖𝑗 ∈ {0,1} ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
Domain constraints
𝑦𝑖 ∈ {0,1} ∀𝑖 ∈ 𝐼
Extension
• What if Disney wanted to select 2 EMT stations?
– How would you adjust the formulation?
Disney World:
Multiple stations
Minimize average 1
min 𝑐𝑖𝑗 𝑥𝑖𝑗
response time 𝐽
𝑗∈𝐽 𝑖∈𝐼
Assign all population
𝑥𝑖𝑗 = 1 , ∀𝑗 ∈ 𝐽
centers to EMT site
𝑖∈𝐼
Select one EMT site 𝑦𝑖 = 1 𝑦𝑖 = 2
𝑖∈𝐼 𝑖∈𝐼
Don’t assign to EMT 𝑥𝑖𝑗 ≤ 𝑦𝑖 ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
site if not open
𝑥𝑖𝑗 ∈ {0,1} ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
Domain constraints
𝑦𝑖 ∈ {0,1} ∀𝑖 ∈ 𝐼
p-Median Problem
• Locate 𝑝 sites
– To minimize average distance from customers to selected sites
– Such that every customer is assigned exactly 1 site
Disney World
• The p-median locates the EMT station(s) so that the
average time is minimized
• But alternatively, we care about the maximum time from
the selected EMT station to any population center
– How about we minimize the maximize response time?
Prep: how to linearize the “max” function
• A constraint that has a max in it isn’t linear
– 𝑥1 ≥ max(4𝑥2 , 3𝑥3 )
– An equivalent linear formulation is:
• 𝑥1 ≥ 4𝑥2
• 𝑥1 ≥ 3𝑥3
Very similar with Min
𝑥1 ≤ min 4𝑥2 , 3𝑥3
Could be linearized as:
𝑥1 ≤ 4𝑥2
𝑥1 ≤ 3𝑥3
How to model? (Min the max)
What we had before (standard p-median)
MinimizeKeep
average 1
minget rid
the constraints but of the𝑐𝑖𝑗 𝑥
objective
𝑖𝑗
response time 𝐽
𝑗∈𝐽 𝑖∈𝐼
Assign all population
𝑥𝑖𝑗 = 1 , ∀𝑗 ∈ 𝐽
centers to EMT site
𝑖∈𝐼
Select p EMT site(s) 𝑦𝑖 = 𝑝
𝑖∈𝐼
Don’t assign to EMT 𝑥𝑖𝑗 ≤ 𝑦𝑖 ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
site if not open
𝑥𝑖𝑗 ∈ {0,1} ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
Domain constraints
𝑦𝑖 ∈ {0,1} ∀𝑖 ∈ 𝐼
Minimize the max response time
• Objective
– Minimize the maximum response time to any population center 𝑗 ∈ 𝐽
Max response time: max [response time 𝑗 ]
𝑗∈𝐽
= max 𝑐𝑖𝑗 𝑥𝑖𝑗
𝑗∈𝐽
𝑖∈𝐼
Will be greater than or equal to
the individual response time to ≥ 𝑐𝑖𝑗 𝑥𝑖𝑗 , ∀𝑗 ∈ 𝐽
any population center 𝑖∈𝐼
Minimize the max response time
• Introduce a new variable
𝜇 ≔ max response time across population centers
• We want to enforce this relationship:
𝜇 = max σ𝑖∈𝐼 𝑐𝑖𝑗 𝑥𝑖𝑗 (but can’t include this directly in the model -
𝑗∈𝐽
because it’s not linear)
• However, we can use this inequality: 𝜇 ≥ 𝑐𝑖𝑗 𝑥𝑖𝑗 , ∀𝑗 ∈ 𝐽
𝑖∈𝐼
max 𝑐𝑖𝑗 𝑥𝑖𝑗 ≥ 𝑐𝑖𝑗 𝑥𝑖𝑗 , ∀𝑗 ∈ 𝐽
𝑗∈𝐽
𝑖∈𝐼 𝑖∈𝐼
Minimize the max response time
Minimize the maximum min 𝜇
response time
Max response time must be
at least the response time
𝜇 ≥ 𝑐𝑖𝑗 𝑥𝑖𝑗 , ∀𝑗 ∈ 𝐽
to all population centers
𝑖∈𝐼
Assign all population
𝑥𝑖𝑗 = 1 , ∀𝑗 ∈ 𝐽
centers to EMT site
𝑖∈𝐼
Select p EMT site(s) 𝑦𝑖 = 𝑝
𝑖∈𝐼
Don’t assign to EMT 𝑥𝑖𝑗 ≤ 𝑦𝑖 ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
site if not open
𝑥𝑖𝑗 ∈ {0,1} ∀𝑖 ∈ 𝐼, 𝑗 ∈ 𝐽
Domain constraints
𝑦𝑖 ∈ {0,1} ∀𝑖 ∈ 𝐼
Disney EMT – fixed charge
• How let’s consider that the higher ups decide to give
a budget 𝐵 rather than max number of locations
(𝑝 = 5)
• Building an EMT station at site 𝑖 ∈ 𝐼 costs 𝑏𝑖
• Adjust the formulation to account for this
Disney EMT – limited allocation
• Consider a BIGGER problem where sets 𝐼, 𝐽 have many more
options than they had before.
• We can open up to 5 EMT locations; however, each EMT station can
only be the primary response station for up to 15 rides.
– Helps to decrease the likelihood of two simultaneous emergencies
needing to be responded to from the same location.
• We will let 𝑐𝑖𝑗 be the response time from location 𝑖 ∈ 𝐼 and location
𝑗∈𝐽
• Formulate as an IP to minimize the average response time
Discount Schemes
Context: if you buy more, you pay less per item
Can’t model with LP
Can model with IP
Equipment Procurement
• Suppose you sell chairs and have a
warehouse and a retail store
Warehouse Retail store
You need to figure out how many units to ship from the warehouse to the store.
• Cost is a major factor.
• However, there’s not a per-unit shipping cost
Shipping costs are a function of the number of trucks
Equipment Procurement
• Each truck costs $2500 to buy
– This could represent the amortized purchase price too
• Suppose
– 𝑥 is your decision on the number of units shipped
– Each truck as a capacity of 500 units
• What’s your integer variable?
– 𝑦: the number of trucks purchased
Equipment Procurement
• Constraint relating units shipped 𝑥 and number of trucks
𝑦?
𝑥 ≤ 500𝑦
• What term is in the objective?
2500𝑦
Equipment Procurement
• Now suppose the truck dealer
offers you a discount
Price of truck 𝒊
• They’ll knock off $100 of the
purchase price of a second
truck
– Another $100 off the purchase
price of the 3rd truck
– Etc.
This means we can no longer capture
the cost with 𝑐𝑦
• Because 𝑐 depends on 𝑦
Equipment Procurement
• Instead, we’ll model the costs with binary variables!
• Decision variables
1 purchase exactly 𝑖 ∈ 𝐼 trucks
𝑦𝑖 ∈ ቊ
0 otherwise
Costs
𝑐1 = 2500
𝑐2 = 𝑐1 + 2400 = 4900 Note – cheaper
than 𝑐𝑦 (2500𝑦)
𝑐3 = 𝑐2 + 2300 = 7200
Etc.
Equipment Procurement
Constraints
Can only select one purchase option Note: do we need this constraint?
𝑦1 + 𝑦2 + 𝑦3 + 𝑦4 + 𝑦5 ≤ 1
Not always
E.g., cheaper to select 𝑦4 than 𝑦1 + 𝑦3
We do if we might want to buy > 5 trucks
Shipping amount bounded by available trucks
𝑥 ≤ 500 ∗ 𝑦1 + 2𝑦2 + 3𝑦3 + 4𝑦4 + 5𝑦5
Equipment Procurement
Alternative formulation
We could also let 𝑧𝑖 be the decision to purchase the 𝑖-th truck
In that case we’d need constraints:
𝑧𝑖+1 ≤ 𝑧𝑖 , ∀𝑖 ∈ 1, … 𝐼 − 1
𝑥 ≤ 500 ∗ 𝑧1 + 𝑧2 + 𝑧3 + 𝑧4 + 𝑧5