Optimality guarantees for min-cost multi-commodity network-flow data association in online multi-object tracking

Online multi-object tracking associates per-frame object detections with existing trajectories. Yang, Wu and Jia (IEEE TIP 2017) formulated this association over a sliding temporal window as a min-cost multi-commodity network flow: each existing trajectory is a unit-demand commodity routed through a layered, time-ordered graph of detections, together with a dummy commodity that admits newly appearing objects. The authors state, without proof or citation, that the resulting integer linear program is NP-hard and that its linear programming relaxation is not guaranteed to be integral, so the paper solves it by column generation, keeping the best integer solution encountered and certifying sub-optimality only empirically, per instance, as the gap between that solution and the LP lower bound. Whether any theoretical guarantee holds for the structured instance classes that actually arise in tracking — integrality of the relaxation under verifiable conditions, a bounded integrality gap, or a worst-case sub-optimality bound for the column-generation solver — or whether such guarantees are ruled out by inapproximability or an unbounded integrality gap on those structured classes, has not been established. This problem asks for exactly that settlement.

Background

Multi-object tracking (MOT) in video is typically handled by tracking-by-detection: an object detector produces bounding boxes per frame, and the tracker must decide which detections belong to which physical object over time. This decision step, data association, can be formulated as a combinatorial optimization problem. In network-flow formulations, each detection is a node in a directed acyclic graph whose layers correspond to frames and whose edges connect detections in successive frames; a trajectory is a path through this graph, and detection-level exclusivity (a detection belongs to at most one object) becomes a capacity constraint. In the single-commodity version, all trajectories share one flow field and the min-cost flow objective encodes the affinity between linked detections; because the min-cost flow constraint matrix is totally unimodular (every extreme point of the associated linear program is integral), these formulations can be solved exactly in polynomial time, as in the global data-association method of Zhang, Li and Nevatia (CVPR 2008) and the k-shortest-paths tracker of Berclaz, Fleuret, Turetken and Fua (TPAMI 2011). Things change when each object gets its own commodity. Yang, Wu and Jia (IEEE TIP 2017) proposed a hybrid data-association framework in which, within a temporal window of length $\Delta t$, every existing trajectory $T_k$ is a distinct commodity that must send one unit of flow ($d_k = 1$) from a source to a sink, and a dummy commodity with a larger budget ($d_0 = 20$) absorbs detections of newly appearing objects; edge costs come from online-learned, target-specific appearance similarities (with a decay factor $\eta$ discounting long-range predictions). With multiple commodities the constraint matrix is no longer totally unimodular: the authors assert, without proof or citation, that the integer problem is NP-hard, and that the optimal solution of its linear programming (LP) relaxation is not guaranteed to be integral — fractional LP optima have no direct interpretation as trajectories. To track online, the authors solve the LP by column generation, an LP decomposition in which the linear program is written over trajectory-path variables (columns) and solved over a growing subset: at each iteration a shortest-path pricing problem finds a path column with negative reduced cost (a path that would strictly improve the LP objective if added) to add, and the process terminates when no such column exists. The solver keeps the best integer solution encountered during this process; since the final LP value lower-bounds the integer optimum, the difference between the retained integer objective and the LP bound is a certificate of near-optimality. The authors report that these certificates are empirically small (often zero), but they are per-instance observations with no theoretical content. In fact the general situation is provably bad: integer multi-commodity flow is NP-complete even for two commodities (Even, Itai and Shamir, 1976), and the lifted disjoint paths problem used by later trackers — a disjoint-paths formulation augmented with extra long-range edges that add costs depending on whether two non-adjacent nodes are assigned to the same trajectory or to different trajectories — was proven NP-hard by reductions from integer multi-commodity flow and from 3-SAT, through a line-graph-like transformation of an arbitrary digraph that yields neither layered temporal detection networks nor per-trajectory unit-demand commodities with a dummy commodity (Hornakova, Henschel, Rosenhahn and Swoboda, ICML 2020). What is not known is the intermediate, structure-exploiting regime: tracking instances are not adversarial — they live on layered, time-ordered graphs with unit capacities, one unit-demand commodity per trajectory plus a dummy commodity, and costs produced by learned similarity models. Whether integrality of the LP relaxation, a bounded integrality gap (the worst-case ratio between the integer optimum and the LP bound), or a worst-case sub-optimality bound for the column-generation heuristic can be proven for such structured classes — or whether inapproximability or an unbounded integrality gap already holds inside these classes — is the open question. It matters practically: an integrality or bounded-gap result would turn heuristic near-optimal association into certified or exactly solvable association for flow-based trackers, and the same question recurs in adjacent association formulations (set-packing column generation for tracking, lifted disjoint paths, and the lifted multicut problem, a graph-partitioning objective carrying the same kind of long-range edge terms), all of which currently rely on per-instance LP-gap certificates rather than guarantees.

Problem Statement

For the min-cost multi-commodity network-flow formulation of online multi-object tracking data association introduced by Yang, Wu and Jia (2017) — a layered, time-ordered directed acyclic graph of detections within a temporal window, one unit-demand commodity per existing trajectory plus a dummy commodity with budget $d_0$ ($d_0 = 20$ in the source's experiments) for newly appearing objects, detection-exclusivity capacities, and real-valued edge costs computed from online-learned target-specific similarities — settle its theoretical optimality status on the instance classes that arise in practice. The status may be settled positively — by a theorem giving verifiable conditions on the instance structure or cost regime (for example, conditions on the layered temporal graph, the commodity pattern, or the learned cost vectors) under which the LP relaxation of the formulation — the master LP of its Dantzig-Wolfe path reformulation — is integral, or has a bounded integrality gap, or by a theorem giving a worst-case sub-optimality bound for the column-generation solver of Yang et al. (which retains the best integer solution found while generating path columns by shortest-path pricing) on such a class of instances, as a function of instance parameters, where the bound is non-trivial: it must not be a mere a priori majorant obtained by multiplying the largest cost magnitude by the number of admissible path columns, nor the maximum of the solver's own per-instance certificate over a finite parameter box, and it must hold for every instance of the class — or negatively, by inapproximability, or an unbounded integrality gap, established for the formulation itself on a formally defined class of layered temporal tracking instances. For a negative settlement, restating that general integer multi-commodity flow is NP-complete even for two commodities, invoking the hardness of lifted disjoint paths (whose reductions transform an arbitrary digraph, not a layered temporal tracking network), or repeating the source's own uncited assertion that the ILP is NP-hard does not settle the question; and plain NP-hardness of exact optimization would not by itself rule out a bounded integrality gap or approximation algorithms, so only inapproximability or an unbounded gap supports the conclusion that per-instance certificates are the best achievable.

Any answer must define its instance class formally and independently of the property being proved — a class defined as those instances whose LP relaxation happens to be integral, or one collapsed to a degenerate parameter choice such as a single existing trajectory over two frames, does not qualify — and must show that the class is non-vacuous and contains structured instances of the kind the source actually solves: a layered temporal detection DAG over a fixed window ($\Delta t = 10$ in the reported experiments), from a handful to a few tens of concurrent objects per frame, one unit-demand commodity per existing trajectory plus the dummy commodity with budget $d_0 = 20$, a sparsified permissible transition set, and real-valued costs of the online-learned target-specific similarity model; the class need not be restricted to those exact parameter values. It must faithfully embed the full formulation (all commodities including the dummy commodity, the exclusivity constraints, and the general real cost model), and the claimed property must be established for the formulation itself rather than for a simplified surrogate. The paper itself poses no guarantee question as future work — its only stated future direction is learning more effective edge costs — so this target is derived from limitations the source acknowledges: that the LP relaxation 'is not guaranteed to be integral', and that the sub-optimality certificates reported for the column-generation solver are empirical and per-instance.

References

1. Min Yang, Yuwei Wu, Yunde Jia. A Hybrid Data Association Framework for Robust Online Multi-Object Tracking. IEEE Transactions on Image Processing 26(12):5667-5679, 2017. DOI: 10.1109/TIP.2017.2745103; arXiv:1703.10764; https://arxiv.org/abs/1703.10764
2. S. Even, A. Itai, A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing 5(4):691-703, 1976. DOI: 10.1137/0205048; https://doi.org/10.1137/0205048
3. Li Zhang, Yuan Li, Ramakant Nevatia. Global data association for multi-object tracking using network flows. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008, pp. 1-8. DOI: 10.1109/CVPR.2008.4587584; https://doi.org/10.1109/CVPR.2008.4587584
4. J. Berclaz, F. Fleuret, E. Turetken, P. Fua. Multiple Object Tracking Using K-Shortest Paths Optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(9):1806-1819, 2011. DOI: 10.1109/TPAMI.2011.21; https://doi.org/10.1109/TPAMI.2011.21
5. Shaofei Wang, Steffen Wolf, Charless Fowlkes, Julian Yarkony. Tracking Objects with Higher Order Interactions using Delayed Column Generation. arXiv:1512.02413, 2015; published at AISTATS 2017 (as "Tracking Objects with Higher Order Interactions via Delayed Column Generation"), PMLR 54:1132-1140; https://arxiv.org/abs/1512.02413; https://proceedings.mlr.press/v54/wang17c.html
6. Andrea Hornakova, Roberto Henschel, Bodo Rosenhahn, Paul Swoboda. Lifted Disjoint Paths with Application in Multiple Object Tracking. Proceedings of the 37th International Conference on Machine Learning (ICML), 2020, PMLR 119:4364-4375. arXiv:2006.14550; https://arxiv.org/abs/2006.14550; https://proceedings.mlr.press/v119/hornakova20a.html
7. Andrea Hornakova, Timo Kaiser, Paul Swoboda, Michal Rolinek, Bodo Rosenhahn, Roberto Henschel. Making Higher Order MOT Scalable: An Efficient Approximate Solver for Lifted Disjoint Paths. ICCV 2021, pp. 6310-6320. DOI: 10.1109/ICCV48922.2021.00627; arXiv:2108.10606; https://arxiv.org/abs/2108.10606
8. Yanmei Dong, Mingtao Pei, Xiaofeng Liu, Meng Zhao. Scene-Specific Multiple Cues Integration for Multiperson Tracking. IEEE Transactions on Cognitive and Developmental Systems 12(3):511-518, 2020. DOI: 10.1109/TCDS.2019.2928338; https://doi.org/10.1109/TCDS.2019.2928338
9. Patrick Emami, Panos M. Pardalos, Lily Elefteriadou, Sanjay Ranka. Machine Learning Methods for Data Association in Multi-Object Tracking. ACM Computing Surveys 53(4):69:1-69:34, 2021 (first published online August 2020). DOI: 10.1145/3394659; https://doi.org/10.1145/3394659
10. Pratyusha Musunuru, Yuchao Li, Jamison Weber, Dimitri Bertsekas. An Approximate Dynamic Programming Framework for Occlusion-Robust Multi-Object Tracking. arXiv:2405.15137, 2024; https://arxiv.org/abs/2405.15137