ISE 754 (Fall 2026) 2.4 UFL Heuristics
Watch on YouTube →
Overview
The lecture develops heuristics for the uncapacitated facility location (UFL) problem, where the number and locations of facilities are chosen to minimize transportation cost plus fixed opening costs. It works through LogJam's add, drop, exchange, and hybrid procedures, contrasts UFL with the P-median problem, and shows why machine-capacity constraints require a capacitated model rather than repeated UFL solves. It also explains how to estimate facility fixed cost as the intercept of a regression of operating cost on production rate.
Key takeaways
- UFL jointly selects facility count and locations by minimizing the sum of fixed opening costs and transportation costs; the uncapacitated assumption lets assignments be inferred from the cheapest open site.
- The add heuristic returned sites 3 and 1 at cost 645 in the five-city example, while an exchange step found a 600-cost solution by moving a facility from site 3 to site 4.
- The hybrid UFL procedure combines construction, exchange, and follow-up add/drop checks, helping it find improvements unavailable to greedy add or drop alone.
- P-median fixes the number of facilities but, like UFL, does not enforce machine capacities; the leasing example needed 17 locations to keep maximum utilization below 100% under repeated heuristic solves.
- A facility's fixed cost can be estimated as the intercept of a regression of operating cost on production rate, with the rate-dependent production cost excluded from the UFL fixed-cost input.
- Least squares is appropriate for estimating the regression intercept because its residuals sum to zero; L1 loss instead targets absolute deviations and is associated with median-location behavior.
Chapters
- Unlike the ALA procedure, which takes the number of facilities as an input, UFL determines how many to open.
- Adding facilities generally reduces transportation cost, while each new facility adds fixed cost; the objective is to minimize their sum.
- Because facilities are uncapacitated, each existing location can be assigned to its cheapest open site, so the solution reports sites and total cost rather than a separate allocation.
- The lecture distinguishes mathematical formulations from algorithm pseudocode and implementations, including LogJam functions and their input and output arguments.
- A construction heuristic builds a feasible solution from problem data; an improvement heuristic starts with a feasible solution and searches for a better one.
- UFL is presented as a harder-construction problem: building a feasible solution takes care, but a well-constructed solution can already be relatively good.
- The add procedure starts with no selected sites and evaluates each candidate using its fixed facility cost plus the transportation cost of serving all existing locations.
- In the five-city example, the first selected site is site 3; adding site 1 next lowers total cost from 665 to 645.
- The procedure adds a site only when it strictly improves the objective, so it stops when a third facility cannot reduce the cost below 645.
- The hand calculation, raw Julia implementation, and LogJam UFL add function all return sites 3 and 1 with total cost 645.
- The drop heuristic begins with a facility at every candidate site and removes facilities as long as doing so reduces total cost; its example solution costs 645.
- Add and drop can reach different facility sets and do not generally produce the same objective value, even though both return cost 645 in this example.
- The exchange improvement function takes a feasible solution, such as the add result at sites 3 and 1, and finds a lower-cost solution at 600 by switching a facility from site 3 to site 4.
- LogJam's UFL hybrid combines add, exchange, and further add/drop checks; it returns the 600-cost solution when none of the subsequent checks improves it.
- The P-median problem is a discrete counterpart to ALA: it takes a specified facility count P and transportation costs, rather than facility fixed costs.
- In a machine-leasing example, a $100,000 annual lease is modeled as a fixed cost and a $0.25-per-ton-mile rate helps construct transportation costs.
- UFL selects six machine locations, but three exceed the 2-million-unit annual capacity; a P-median run with seven machines still leaves a machine above 100% utilization.
- Brute-force increases to the facility count require 17 machines to get maximum utilization below 100%, illustrating that UFL and P-median do not enforce capacity constraints.
- The correct formulation is capacitated facility location, which incorporates capacity limits directly instead of treating an infeasible UFL result as a valid solution.
- Fixed facility cost is rarely supplied directly in practice; it can be estimated from historical annual operating costs across facilities of different production rates.
- Separate each facility's total production cost into a rate-dependent variable component and a fixed component by fitting a regression line.
- The regression intercept K estimates the fixed cost that does not vary with production rate; the production-rate-dependent term is excluded from the UFL fixed-cost input.
- For the example production data, the L2 least-squares fit is used to estimate the fixed-cost intercept, while an L1 absolute-deviation fit gives a different result.
- Least squares produces residuals that sum to zero, matching the goal of fitting the production data without a net over- or under-estimate.
- L1 loss is useful for the median location problem, but the Asheville-to-California example shows that it can leave the location objective unchanged, unlike L2; the appropriate loss depends on the modeling goal.
Transcript excerpt
0:04 For this lecture, we're starting our discussion where we're actually going to be solving the location problem as a discrete problem. Everything we've done to date has been for a continuous version of the problem. Today, we're going to be talking about a very particular type of problem called the uncapacitated facility location problem. And to solve it, we're going to use a variety of different heuristics. This figure shows basically what the problem that we're going to be dealing with is. What it shows are two different cost. The dotted line represents transportation cost. And just like we saw with the ALA procedure from the previous lecture, if we have one facility, the transportation cost serving all of
0:52 existing customers is at its highest level. With two, each existing facility can be allocated to just one of the two. And when we keep doing that, we get a reduction in the total transportation cost, which is typically proportional to the total distance. So, as we increase the number of new facilities, we get the expected decrease in the transportation cost. In terms of the ALA procedure, we basically had the number of facilities as given as outside of the problem. One of the inputs to the ALA procedure was how many of the facilities do we want to actually locate. So, we gave the problem
1:39 the number. More generally, it would be better if we could have the number actually determined as part of the procedure itself. And that is exactly what the UFL procedure does. It actually adds the cost of every time we added additional new facility, it adds an additional uh fixed facilities cost. So, every time we add a facility, it goes up in direct proportion. And then what we're looking at as a solution to the UFL problem is given the
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Michael G. Kay.