New Deterministic Algorithm Tames the Combinatorial Chaos of Regression Subset Selection

Few problems in statistics look as innocent on paper as choosing which variables to include in a multiple linear regression. Given a table of candidate predictors and an outcome of interest, the task seems to be nothing more than deciding which columns belong in the model. Yet the moment the number of candidate predictors grows, the problem explodes combinatorially. With fifty predictors there are more than a quadrillion possible subsets; with a hundred, the number of models exceeds the number of atoms in the universe by an unimaginable margin. Exhaustive all-subsets regression, the gold standard that guarantees the best model, becomes computationally impossible long before researchers reach the dimensions that modern datasets routinely present. A new study published in the International Journal of Data Science and Analytics by Jackson J. Alcázar of Universidad del Desarrollo in Chile confronts this wall directly, introducing a deterministic heuristic called EPR-C3 that promises to make high-dimensional subset selection tractable without sacrificing statistical rigor.

The core insight behind EPR-C3 is that the search for the best subset should not be blind. Traditional approaches to the problem fall into two broad camps, each with well-known weaknesses. Stepwise procedures, which add or remove predictors one at a time based on statistical criteria, are fast but notoriously unstable, often missing the globally best model and producing results that shift with small perturbations of the data. Penalized regression methods such as the lasso, ridge, and elastic net shrink coefficients to perform implicit selection, but they transform the problem itself, replacing the ordinary least squares formulation with a modified objective and yielding biased estimates that complicate interpretation. Genetic algorithms and other stochastic search techniques can explore large spaces, but their reliance on random initialization and random operators means that two runs of the same algorithm on the same data can produce different answers, undermining the reproducibility that scientific work demands.

EPR-C3 takes a different path. The method is a deterministic multi-start neighborhood-search heuristic, meaning that it systematically explores multiple regions of the subset space using structured moves rather than random jumps, and that repeated runs on identical data produce identical results. The name encodes its workflow: expansion, perturbation, and reduction form the exploratory core, while C3 refers to a three-part constraint refinement stage comprising correlation cleanup, replacement recovery, and variance inflation factor pruning. Each stage addresses a specific pathology of high-dimensional regression. Expansion grows a candidate subset by adding predictors that promise improvement. Perturbation shakes up the current solution to escape local optima, the traps where a greedy search would otherwise stall. Reduction trims away predictors that no longer earn their place.

The C3 refinement stage is where the method embeds statistical admissibility directly into the search. Correlation cleanup removes predictors that are so strongly correlated with others already in the model that they add redundancy rather than information. Replacement recovery attempts to swap problematic predictors for alternatives that preserve predictive power while restoring stability. Variance inflation factor pruning, the final safeguard, quantifies how much the variance of an estimated coefficient is inflated by multicollinearity and eliminates predictors whose presence destabilizes the model. By enforcing these constraints during the search rather than checking them afterward, EPR-C3 ensures that every candidate model it evaluates is statistically admissible, avoiding the embarrassing situation in which a search returns a model with excellent fit but coefficients so unstable that they are meaningless.

A crucial design decision sets EPR-C3 apart from penalized approaches: it preserves the native ordinary least squares formulation throughout. The final output is not a shrunken or regularized set of coefficients but an explicit regression equation of the familiar form, with interpretable coefficients estimated by classical least squares. This matters enormously for applied researchers in fields such as chemistry, medicine, and the social sciences, where the goal is often not just prediction but understanding, and where an explicit equation with transparent coefficients is the deliverable that matters. The author’s own background in chemical modeling, including prior work on predicting acid dissociation constants in nitrogen compounds, reflects this applied orientation toward interpretable equations.

The benchmark results are striking. In analyses comparing EPR-C3 against exhaustive all-subsets regression, the heuristic recovered a high proportion of the Top-K admissible subsets, the best-ranked models that exhaustive search identifies, while dramatically reducing computational cost in highly combinatorial problems. In other words, when the exhaustive answer is computable, EPR-C3 usually finds it; when exhaustive search is impossible, EPR-C3 still delivers high-quality admissible models in a fraction of the time. The study goes further and proposes an empirical utility threshold, a practical guideline that tells analysts when the heuristic search becomes preferable to exhaustive enumeration, giving practitioners a principled rule for choosing between the two strategies rather than guessing.

The comparative evaluation is unusually thorough for a methods paper. EPR-C3 was benchmarked against stepwise procedures, penalized-regression preselection, filter and wrapper screening approaches, genetic algorithms, and branch-and-bound subset selection, the latter being the classical exact method that prunes the search space using bounds on the objective. Across these comparisons, a consistent pattern emerged: embedding admissibility constraints within the search workflow improves the tradeoff between recovery of the best models and computational efficiency. Competing methods that search first and check statistical validity later, or that abandon the least squares framework entirely, tend to either waste effort on inadmissible candidates or return models that require post-hoc repair. EPR-C3’s constraint-aware architecture avoids both failure modes.

Reproducibility and robustness received dedicated attention. Bootstrap analyses, in which the method was run on resampled versions of the data, showed close agreement with exhaustive selection in best-subset recovery, out-of-bag performance, and predictor-inclusion concentration, the degree to which the same predictors are selected consistently across resamples. This concentration measure is particularly important because instability of variable selection is one of the most cited criticisms of heuristic and stepwise methods. A seed-package analysis further confirmed that the deterministic nature of the algorithm holds in practice, with repeated runs converging on the same solutions. An applied case study demonstrated that EPR-C3 could reproduce a previously published multiple linear regression equation, recovering the same model with reduced runtime, providing a concrete demonstration that the method delivers on real problems rather than only on synthetic benchmarks.

The significance of this work extends beyond the specific algorithm. Variable selection remains one of the most contested practices in applied statistics, with methodologists repeatedly warning that automated selection can produce misleading inference, inflated significance, and models that fail to replicate. By making the search deterministic, constraint-aware, and anchored in the classical least squares framework, EPR-C3 offers a middle path between the computational impossibility of exhaustive search and the statistical compromises of penalization and greedy stepwise selection. The method is implemented in the author-maintained MLR-X project and publicly available, lowering the barrier for adoption. As datasets in genomics, chemometrics, economics, and the behavioral sciences continue to swell in dimensionality, tools that combine computational tractability with statistical admissibility and exact reproducibility are likely to find eager audiences. The study, published as volume 22, article 311 of the journal and supported by ANID-FONDECYT grant funding, suggests that the future of high-dimensional model selection may lie not in abandoning classical regression but in searching its vast model space more intelligently.

Subject of Research: Deterministic constraint-aware subset selection in high-dimensional multiple linear regression

Article Title: Epr-c3: a deterministic constraint-aware heuristic for high-dimensional subset selection in multiple linear regression

Article References: Epr-c3: a deterministic constraint-aware heuristic for high-dimensional subset selection in multiple linear regression. (n.d.). https://doi.org/10.1007/s41060-026-01298-0

Image Credits: AI Generated

DOI: 10.1007/s41060-026-01298-0

Keywords: subset selection, multiple linear regression, ordinary least squares, multicollinearity, variance inflation factor, heuristic optimization, best-subset regression, statistical computing, high-dimensional data, model selection, deterministic algorithms, bootstrap validation