A large share of the genetic influence on human traits cannot be pinned to specific DNA variants. Family studies say a trait is strongly heritable, but the variants that pass genome-wide significance explain only a sliver of it. This gap is called "missing heritability." One long-standing explanation is epistasis: combinations of variants that matter jointly while each looks inert on its own. That explanation has never been testable in a satisfying way, because the number of three- or four-variant combinations across millions of variants is astronomically large. Current tools sample that space heuristically. When they find nothing, they tell us nothing about what remains. We propose to borrow the main tool personnel-scheduling researchers use for astronomically large search spaces. That tool is column generation, a method that solves a selection problem over a huge set of candidates by building the candidates on demand, one at a time, through a separate search called the pricing step. Run to completion, column generation proves that no unbuilt candidate could improve the solution.
The core claim follows. Recast as column generation, epistasis discovery produces both a model and a certificate. The model is a sparse regression over additive variants plus multi-locus interaction terms. The certificate is an exact statement of the largest share of residual phenotypic variance that any single omitted interaction could explain, within an explicitly defined family of biologically constrained combinations. For any trait and cohort, this turns the vague question "could epistasis hide the missing heritability?" into a falsifiable number with a permutation-calibrated null.
Why scheduling is the right source
Bus-driver scheduling has the same shape of difficulty. The candidate set is every legal driver shift, far too many to list. Branch and Price for Bus Driver Scheduling with Complex Break Constraints handles it with a master problem that chooses among shifts and a pricing step that searches for a profitable new shift as a constrained shortest path through a graph of trip legs. Each partial path tracks 11 accumulated "resources," such as driving time and break placement. Inferior partial paths are discarded by dominance checks run efficiently with k-d trees, a spatial index over those resource coordinates. That paper supplies our method. It is also our main constraint: at 100 tours, "label explosion" left optimality gaps up to 67.8%, so exact pricing alone will not scale. Investigating Large Neighbourhood Search for Bus Driver Scheduling offers the fix we reuse. It runs fast heuristic repair that solves only the root of the column generation problem and found 23 new best-known solutions on 65 instances. Our pricing will likewise run a cheap heuristic phase and invoke exact search only to close the certificate.
On the genetics side, three papers motivate the gap. Epistasis regulates genetic control of cardiac hypertrophy used low-signal signed iterative random forests (lo-siRF) on 29,661 UK Biobank cardiac MRIs. It found interactions among loci near CCDC141, IGF1R, TTN and TNKS that were insignificant in marginal tests, and confirmed the non-additivity in stem-cell-derived heart cells. Because the method is a stochastic tree heuristic, a null result says nothing about combinations it never visited. A statistical framework to identify gene-gene interactions underlying multiple dichotomous phenotypes from genotype data (GiMat) tests pre-filtered pairs with kernel regression and saddlepoint calibration across 337,205 participants. It stops at pairs and relies on external pre-filtering. Phenome-wide heritability analysis of the UK Biobank estimates additive chip heritability by fast moment matching, for example height at about 0.685. This gives the additive reference point our certificate sits on top of, but it cannot localize anything. The closest methodological precedent is Boolean Decision Rules via Column Generation, which, as its title indicates, learns rule sets by generating conjunctive rules in a pricing step. It shows conjunctions can be priced. It does not supply what we need: a regression master on a continuous trait with covariates, biological resource constraints in pricing, scheduling-style dominance pruning, or a calibrated variance bound as the reported scientific output.
Core formulation
Let $y$ be a covariate-adjusted trait for $n$ people. Covariates include ancestry principal components and are left unpenalized. Let $\mathcal{F}$ be the family of allowed features. Each feature $c$ is an indicator vector $x_c \in \{0,1\}^n$. It marks carriers of one variant, or carriers of all variants in a conjunction of up to $k$ variants. The master problem is the lasso:
$$\min_{w} \tfrac{1}{2}\lVert y - \textstyle\sum_{c \in S} w_c x_c \rVert^2 + \lambda \lVert w \rVert_1 ,$$
where $S \subseteq \mathcal{F}$ is the current working set and $\lambda$ the sparsity penalty. The residual $r$ at the current solution plays the role of the dual prices.
A new feature can enter only if $|x_c^\top r| > \lambda$. If exhaustive pricing finds none, the working-set solution is optimal over all of $\mathcal{F}$. We also report a second quantity:
$$\rho^\ast = \max_{c \in \mathcal{F} \setminus S} \frac{(x_c^\top r)^2}{\lVert x_c\rVert^2 \lVert r \rVert^2}.$$
This is the largest fraction of remaining residual variance any single omitted interaction explains. It is exactly the quantity the missing-heritability debate needs.
Pricing is a constrained path search. Each step adds a variant to a partial conjunction along an allowed edge, either a protein-interaction link or membership in the same pathway. Each partial conjunction carries a resource vector: its order, its carrier count, the positive residual mass over carriers, and the negative residual mass over carriers. Adding a variant can only shrink the carrier set. The best any extension can achieve is therefore bounded by the larger of the two residual masses, normalized by a minimum carrier count. That minimum count is also a hard resource, and it directly addresses the near-empty genotype cells that break asymptotic tests in GiMat's setting. Partial conjunctions are pruned when their bound falls below the incumbent. Dominance between partial conjunctions that reach the same graph node is checked with k-d trees over the resource vector, following the bus-driver paper.
Research Program
We will build the solver in three layers. The first is a warm-started lasso master. The second is a heuristic pricer, a beam search plus large-neighbourhood moves that remove and regrow variants. The third is an exact pricer used only to certify $\rho^\ast$. Training-sample maxima are inflated because so many features are scanned. We therefore calibrate $\rho^\ast$ by rerunning exact pricing on the same pipeline with the trait permuted within ancestry strata, about 100 times. We report its quantile under that null and evaluate all fitted models on held-out individuals.
The scientific output for each trait is a curve. It shows how the certified $\rho^\ast$ and the held-out variance explained change as the family grows: pairs within genes, pairs along interaction edges, triples, then four-way combinations. A curve that stays at the null quantile is a quantitative negative result about structured epistasis that no current method can produce. A curve that lifts off the null localizes the responsible combinations.
Baselines
The naive reference is marginal GWAS followed by an additive polygenic score built from the marginal effects. It sets the floor that any epistatic model must beat on held-out variance explained. The additive ceiling comes from moment-matching chip heritability as in Phenome-wide heritability analysis of the UK Biobank, which reports height $h^2_{\text{SNP}} \approx 0.685$. We recompute it on our exact sample so the gap is measured on identical data.
The strongest existing epistasis method is lo-siRF from Epistasis regulates genetic control of cardiac hypertrophy. It is the only method in the file shown to recover high-order interactions among variants with negligible marginal effects at biobank scale. We run it on the same genotypes, covariates and left-ventricular-mass trait, with the same wall-clock and memory budget and equal tuning trials. We feed its discovered interactions into the same held-out lasso so that only the search procedure differs. That paper reports the CCDC141/IGF1R/TTN/TNKS interactions and an 8.5% non-additive cell-size effect, but no recovery rate or held-out variance figure (no reported result found on Lacuna for lo-siRF held-out variance explained or planted-interaction recovery). Beating it therefore means three things on our simulations and held-out data. We must recover planted interactions at a strictly higher rate under matched budget. We must match or exceed its held-out variance explained on real left ventricular mass. And we must supply the certificate it cannot.
For binary pairs we run GiMat on the type 2 diabetes and hypertension cohort. Success means recovering its four reported pairs while additionally reporting certified $\rho^\ast$ over triples.
Two ablations isolate the key ingredients. The first removes the structural resources: unconstrained pricing over all conjunctions up to order $k$, at the same budget. It tests whether the biological graph matters or only shrinks the search. The second keeps heuristic pricing only. It tests whether the exact certificate changes any conclusion relative to heuristic search alone. A third comparison runs Boolean-rule column generation in the style of Boolean Decision Rules via Column Generation on a dichotomized trait. It checks whether our regression master and pruning add anything over the existing column-generation recipe.
Why not just…?
Why not just fit a lasso over all pairwise interactions with marginal pre-screening? Pre-screening on marginal effects throws away exactly the variants that lo-siRF found to act only in combination (Epistasis regulates genetic control of cardiac hypertrophy), and enumerating all pairs before fitting does not extend to triples. Our simulations plant interactions with zero marginal effect specifically to show where screening fails. If they are recovered anyway, the threat is real and we will say so.
Why not just estimate total epistatic variance with an interaction kinship matrix and moment matching? This is the most serious alternative. It extends the fast estimator of Phenome-wide heritability analysis of the UK Biobank, and it may give a good aggregate number for pairwise variance. It assumes many tiny effects, however. It does not localize them, and it says nothing about sparse higher-order combinations constrained to pathways. We will compute it on the same traits. If it agrees with our cumulative curve at order two, our contribution reduces to localization and the higher-order bound, and we will frame it that way.
Why not just run lo-siRF longer or with more seeds? More sampling raises recall but never yields a statement about unvisited combinations. The matched-budget comparison above shows whether column generation finds more. The certificate is something no amount of extra sampling provides.
Why not just hand the problem to a commercial integer programming solver? The scheduling evidence argues against it. Commercial integer programming took over 24 hours on nurse rostering instances that a structured heuristic solved in minutes (An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering), and our candidate set cannot even be written down explicitly.
Proposed Experiments
The first experiment is a planted-truth study. We simulate traits on real UK Biobank genotypes with additive background matching the reported height heritability. We add two- to four-way interactions with zero marginal effect, placed either on or off interaction-graph edges, and vary the carrier frequency. We measure recovery rate, false discoveries, held-out variance explained, the calibration of certified $\rho^\ast$ against the true omitted variance, and wall-clock time against lo-siRF and the ablations. The off-graph placements test honestly how the structural constraint fails when biology violates it.
The second experiment reanalyzes real data. On left ventricular mass from cardiac MRI, the decisive check is whether we recover the lo-siRF loci and what certified $\rho^\ast$ remains beyond them. On the type 2 diabetes and hypertension cohort, the check is GiMat's pairs plus a triple-level bound. On height, the question is whether the certified curve over structured triples stays at the permutation null. If it does, that is a calibrated upper bound on how much height heritability such epistasis can hide.
The third experiment is a scaling study. It tracks the pricing label counts with and without k-d tree dominance as the variant count grows, to test directly whether the label explosion seen at 100 tours in bus scheduling recurs here and where the exact certificate stops being affordable.
The proposal is falsified if, under matched budget, heuristic pricing alone produces the same conclusions as exact certification. It is also falsified if certified $\rho^\ast$ is poorly calibrated against held-out omitted variance in simulation.
References
- Branch and Price for Bus Driver Scheduling with Complex Break Constraints
- Investigating Large Neighbourhood Search for Bus Driver Scheduling
- Epistasis regulates genetic control of cardiac hypertrophy
- A statistical framework to identify gene-gene interactions underlying multiple dichotomous phenotypes from genotype data
- Phenome-wide heritability analysis of the UK Biobank
- Boolean Decision Rules via Column Generation
- An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering