Many fast exact solvers use a "restrict-then-solve" decomposition. A neural network trained on synthetic instances makes a rough guess, and an exact solver then searches only a narrow window around that guess. The speedups can be large. The risk is that the guarantee is only as good as the synthetic data behind the guess. If the generator never produced the structures that real instances contain, the guess lands far from the true optimum. The exact solver then returns the best answer inside the window and labels it optimal, and nothing warns anyone that the true optimum lay outside.
We propose to evaluate synthetic training data for these hybrid solvers by one quantity: window coverage. For a given instance, it is the smallest search window that still contains a globally optimal solution. The question is how this smallest window is distributed on real instances compared with synthetic ones. The coverage gap becomes three things at once. It is a substitutability metric for the generator. It is an exchange rate, meaning how many real instances buy back how much window width. It is also the basis of a solver that detects when its window is too small and widens it only then. In short, current hybrid solvers fix the window width in advance and evaluate their synthetic data indirectly. We measure directly whether the synthetic data keeps real optima inside the window, and we make the solver check this on every instance.
Core Claim
The clearest example is Inc-ILP, from Accelerating Exact Combinatorial Optimization via RL-based Initialization - A Case Study in Scheduling. There, a reinforcement-learning agent trained on one million synthetic directed acyclic graphs (DAGs, here neural-network computation graphs) predicts a coarse pipeline schedule. IBM CPLEX then solves an integer linear program (ILP) only within a topological relaxation window of $\gamma = 10$ around that prediction. The paper reports speedups of 54×, 128× and 115× over full CPLEX on 4-, 5- and 6-stage scheduling at 100% optimality, and 19–27× faster solving than the Edge TPU compiler. These results come from only 10 ImageNet networks. The paper never relates the synthetic DAG distribution to real graphs. It also never asks how close those 10 graphs came to needing a window wider than 10.
Our claim has two parts. First, for restrict-then-solve decomposition, the generator property that matters is coverage on real instances. General realism, such as matching graph statistics, is the wrong target, and the two can rank generators differently. Second, a solver can certify coverage on every instance at modest cost, which turns silent failures into detected ones.
Formally, let $\hat{s}$ be the predicted coarse schedule and $s^*$ range over optimal schedules. Window coverage is
$$ \gamma^*(x) = \min_{s^* \in \mathrm{OPT}(x)} \; \max_{v} \, |\mathrm{pos}_{s^*}(v) - \mathrm{pos}_{\hat{s}}(v)|, $$
where $v$ ranges over graph nodes and $\mathrm{pos}$ is a node's topological stage position. A fixed-window solver is exactly optimal on instance $x$ if and only if $\gamma^*(x) \le \gamma$. The value $\gamma^*$ is computable on test instances with a lexicographic ILP. The first stage finds the optimal objective. The second stage minimizes the maximum deviation from $\hat{s}$ while holding the objective at its optimum.
Research Program
Building the coverage measurement. We first reimplement the Inc-ILP pipeline, since no code for it appears in the file, together with its synthetic DAG generator. We also assemble a real test pool much larger than the original 10 networks. This pool consists of a few hundred computation graphs exported from publicly available architectures: convolutional, residual, dense, attention-based and mixed designs. For each graph we compute $\gamma^*$. Comparing the distribution of $\gamma^*$ on held-out synthetic graphs with its distribution on real graphs gives the coverage gap. This distribution, and especially its upper tail, is the object we study.
Turning coverage into a substitutability test. On the Equivalency, Substitutability, and Flexibility of Synthetic Data defined an exchange rate between synthetic and real data for video tracking, about 30:1, and found that structural and behavioral complexity mattered more than surface realism. We borrow the concept but change the downstream measure. Instead of task accuracy, we ask how many real graphs mixed into training are needed to bring real-instance coverage at $\gamma = 10$ to a target level, or to shrink the 95th-percentile $\gamma^*$ by a given amount. We then build generator variants that differ along structural axes: branching factor, density of skip connections, heavy-tailed tensor sizes, and operator mix. We test whether coverage on a small real calibration set predicts which variant works best on the remaining real pool better than standard graph-statistic distances do. Our working hypothesis follows the tracking result. Coverage should be driven by a few structural features that ordinary similarity measures down-weight.
Certified window expansion. In the solver, the restricted ILP returns value $z_R$. We then obtain a lower bound $L$ on the full problem. Cheap options come first: the linear-programming relaxation, then a short time-limited CPLEX run on the full problem with $z_R$ supplied as a cutoff. If $z_R - L \le \epsilon$, the answer is certified. Otherwise the solver doubles $\gamma$ and repeats. Scheduling relaxations can give weak bounds, so this step may sometimes cost close to a full solve. Measuring how often that happens is part of the study, not a footnote.
A calibrated second domain. Inc-ILP's test set has no difficulty control. DynaSchedBench provides calibrated dynamic flexible job-shop instances. Each instance is graded by a Schedule Stress Index (SSI), which combines congestion, time pressure, structural complexity and disruption intensity. We apply the same restrict-then-solve design there: a learned or heuristic dispatcher produces the guess, and a constraint-programming solver searches a window around it. We then ask whether $\gamma^*$ rises with SSI. If it does, a fixed window that looks safe on uncalibrated synthetic data fails specifically on high-stress instances, and the instance's stress level could set the starting window.
Baselines
The naive reference point is full CPLEX on the unrestricted ILP, with the same machine and time limits. It defines the optimal answer and the solve times that every speedup is measured against.
The strongest existing method is Inc-ILP as published: an agent trained only on synthetic DAGs with a fixed $\gamma = 10$. Its reported results are 54×/128×/115× speedups over full CPLEX at 100% optimality on 10 ImageNet networks, from Accelerating Exact Combinatorial Optimization via RL-based Initialization - A Case Study in Scheduling. We run it on our expanded real pool with the same training budget as every other variant. Our method beats it if it stays optimal on all real instances, including those where fixed $\gamma = 10$ is silently suboptimal, while keeping median speedup within a small factor of fixed $\gamma = 10$. If fixed $\gamma = 10$ is already optimal everywhere on the expanded pool, the certified solver cannot beat it on quality and must justify itself by detection alone.
Warm-start-only CPLEX gives the same predicted schedule to CPLEX as a starting solution on the full problem, with no restriction. It is the strongest competitor for the solver component because it keeps optimality by construction. We give it the same predictor and the same wall-clock budget.
We also run fixed wider windows, $\gamma \in \{15, 20, 30\}$. These trace the cost–coverage curve that adaptive expansion must lie above.
Two baselines test the data component. The first is fine-tuning the agent on real graphs, given the same real-graph budget as our coverage-guided generator selection. The second is generator selection by graph-statistic distance, given the same calibration set.
Two ablations isolate our ingredients. One compares the certificate-driven expansion against an uncertified heuristic that widens $\gamma$ whenever the predictor's confidence is low. The other compares generator selection by coverage against selection by similarity, with everything else held fixed.
Why not just…?
Why not just use a larger fixed window? A wider window raises coverage, but solve time grows quickly with window width. Inc-ILP's speedups depend on the window being narrow. More importantly, any fixed width is a bet about the real $\gamma^*$ distribution, which nobody has measured. Our fixed-$\gamma$ sweep shows directly whether a single width covers the real tail at acceptable cost. If it does, we will report that the adaptive solver is unnecessary for this domain and that the measurement is the contribution.
Why not just warm-start the full solver instead of restricting it? This is the most serious threat. If CPLEX with a good starting solution proves optimality nearly as fast as the restricted solve, then restriction adds risk for little benefit. The Inc-ILP paper compares against unguided CPLEX, not warm-started CPLEX, so the file contains no evidence either way. Our head-to-head comparison at equal predictor quality settles the question. If warm-start matches restriction, we will say so and recast the coverage metric as a data-evaluation tool for warm-start quality.
Why not just fine-tune on real graphs or meta-learn across many synthetic distributions? Meta-learning across synthetic distributions helps small routing models adapt to new distributions. On the Generalization of Neural Combinatorial Optimization Heuristics reduces a TSPLIB 151–200 node gap from 17.35% to 13.22%. Towards Omni-generalizable Neural Methods for Vehicle Routing Problems reaches 3.74% versus 4.43% for the POMO baseline on 300-node Rotation TSP. Both still report nonzero gaps, so neither guarantees that a guess falls within a fixed distance of the optimum. Fine-tuning is complementary to our work, not a replacement. The coverage metric is what tells us how many real graphs fine-tuning needs, and the matched-budget fine-tuning baseline shows whether coverage-guided generator design does better with the same real data.
Why not just judge the generator by distributional similarity? In energy scheduling, Privacy-Preserving Spatiotemporal Scenario Generation of Renewable Energies warns that statistical similarity does not guarantee operational safety. In tracking, On the Equivalency, Substitutability, and Flexibility of Synthetic Data finds that structural complexity matters more than photorealism. Our generator-ranking experiment tests the same pattern here: does similarity rank generators differently from real-instance coverage?
Proposed Experiments
The first experiment compares coverage on synthetic and real graphs. We train on synthetic DAGs and compute $\gamma^*$ for every held-out synthetic and real graph. We then report the fraction of real graphs with $\gamma^* > 10$ and how that fraction varies by architecture family.
The second experiment estimates the exchange rate. We mix increasing numbers of real graphs into training and plot real-instance coverage at $\gamma = 10$ against the real-graph count. From this we derive the synthetic-to-real equivalence for this solver.
The third experiment compares generator rankings. Across the structural generator variants, we compute the rank correlation between coverage on the held-out real pool and two predictors: coverage on the calibration set, and graph-statistic distance.
The fourth experiment evaluates certified expansion. On all real graphs we report optimality rate, median and tail solve time, and how often the certificate needed a near-full solve, alongside all baselines.
The fifth experiment covers stress. On DynaSchedBench subsets stratified by SSI, we test whether $\gamma^*$ rises with stress. The only nearby reported numbers are not for a windowed exact solver: on that benchmark, the best dispatching heuristic's mean normalized excess makespan is 1.11% and the best language-model configuration's is 0.65%. We use the heuristic as the window's starting guess and report exact makespans as the reference.
The decisive check is the first experiment. If fixed $\gamma = 10$ covers essentially every real graph in a diverse pool, the claimed failure mode is not present in this domain, and the proposal shrinks to a measurement result. If even a few percent of real graphs need wider windows, then a published 100%-optimality claim does not transfer to deployment, and both coverage-based evaluation and certification are necessary.
References
- Accelerating exact combinatorial optimization via rl-based initialization-a case study in scheduling
- On the Equivalency, Substitutability, and Flexibility of Synthetic Data
- DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents
- On the Generalization of Neural Combinatorial Optimization Heuristics
- Towards Omni-generalizable Neural Methods for Vehicle Routing Problems
- Privacy-Preserving Spatiotemporal Scenario Generation of Renewable Energies: A Federated Deep Generative Learning Approach