A Primal-Dual Solver for Large-Scale Tracking-by-Assignment
We propose a fast approximate solver for the combinatorial problem known as tracking-by-assignment, which we apply to cell tracking. The latter plays a key role in discovery in many life sciences, especially in cell and developmental biology. So far, in the most general setting this problem was addressed by off-the-shelf solvers like Gurobi, whose run time and memory requirements rapidly grow with the size of the input. In contrast, for our method this growth is nearly linear. Our contribution consists of a new (1) decomposable compact representation of the problem; (2) dual block-coordinate ascent method for optimizing the decomposition-based dual; and (3) primal heuristics that reconstructs a feasible integer solution based on the dual information. Compared to solving the problem with Gurobi, we observe an up to~60~times speed-up, while reducing the memory footprint significantly. We demonstrate the efficacy of our method on real-world tracking problems.
Code (2)
Tasks
Cell TrackingSimilar Papers 제목 키워드 기반
Self-Certifying Primal-Dual Optimization Proxies for Large-Scale Batch Economic Dispatch
Recent research has shown that optimization proxies can be trained to high fidelity, achieving average optimality gaps under 1% for large-scale problems. However, worst-case analyses show that there exist in-distribution…
Distributed and time-varying primal-dual dynamics via contraction analysis
In this note, we provide an overarching analysis of primal-dual dynamics associated to linear equality-constrained optimization problems using contraction analysis. For the well-known standard version of the problem: we …
Distributed OptimizationLarge Scale Model Predictive Control with Neural Networks and Primal Active Sets
This work presents an explicit-implicit procedure to compute a model predictive control (MPC) law with guarantees on recursive feasibility and asymptotic stability. The approach combines an offline-trained fully-connecte…
Model Predictive ControlAn Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling
Quadratic programs (QPs) arise in various domains such as machine learning, finance, and control. Recently, learning-enhanced primal-dual hybrid gradient (PDHG) methods have shown great potential in addressing large-scal…
Implicit Primal-Dual Interior-Point Methods for Quadratic Programming
This paper introduces a new method for solving quadratic programs using primal-dual interior-point methods. Instead of handling complementarity as an explicit equation in the Karush-Kuhn-Tucker (KKT) conditions, we ensur…