You have detections in every frame. Now you need the connections — and from Part 1, the connections are the entire score.
Each candidate link gets a score: how close are these two nuclei in physical space, how well does the motion fit, what does the model's edge head think. Then the obvious thing is to sort by score and take the best ones first.
The obvious thing is a trap.
Why taking the best link first loses
Greedy assignment makes each choice in isolation, and every choice removes options from the choices after it. One confident wrong link early on poisons everything downstream of it.
The clearest version is small enough to hold in your head. Suppose the greedy step takes a link scoring 0.95 — genuinely the highest-scoring single edge available. But taking it consumes a cell that two other links needed, and both of those are now forced onto worse alternatives. Total: 1.45. Solve the same set jointly, decline that 0.95, and the total comes to 2.55.
The greedy answer is not just worse. It is worse because it was locally optimal.
The global version
The fix is to stop choosing one at a time and describe the whole frame-to-frame assignment as a single optimisation. Every candidate link becomes a binary variable — take it or don't. The objective is the total score of everything taken. The constraints encode what a lineage is allowed to look like:
- a cell has at most one parent in the previous frame;
- a cell has at most one child in the next — unless it divided, in which case exactly two;
- appearances and disappearances are allowed, but they cost something, so the solver doesn't use them to wriggle out of hard cases.
That is an integer linear program. The "integer" part is not decoration: you cannot take 0.6 of a link. A cell either connects to that other cell or it does not, and it is precisely that integrality which makes the problem combinatorial rather than a matter of solving a linear system.
Given all candidates at once, the solver returns the highest-scoring set of links that is simultaneously legal — no cell with two parents, no accidental three-way division. Not locally greedy. Globally consistent.
The first implementation was correct and unusable
My first working version used ultrack with an open-source solver. It produced good tracks and found 108 divisions, which was more than anything I'd managed before.
It also took 6.79 minutes per volume, against a budget of roughly 3.6. That is 2.3× over — a correct answer that would fail the submission re-run.
The obvious escape was parallelism, and it did not work either: running multiple workers deadlocked. I spent a while there, found and fixed two real bugs in my own usage along the way, and then parked the whole approach. A correct pipeline that cannot finish is not a pipeline.
The version that shipped uses the public pipeline's ILP formulation via tracksdata with a SCIP backend, which solves the same problem inside the budget. This is the second time in the series that the practical answer was "use the public thing" — and, as in Part 3, I'd rather say so than imply the formulation was mine.
The part that transferred, and the part that didn't
Something worth noticing about the two linking approaches. Greedy linking on my blob detector scored 0.746. ILP linking on the public U-Net scored 0.867. It is tempting to attribute that gap to the linker.
Most of it is the detector. The two changed together, and I never ran the clean factorial — blob-plus-ILP and U-Net-plus-greedy — that would separate them. I am fairly confident the linker is worth real points, because the failure mode it fixes is visible in the output. But "fairly confident" is not "measured," and after what happens in Part 6 I am wary of asserting effect sizes I did not isolate.
Which is a small example of a bigger habit worth having: when you change two things and the number moves, you have learned that the pair helps. You have not learned which one.
What the ILP still can't fix
The solver can only choose among the links you gave it. If the detector missed a nucleus entirely in frame t, there is no candidate edge into it and no candidate edge out of it — nothing for the optimisation to select, however global it is.
That gap is not a small local blemish. It is the single most expensive event in the pipeline, and repairing it was the largest improvement I made myself.