Lecture 4.2 Recap

4.2: Assignment and Transportation Problems · ISE 754, Fall 2026 · in class 15 October 2026

A recap answers what students found most difficult in their pre-class review of the lecture, along with anything the instructor adds. Blue Lecture panels quote the lecture; orange Another view panels look at the same idea from another side.

What changed in the lecture

Added by the instructor Lecture 4.2, Secs. 1, 2 and 4, revised 14 and 15 October

Lecture 4.2 was revised after the version the review was built on, the one posted on 14 October. The largest changes are in Sec. 4, where the network figures now carry everything needed to state a small minimum cost network flow problem, and Example 7 is a new example, the earthquake relief network, in place of the three-level network, which was dropped.

Lecture New: Fig. 10, and how an arc's numbers read

The five-node network of Fig. 8, each node labeled with its net supply: 6 at node 1, 2 at node 2, 0 at nodes 3 and 4, and minus 8 at node 5. Arc labels: 1 to 2, 2; 1 to 3, 3; 2 to 5, 5, 9; 2 to 4, 4, 3; 3 to 5, 1, 3; 4 to 5, 3, infinity, 1. A key at the right shows an arc from i to j labeled c, u, l above and c, infinity, 0 below. — The lecture's Fig. 10. “The network of Fig. 8 with the bounds of Ex. 6(c), each node labeled with its net supply. Each arc is labeled \(c, u, l\): its cost, its upper bound and its lower bound, a default left off the end, as the key at the right reads. Arc (4,5)’s lower bound of 1 is the only lower bound above zero, and arcs (2,4), (2,5) and (3,5) carry the only upper bounds below infinity.”

“By default an upper bound is infinity and a lower bound is zero, and the columns are needed only for values other than the defaults: an upper bound less than infinity goes in the fourth column and a lower bound greater than zero in the fifth.”

Another view Reading Fig. 10's labels

A label lists the cost first, then the upper bound, then the lower bound, and stops as soon as everything left is a default, the key's lower line, \(c, \infty, 0\). So each arc shows only as many numbers as it needs:

Arc	Label	Cost \(c\)	Upper bound \(u\)	Lower bound \(l\)
(1,2)	2	2	\(\infty\), the default	0, the default
(2,5)	5, 9	5	9	0, the default
(4,5)	3, ∞, 1	3	\(\infty\), written out	1

Arc (4,5) writes its \(\infty\) out only because a lower bound comes after it. The upper bound comes before the lower because, in the lecture's words, “the lower bound’s default of zero is more often what a problem wants than the upper bound’s of infinity.”

Example 7 is new: earthquake emergency response. The earlier Example 7, a three-level network, was dropped.

The new example is the lecture’s last. Its network, as given, cannot deliver what the hospital needs, so the question becomes which arc’s capacity to raise. It is reviewed in the two panels below, and the example it replaced is quoted after them for reference.

Lecture New: Example 7, earthquake emergency response

“Determine the least-cost flows, as Model 3, that deliver the 700 pallets the Field Hospital needs through the relief network of Table 6; if the network as it stands cannot deliver them, determine which arc’s capacity to raise, and the least total cost with it.”

The relief network. The Regional Warehouse (RW, 500) ships to the Local Airfield (LA) and the Central Distribution Hub (CH); the Specialty Pharmacy (SP, 200) ships to CH; LA and CH ship to the Staging Area (SA); SA ships to the Field Hospital (FH, minus 700). LA, CH and SA have a net supply of zero. Each arc carries its cost and bounds in the same c, u, l form, with a key at the top right. — The lecture’s Fig. 12, the relief network, its arcs labeled the same way as Fig. 10’s: RW and SP supply 500 and 200 pallets, the Field Hospital needs 700, and the airfield, the hub and the staging area only pass pallets through.

“In looking at the graph, at most 500 units can flow into Node 4 and then on to Node 5. Since only 150 units can travel from 3 to 5, the total of 650 is less than the required demand of 700 at Node 6.”

“Raising road (1,4) instead delivers all 700 pallets for 8,950, 150 less than raising the helicopter’s: the 50 pallets the path 1 → 3 → 5 carried at 4 + 10 = 14 a pallet go by road, 1 → 4 → 5, at 6 + 5 = 11, a saving of 3 × 50 = 150, the Triangulate check of Lecture 1.2. The count before Code block 68, at most 650 pallets into node 5 against the 700 needed, is the Bounds check: it explains the infeasibility without the linear program.”

Another view Example 7 in three runs

Flows in pallets, from Model 3 with each arc’s bounds. “Into SA, at most” is the count the lecture makes before solving: the hub can receive at most 300 + 200 = 500 and the helicopter carries at most 150.
The network	Into SA, at most	RW→LA	RW→CH	SP→CH	LA→SA	CH→SA	SA→FH	Least total cost
As it stands	650	no flow delivers 700						infeasible
Helicopter (3,5) raised to 200	700	200	300	200	200	500	700	9,100
Road (1,4) raised to 350	700	150	350	200	150	550	700	8,950

Either raise adds the missing 50 pallets of capacity into the staging area, and both plans deliver all 700. They differ only in which way those 50 go: by helicopter, 4 + 10 = 14 a pallet, or by road through the hub, 6 + 5 = 11. Each total is its flows times their costs: for the road, 4 × 150 + 6 × 350 + 3 × 200 + 10 × 150 + 5 × 550 + 2 × 700 = 8,950. The convoy’s lower bound of 100 on (4,5) is met in both, at 500 and 550.

Lecture Dropped: the earlier Example 7, a three-level network

Quoted from the version the review was built on. It is no longer in the lecture.

“Two plants, which can supply 65 and 80 units, ship to the three supply nodes of Ex. 4, now DCs that only pass flow through, at costs per unit of 4, 6 and 5 from the first plant to the three DCs and 3, 8 and 2 from the second; the DCs ship to Ex. 4’s demand nodes at its costs. Determine the least-cost flows through the network, and compare the result with the transportation problem the network reduces to.”

“The plants supply the customers at a least total cost of 1,320, the same as the transportation problem on the cheapest two-leg costs”

Also changed

Sec. 1 finds the places first. “The streets of Ex. 1 are found the way they would be for any problem: the places that matter are located first, a box is put around them, and the streets inside the box are downloaded.” Code block 1 looks up the two buildings by their addresses, and Code block 2 puts the box around them.
Example 3 is Unter on Raleigh’s streets, its twelve drivers and ten passengers drawn from the Census block groups within 3 miles of downtown. Greedy now comes out 1.7% above the optimum, 36.17 min of pickups against 35.55.
Every node in Sec. 4’s figures is labeled with its net supply, a zero included, and Fig. 8 also with its role. Fig. 11 is new: Example 6(d)’s two modes between nodes 1 and 4, the cheaper labeled 6, 20, its cost and the 20 units it can carry.
Numbering. Figs. 10 and 11 are new, so the relief network is Fig. 12, and Sec. 4’s code blocks from 61 on are renumbered around the two new drawings.

When greedy is preferred to a linear program

Asked in the review Lecture 4.2, Secs. 2 and 3

The questionWhen is a greedy procedure preferred to a linear program?

Lecture Why build a greedy procedure at all

“The greedy procedure comes first, in Julia, even though the linear program is the better approach. Developing a greedy procedure is not something this course asks for, but in research, small problems often come up that need some answer, and a greedy procedure can be the quickest way to get one.”

“There might be a better way of assigning the cars than this, but when an answer is needed, a greedy procedure at least gives a feasible solution, if not an optimal one, which makes it handy to have.”

Lecture When the optimum is hard to find, and when it is not

“Were the optimum hard to find, as it is for the uncapacitated facility location problem of Lecture 2.4, a heuristic would be welcome, and there it was: Lecture 2.7 found the heuristic within a small fraction of one percent of the optimum of the mixed-integer linear program. Here, even on a small problem, the greedy approach is a lot worse than the optimum, and the optimum is easy to get because the problem is a linear program, which today’s solvers handle at sizes far beyond any example here, and so there is no reason to accept greedy’s answer.”

“That is not the case of the ADD procedure for the uncapacitated facility location problem, where the heuristic really is pretty good; here the difference is significant enough that the linear program is definitely wanted. The good news is that the linear program is very effective and easy to implement, so using it is no burden.”

Lecture Not every greedy procedure falls short

“The greedy procedure is fast but not always optimal for the transportation problem. By contrast, Dijkstra’s shortest path procedure of Lecture 4.1 and the simplex method for LP are optimal greedy procedures.”

“There is one greedy procedure that does give the optimal solution to both the linear assignment and the transportation problems, and that is linear programming itself: the simplex method is greedy in that it always makes the most immediately favorable move. So the claim is not that greedy never works, only that this greedy procedure does not.”

Lecture And a greedy answer can be wrong without saying so

“With fewer cars than passengers, the first two rows of D only, the greedy function still returns a solution, but it is not feasible: the third passenger has not been assigned a car. The code runs without complaint and says nothing, so knowing that the answer is infeasible is left to whoever runs it.”

Another view The lecture's greedy answers against their optima

The first four are this lecture’s, each a linear program, which the lecture solves to optimality in one call. The last is a facility location problem, whose optimum takes a mixed-integer program. Of the first, the lecture notes: “Unter’s 3 × 3 matrix of Ex. 2 was chosen to make greedy look especially bad.”
Problem	Greedy	Optimum	Greedy above
Example 2, Unter’s three cars (distance)	12	10	20%
Example 3, Unter on Raleigh’s streets (pickup minutes)	36.17	35.55	1.7%
Example 4, the tableau (cost)	1,030	970	6.2%
Example 5(b), DCs at 1.5 million people (person-mi)	83,033,122	80,752,829	2.8%
Lecture 2.7, the heuristic of Lecture 2.6 against the MILP (cost)	726,035,315	725,479,140	0.077%

Where the optimum is one linear program away, greedy came out above it every time, and by up to 20%, though not on every instance: on 300 tableaux of Example 4’s size, dealt at random as the tableau below deals them, greedy found the least cost 161 times. Where the optimum is hard to get, the heuristic came within 0.077% of it. That is the lecture’s line between the two: a greedy procedure earns its place when the optimum is hard to find or any feasible answer will do, and not when the problem is a linear program.

Greedy, one pick at a time

Added by the instructor Lecture 4.2, Sec. 3, Ex. 4(a) and Fig. 6

Lecture The procedure

“Greedy Transportation Procedure: Continue to select the lowest cost supply until all demand is satisfied.”

“The greedy approach picks the smallest cost and assigns as much as it can on that arc, then looks for the next least cost and assigns as much as it can of that, and keeps going until all of the demand has been satisfied from the supply.”

Another view Fig. 6, to work by hand

Click any cell to ship on it, as much as the cell can carry: the smaller of the supply its row has left and the demand its column still needs. A cell whose row has nothing left, or whose column needs nothing more, cannot ship and says why. Each cell holds its cost per unit at the corner and, once units are shipped on it, the units in bold and, in the circle, the step that shipped them. Greedy always takes the least cost still available: Greedy step makes that pick, and Hint outlines the least cost. A new tableau deals out another problem of the same size. Once all the demand is met, the plan’s cost is set against greedy’s and against the linear program’s least cost.

Try it on Example 4. Greedy’s plan costs 1,030. Find the step where taking the second-lowest cost instead of the lowest, and letting greedy finish, gives a plan that costs less.

What to add up on a shipping plan

Added by the instructor Lecture 4.2, Sec. 3, Ex. 4(b)

Lecture The plan balances, row by row and column by column

The lecture’s Code block 41: the linear program’s shipments for Example 4, at a total cost of 970.
Node	4	5	6	7	Shipped	Supply
1	5	20	30	0	55	55
2	40	0	0	0	40	50
3	0	0	0	30	30	40
Shipped	45	20	30	30
Demand	45	20	30	30

“The shipments of Code block 41 balance: each supply node ships no more than its supply (in its row, Shipped against Supply), and each demand node receives exactly its demand (in its column, Shipped against Demand); and the 145 units of supply less the 125 shipped leaves 20 unshipped, 10 at node 2 and 10 at node 3. That the parts add up to the whole is the Balance check of Lecture 1.2.”

“Row (a), supply, lets a supply node ship less than its supply, so total supply can exceed total demand and the excess is simply not shipped; row (b), demand, meets each demand exactly.”

Another view Why the columns alone are not enough

Take the plan above and move 15 of node 4’s units from node 2, at 9 a unit, to node 1, at 8:

Node	4	5	6	7	Shipped	Supply
1	20	20	30	0	70	55
2	25	0	0	0	25	50
3	0	0	0	30	30	40
Shipped	45	20	30	30
Demand	45	20	30	30

Every column still adds to its demand and 125 units are shipped in all, so the columns and the total pass. The cost falls to 955, below the optimum’s 970, and still inside the lecture’s bracket of 930 to 1,030. Only node 1’s row, 70 against a supply of 55, shows that the plan cannot be carried out. And expecting every row to equal its supply would refuse the lecture’s own plan, whose rows ship 55, 40 and 30 of 55, 50 and 40.