ISE 754 (Fall 2026) 2.7 Discrete Location and MILP

Overview

The lecture explains how mixed-integer linear programming (MILP) converts discrete location and allocation decisions into optimization models, then demonstrates implementation in Julia with JuMP and the open-source HiGHS solver. Examples show MILP's global-optimality guarantees and its ability to add capacity constraints directly, alongside set-covering and bin-packing applications where solver performance and heuristics differ substantially.

Key takeaways

MILP enforces discrete choices that continuous linear programming cannot represent, and integer restrictions can worsen the best objective value by reducing the feasible region.
JuMP lets Julia models closely mirror mathematical programs, and HiGHS offers an open-source solver suitable for many practical MILP problems.
A heuristic can find a useful facility-location solution but does not generally certify global optimality; a completed MILP solve does, while an optimality gap supports stopping early.
Modeling machine capacity directly reduced the example from 17 machines costing just under $1.8 million to an optimal feasible solution of eight machines costing just under $1.35 million.
Set covering is often tractable even for thousands of objects because its LP relaxation is close to the integer solution, whereas bin packing can become hard at several hundred objects and is often better served by heuristics.

Chapters

0:00 From Linear Programming to Discrete MILP Decisions

A continuous linear program can yield fractional decisions, such as 3.5 units, while personnel and facility choices often require discrete or yes/no decisions.
Restricting the feasible region to integer points changes the example's maximum objective from 31.67 to 30, since added constraints cannot improve a maximization solution.
The lecture applies MILP to the uncapacitated facility location problem, alongside add-drop and hybrid heuristics introduced earlier.

5:37 Solving Facility Location with Julia JuMP and HiGHS

Julia's JuMP package expresses variables, objective functions, coverage constraints, and linking constraints in code close to the mathematical formulation.
The example uses the open-source HiGHS solver, which provides much of the needed MILP functionality without the cost of commercial solvers.
For five cities along I-40, the model selects sites 1 and 4 for a total cost of 600, matching the earlier heuristic result while certifying global optimality if solved to completion.
MILP can take exponential time on difficult instances; solvers use optimality gaps to stop when the current solution is sufficiently close to the bound.

12:03 Adding Capacity Constraints to Facility Location

Ignoring capacity produced an infeasible six-machine solution; adding machines by trial and error required 17 machines and cost just under $1.8 million.
Adding a capacity constraint directly to the MILP model yields a feasible optimum of eight machines, maximum utilization of 85.7%, and a cost just under $1.35 million.
Heuristics remain useful for problems too large for exact optimization and can provide a warm start or bound to help a MILP solver.

16:51 Set Covering and Bin Packing in Logistics

Set covering chooses the fewest sets that cover every object; in the six-object example, sets M2 and M4 together cover all objects.
A North Carolina transmitter-location example covers every county with five transmitters, allowing counties to be covered more than once.
Bin packing minimizes the number of equal-capacity bins needed for a collection of objects, with freight containers and machine allocation as applications.
Set covering often scales well to thousands of objects because its LP relaxation is close to the integer optimum, while bin packing can become difficult beyond several hundred objects and often relies on heuristics.

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.