This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth of the Hessian’s support graph, its volume growth, and an appropriate margin parameter. Under suitable structural conditions, the overall complexity scales linearly with the problem dimension. To demonstrate the practical impact of our approach, we introduce a novel framework for joint forecasting and outlier detection by extending exponential smoothing to time series with outliers. Computational experiments on both synthetic and real data sets show that our method significantly outperforms state-of-the-art solvers.

[Github link] [paper link]

Gene regulatory networks (GRNs) orchestrate cellular decision-making and survival strategies. Inferring the structure of these networks from high-dimensional transcriptomics data is a central challenge in systems biology. Traditional approaches to GRN inference, such as the graphical lasso and its joint extensions, rely on ℓ₁ penalty to induce sparsity but can bias network recovery and require extensive hyperparameter tuning. Here, we present a scalable framework for the joint inference of dynamic GRNs using a discrete ℓ₀ penalty, enabling direct and unbiased control over network sparsity. Leveraging recent algorithmic advances, we efficiently solve the resulting mixed-integer optimization problem for populations structured as arbitrary tree hypergraphs, accommodating both continuous and categorical distinctions among biological samples. After validating our method on synthetic benchmarks, we apply it to single-cell and spatial transcriptomics data from glioblastoma (GBM) patient tumors. Our approach reconstructs gene networks across tumor clusters, maps network rewiring along hypoxia gradients, and reveals niche-specific differences between primary and recurrent tumors. By providing a robust and interpretable tool for GRN inference in complex tissues, our work facilitates high-resolution dissection of tumor heterogeneity and adaptation, with broad applicability to emerging large-scale transcriptomic datasets.

[Github link] [paper link]

We study convex quadratic optimization problems involving indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this problem in quadratic time and memory. Our computational experiments conducted on both synthetic and real-world datasets demonstrate the superior performance of our proposed algorithm compared to existing algorithms and state-of-the-art mixed-integer optimization solvers. An important application of our algorithm is in the real-time inference of Gaussian hidden Markov models from data affected by outlier noise. Using a real on-body accelerometer dataset, we solve instances of this problem with over 30,000 variables in under a minute, and its online variant within milliseconds on a standard computer.

[Github link] [paper link]