Learning Warm Starts for the Simplex Method from Measured Solver Cost

Felix Parker; Danielle A. Ripsman; Emmett Springer; Kimia Ghobadi

math.OCOct 14, 2026

Learning Warm Starts for the Simplex Method from Measured Solver Cost

Authors: Felix Parker, Danielle A. Ripsman, Emmett Springer, Kimia Ghobadi

Organizations: Center for Systems Science and Engineering, Johns Hopkins University

Abstract

Learned warm starts for the simplex method build starting bases using predictions of which variables will be basic at optimality. Prior work has shown that starting bases predicted by graph neural networks can sharply reduce iteration counts, but the time saved may fall well short of the iterations saved. On 25 classes of linear programs (LPs), we find that a strong supervised basis predictor removes two thirds of the dual simplex's iterations but only a third of its time. Two effects explain the gap: the iterations removed by a good start tend to be cheap, and closeness to an optimal basis does not rank starts by cost. We prove that two starts with equal overlap with an optimal basis and equal pivot counts can differ in linear-algebra work by a factor that grows with the square root of the number of rows. Empirically, across the starts of one LP, the pivot count explains 71% of the variance of log solve time, while the CPU instruction count explains 98.5%. We introduce CostStart, which uses supervised prediction for the basis and trains a small policy on measured instruction counts to choose, per LP, how many predicted columns to use, which algorithm and pricing rule to run, and whether to warm-start at all. On unseen LPs of the training classes, including LPs four times the training size, CostStart roughly halves the solve time relative to the solver's default start and is 1.4 to 2.2 times as fast as two published methods retrained on the same data.

Figures & tables

Figure 1: Iteration savings overstate time savings. (a) Iterations and charged time of learned warm starts on unseen test LPs, relative to the dual simplex from a cold (all-slack) start (geometric means; § 5 ). Every method lies well above the diagonal, where time saved would equal iterations saved. (b) How much of the variance in log solve time each quantity explains across different starts of the same LP. The CPU instruction count, which our method, CostStart (§ 4 ), trains on, explains nearly all of it.

Fan et al. (2023) : iterations / time			Lu & Yan (2025) : iterations / time
Dataset	OptVerse	HiGHS	Dataset	unpresolved	presolved
LIBSVM	0.61 / 0.66	0.58 / 0.62	Mirp1	0.42 / 0.52	0.32 / 0.42
MIRP	0.64 / 0.70	0.61 / 0.81	Mirp2	0.93 / 1.05	0.86 / 0.83 †
STOCH	0.42 / 0.96	0.48 / 0.35 †	Anonymous	0.59 / 0.72	0.74 / 1.19
GEN	0.23 / 0.38	0.04 / 0.15	Load balancing	0.46 / 0.71	0.63 / 0.70
SC-1	0.10 / 0.29	0.25 / 0.52

Table 1: Iteration and time ratios (learned start / default start) computed from the published tables: Fan et al. (2023) , Tables 1 (OptVerse) and 2 (HiGHS), dual simplex; Lu & Yan (2025) , Tables 3 to 7 (HiGHS dual simplex, their tripartite model). Geometric means over the datasets of each column. † time falls more than iterations.

Figure 2: Equal overlap and pivot count do not imply equal work. (a) The warm starts of Theorem 1 : DSE resolves the singletons of warm A in blocks and the pairs of warm B one at a time. (b) The chain LP in HiGHS (presolve and scaling off, Devex): warm B takes 27 times as long as warm A. (c) Our generated LPs: pairs of starts of one LP with overlap within 0.005 and pivots within 2% differ in time by more than 25% in 9% of cases (class-balanced; the histogram gives each LP equal weight).

Figure 3: Cumulative instructions against iteration, normalized by the native solver’s total, on eight of the 20 traced LPs of Dev-20k (the LPs at evenly spaced ranks of the native solver’s iteration count). The value at iteration 0 is the setup; each curve ends at the solve’s total, so a learned curve’s end point is its total relative to the native solver. The all-slack dual simplex is drawn only where its path differs from the native solver’s.

Panel of Figure 4 — Figure 4: CostStart at deployment (top) and in training (bottom). Blue boxes are learned and orange tags are guardrails, all charged in the timings; the solver is unmodified. From the predictor’s embedding $h$ and score statistics $z$ , the policy picks one of up to 20 actions: a shift $\delta$ of the scores $s$ with an algorithm and pricing rule, or the native solver. Training uses optimal bases for the predictor and instruction counts of every action for the policy.

	Test-20k (1,356 LPs)			Test-50k (382 LPs)			Test-80k (81)
Method	iter.	time [95% CI]	W/L	iter.	time [95% CI]	W/L	time
all-slack dual simplex	1.00	1.07 [0.87, 1.30]	12/13	1.00	0.99 [0.76, 1.30]	12/13	0.96
stock solver, presolve on	0.85	1.10 [1.06, 1.16]	3/22	–	–	–	–
classical crash	1.22	1.76 [1.19, 2.60]	9/16	–	–	–	–
Fan et al.	0.49	1.10 [0.89, 1.35]	15/10	0.50	1.02 [0.78, 1.37]	15/10	0.96
Lu & Yan	0.47	0.94 [0.70, 1.22]	14/11	0.50	0.85 [0.56, 1.23]	19/6	0.72

Table 2: Main results on unseen LPs of the training classes: every learned start removes half or more of the iterations, but only our systems save substantial time. Class-balanced geometric means (below 1 is better) of iterations relative to the all-slack dual simplex and of charged time relative to the native solver, with 95% intervals and classes won/lost. The class-blind gate is refit without the test LP’s class; the per-class lookup plays each class’s cheapest training action (Appendix J.2 ). On Test-50k and Test-80k , methods run without the optimality check, and the larger policies are reported in Table 4 a. More rows: Appendix J .

Figure 5: Every learned start trades fewer iterations for costlier ones. Charged time on Test-20k relative to the native solver, split by Eq. ( 1 ) into iterations, time per iteration and fixed overhead (class-balanced geometric means). On the log axis, segments left of 1 lower the time, segments right of 1 raise it, and the diamond (95% interval) is their sum. “Predictor + shift policy” is CostStart-Shift without the harm gate.

LPs	Label	instructions [95% CI]	iterations	per iteration	Devex	primal
held-out, W1 (1,531)	instructions	0.669 [0.589, 0.751]	0.892	0.749	51%	8%
	iterations	0.937 [0.817, 1.103]	0.759	1.234	12%	36%
held-out, W2 (316)	instructions	0.668 [0.526, 0.826]	0.729	0.916	29%	20%
	iterations	0.679 [0.489, 0.998]	0.601	1.129	5%	51%
selection split of Dev-20k (275 of 283)	instructions	0.682 [0.570, 0.797]	0.868	0.786	60%	9%
	iterations	0.960 [0.798, 1.170]	0.723	1.327	15%	46%

Table 3: Training label of the CostStart-Full policy, offline on held-out training LPs: instructions of the chosen actions relative to the predictor’s unshifted start, split into iterations and work per iteration, and the share of LPs routed to Devex and to primal simplex. The selection split was used to design the policy and is not held out.

(a) Larger LPs	Test-50k	Test-80k
	(309)	(63)
all-slack dual simplex	0.94	0.90
predictor	0.65 (1)	0.83 (1)
Devex on every LP	0.66	0.78 (1)
CostStart-Shift	0.58	0.67
CostStart-Alg	0.60 (2)	0.83 (1)

Table 4: CostStart keeps most of its gain on larger LPs and held-out variants; new classes need adaptation. Charged time relative to the native solver (class-balanced). (a) Solves under 120 s, with the optimality check inline (failures in parentheses); Table 2 also includes longer solves. (b) With 95% intervals; the last column is relative to the reference named in each block.

Method (decoder)	Mirp1	Mirp2	Anonymous	Load bal.	Geomean [95%]
Fan et al. reimplemented (top- $m$ )	0.58 / 0.72	1.01 / 1.14	0.92 / 1.62	0.61 / 0.69	0.76 / 0.98 [0.93, 1.04]
Fan et al. reimplemented (top- $m$ repair)	0.55 / 0.69	0.78 / 0.92	0.87 / 1.69	0.56 / 0.68	0.68 / 0.92 [0.86, 0.99]
Lu & Yan reimplemented (top- $m$ )	0.70 / 1.10	0.92 / 1.07	0.71 / 1.37	0.60 / 0.68	0.72 / 1.02 [0.95, 1.10]
Lu & Yan reimplemented (top- $m$ repair)	0.71 / 1.12	0.80 / 0.99	0.70 / 1.48	0.58 / 0.70	0.69 / 1.03 [0.96, 1.12]
our predictor, fine-tuned (top- $m$ )	0.43 / 0.64	1.00 / 1.07	0.55 / 1.05	0.59 / 0.67	0.61 / 0.83 [0.78, 0.88]
our predictor, fine-tuned (top- $m$ repair)	0.35 / 0.57	0.99 / 1.06	0.56 / 1.27	0.55 / 0.69	0.57 / 0.85 [0.80, 0.91]

Table 5: Lu & Yan’s public benchmark under their protocol (one model per dataset, 7:3 split, presolved LPs): geometric-mean ratios over test LPs against the dual simplex with presolve off (iterations / fully charged time), with the geometric mean over the four datasets and its 95% interval. Test LPs per dataset: Mirp1 9, Mirp2 18, Anonymous 23, Load balancing 30; native solve times 9.6, 30, 1.2 and 3.0 s. All rows come from one paired panel except the two reported ones.

Appendix figures & tables32 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	cold	warm A	warm B	warm B / warm A
Devex forced, scaling off	1.21	0.156	4.21	27.0
DSE requested, scaling off	1.48	34.0	34.6	1.02
HiGHS defaults	26.4	36.1	34.9	0.97

Appendix

Table 6: The chain LP of Theorem 1 at

t=16

(65,535 rows) in HiGHS 1.13.1: wall time in seconds of installing the start and solving (one thread, presolve off, dual simplex; one repetition at this size). Warm A and warm B share overlap 0.94 and 4,096 pivots; the cold start takes 65,535. The first two settings also turn off cost perturbation and HiGHS’ less-infeasible DSE row choice; the defaults keep automatic edge weights, scaling and that row choice.

Kendall $\tau$ with time
Statistic	Value [95% CI]
overlap	0.31 [0.22, 0.41]
pivot count	0.65 [0.59, 0.71]
instruction count	0.91 [0.89, 0.93]
Kendall $\tau$ , other pairs
overlap and pivot count	0.45 [0.36, 0.55]

Appendix

Table 7: Within-LP statistics on the 381-LP panel of Dev-20k (25 classes, 17,329 distinct starts). Rank and variance statistics are computed within each LP and pooled; intervals are class-balanced bootstraps over classes and then LPs.

Figure 6: Per-LP iteration and charged-time ratios of the predictor against the all-slack dual simplex on a class-stratified subset of 400 W1 LPs of Test-20k (two timing repetitions averaged). Points in the upper left take fewer pivots and more time.

Change	Ratio
Recipe
main recipe, 5 seeds (mean $\pm$ sd)	$0.896\pm 0.013$
ensemble of the 5 seeds	0.900 [0.839, 0.961]; pivots 0.920; summed instructions 0.905
hidden width 64 / 256 / 512 / 1024	0.900 / 0.900 / 0.904 / 0.925
learning rate $3\times 10^{-4}$ / $3\times 10^{-3}$	0.896 / 0.898
loss clip 1 / 6 / none	0.903 / 0.891 / 0.888

Appendix

Table 8: Ablations of the shift policy: instructions relative to the unshifted predictor (class-balanced geometric means), on the 283-LP selection split of Dev-20k for the first two blocks. Single seeds unless noted. The action-set rows compare with the nine shifts on the same LPs. Transfer rows hold out each class, formulation or dual form of the training LPs in turn (three seeds, epoch chosen on a held-out fifth of the training LPs); the worst held-out classes are knapsack (2.10), telecom (2.17) and load balancing (2.01).

Rule	Ratio
best fixed shift chosen on training data	1.000 ( $\delta=0$ )
every other fixed shift	1.005 to 1.090
best fixed retune of the decoder (shift and degree exponent)	0.967
best constant shift per class, chosen in hindsight	0.926
learned policy, score statistics only (no embedding)	0.975
learned policy, embedding only	0.897

Appendix

Table 9: Controls for the shift policy on the 283-LP selection split of Dev-20k (22 classes): instruction ratios to the unshifted predictor. The oracle picks the best of the nine shifts per LP.

Figure 7: (a) Shift policies that differ only in their training label, on Dev-20k (charged time, three repetitions; Appendix J.1 ): the policy trained on iterations removes more pivots and saves less time. (b) The shift policy’s gain over the predictor as a function of the predictor’s recall of the optimal structural columns, on a development panel of 477 LPs at 40k to 60k variables that includes 23 duplicates of training LPs, with a shift policy trained on training data that include duplicates. Panel (b) only locates where the gain arises; no reported comparison uses it.

Design of CostStart-Alg
Action set	W1	W2
shifts only	0.906 / 0.935	0.851
shifts and native solver	0.810 / 0.781	0.792
shifts, native solver and primal simplex ( $\mathcal{A}_{2}$ , chosen)	0.783 / 0.754	0.605
$\mathcal{A}_{2}$ plus all-slack dual simplex and classical crash	0.796 / 0.773	0.648
Design of CostStart-Full

Appendix

Table 10: Design of the action sets on a held-out fifth of the training LPs: instructions relative to the predictor (class-balanced geometric means). For CostStart-Alg , W1 is reported on two sub-splits. Configuration only: a selector among the solver’s own starts under both pricing rules, without the learned start.

	Dev-20k panel		Dev-50k
Method	W1	W2	W1	W2
CostStart-Full	0.761 [0.618, 0.912]	0.524 [0.409, 0.666]	0.891 [0.813, 0.971]	0.857 [0.719, 0.993]
+ check and harm gate	–	–	0.751	0.682
CostStart-Alg	0.801	0.462	0.941 [0.88, 1.00]	0.856 [0.73, 0.97]
+ check and harm gate	–	–	0.796	0.679
predictor, Devex on every LP	0.980	1.189	0.865 [0.730, 1.019]	1.372 [0.943, 2.326]

Appendix

Table 11: Development readouts of the two larger policies: charged time relative to the predictor (class-balanced, 95% intervals where available). The Dev-20k panel has 207 W1 LPs of 23 classes and 45 W2 LPs of 8; Dev-50k has 290 W1 LPs of 23 classes and 164 W2 LPs of 16. No training LP is larger than 25,000 variables.

Option	instructions	iterations	work per iteration	failures
Devex pricing	0.910	1.067	0.853	0
Dantzig pricing	1.846	2.073	0.891	7
DSE without the switch to Devex	1.057	0.982	1.076	0
price strategy 1 / 2	1.010 / 0.994	1.000	1.010 / 0.994	0
cost perturbation off / $\times 5$	1.160 / 1.046	1.121 / 1.035	1.035 / 1.011	1 / 0
factor pivot threshold 0.01 / 0.5	1.007 / 1.014	1.005 / 1.011	1.003 / 1.003	0

Appendix

Table 12: Probe of HiGHS options on the predictor’s start (275 LPs of the selection split of Dev-20k ): instructions, iterations and work per iteration relative to HiGHS’ default options (class-balanced geometric means), and failures. HiGHS’ default dual edge weights use DSE with automatic switches to Devex.

Contrast	time	iterations	time per iteration	fixed
CostStart-Full vs. CostStart-Alg	0.959 [0.884, 1.046]	1.149 [1.051, 1.282]	0.821 [0.730, 0.909]	1.017
CostStart-Alg vs. CostStart-Shift	0.831 [0.744, 0.915]	0.820	1.084	0.934
CostStart-Full vs. CostStart-Shift	0.796 [0.696, 0.903]	0.942	0.890 [0.815, 0.961]	0.950
predictor vs. Lu & Yan	0.725 [0.637, 0.823]	0.671	1.078 [0.946, 1.212]	1.002

Appendix

Table 13: Paired contrasts on Test-20k , split by Eq. ( 1 ) into iterations, time per iteration and fixed overhead (class-balanced geometric means of the first method relative to the second, 95% intervals where computed).

Component	Setting
Predictor	8-layer GATv2 on the variable-constraint graph, 1.8M parameters, 72-dimensional pooled embedding; fused kernel with TF32, one LP per forward pass (6.4 ms median at 20k variables on an H100)
stage 1	114,874 LPs of Train-Small , 12 epochs (43k steps, 32 LPs per step, edge budget 400k), AdamW at $10^{-3}$ without weight decay, warm-up and cosine decay, gradient clip 5; loss: basis-membership cross-entropy divided by $m$ plus $0.2\times$ auxiliary dual-tightness and bound-status terms
stage 2	3,457 LPs of Train-20k , 6 passes, 48 LPs per step, AdamW at $3\times 10^{-4}$ , clip 1; checkpoint every 37 steps, chosen by paired solve time on the 283-LP selection split of Dev-20k
Decoder	entry threshold $10^{-8}$ of the column maximum, degree exponent $p=0.5$ , shifts $\{0,\pm 0.5,\pm 1,\pm 2,\pm 3\}$
Policies	MLP $84\to 128\to 128\to\|\mathcal{A}\|$ , SiLU, dropout 0.1, AdamW (weight decay $10^{-4}$ ), batch 256 LPs, loss clip $\pm 3$ , failures at $+3$ , last layer initialized to the unshifted start
CostStart-Shift	$\|\mathcal{A}_{1}\|=9$ ; 7,699 training LPs; learning rate $10^{-3}$ , 100 epochs, 3 seeds

Appendix

Table 14: Settings of the learned components and of the solver. Selection was always on development data or a held-out fifth of the training LPs, never on test data.

Axis	Effect on the emitted model	Cardinality
variant	the formulation itself	$129$
target_variables	dimensions re-derived, not padded	wide range
seed	fresh data at fixed size and structure	unbounded
feasibility_status	feasible / infeasible / unknown	3
relax_integer	a MIP, or its LP relaxation	2
bounds_to_constraints	bounds kept, or emitted as explicit rows	2

Appendix

Table 15: Orthogonal axes of the generated instance space. The final three are post- build_model transforms applied centrally, so they act uniformly across all formulations rather than being reimplemented per generator.

Requested	Formulations	Median ratio	Within $\pm 10\%$	Within $\pm 25\%$	Median build (s)
$50$	129	$1.000$	91 %	99 %	–
$200$	129	$1.000$	96 %	100 %	$0.052$
$1000$	129	$1.000$	97 %	98 %	$0.052$
$5000$	93	$1.000$	96 %	97 %	$0.052$
$20\,000$	78	$1.000$	90 %	91 %	$0.053$

Appendix

Table 16: Size fidelity and generation cost (

558

builds). The median ratio of achieved to requested variable count is exactly

1.000

at every scale. Median build time is flat at

{\approx}

52\text{,}\mathrm{ms}$$ from

200

variables upward; the build time at

50

variables is omitted because it absorbs per-formulation JIT compilation on first call. Fewer formulations were measured at the largest targets (see text).

Property (median)	Netlib	Synthetic	Assessment
Matrix density	$0.0079$	$0.0132$	close
Nonzeros per column	$4.23$	$3.71$	close
Nonzeros per row	$8.45$	$5.14$	close
Column-degree variability (CV)	$0.55$	$0.43$	close
Primal degeneracy	$0.196$	$0.094$	about half
Simplex iterations per row	$1.24$	$0.55$	less work

Appendix

Table 17: Structural comparison against Netlib (medians). Sparsity statistics agree closely; numerical range and degeneracy remain lower than in real instances.

Feature	Synthetic	Netlib
Matrix density	0.006–1.000	0.000–0.092
Nonzeros per column	1.96–55.98	2.18–14.24
Column-degree variability (CV)	0.00–2.40	0.11–1.23
Coefficient spread, $\log_{10}\|A_{ij}\|$	0.00–5.75	0.00–8.65
Fraction of entries equal to $\pm 1$	0.000–1.000	0.094–1.000
Primal degeneracy	0.000–0.800	0.000–0.841

Appendix

Table 18: Feature-space breadth, reported as the 5th–95th percentile interval over each corpus.

Category	#	Use	Formulations
airline_crew	1		standard
assignment	2		standard, workload_balance
bin_packing	2	train, test	heterogeneous, standard
blending	3	unseen	equipment_batches, multi_product, standard
container_loading	2	unseen	standard, two_dimensional_bin_packing
crop_planning	1	train, test	standard

Appendix

Table 19: The categories and formulations of SyntheticLPs.jl and their use in this paper.

Set	Variables	LPs	Classes	Use
Train-Small	50–2,000	114,874	37	predictor, stage 1
Train-20k	15k–25k	9,511	26 (25 with test LPs)	predictor stage 2 (3,457 LPs); policies and gates
Dev-20k	15k–25k	450	25	selection and ablations; half twinned with training
selection split	15k–25k	283 of Dev-20k	22	checkpoints, epochs and designs
Dev-50k	40k–60k	454	23	optimality check; policies at larger sizes
Test-20k	15k–25k	1,356	25	main result

Appendix

Table 20: Datasets. Sizes are requested numbers of variables. Every test set is disjoint from every training and development set by content hash, generator call and seed; the classes of Test-NewClass and Test-Adapt were never used in training.

	Test-20k (1,356 LPs)			Test-50k (382 LPs)			Test-80k
Method	iter.	time [95% CI]	W/L	iter.	time [95% CI]	W/L	time (81)
all-slack dual simplex	1.00	1.07 [0.87, 1.30]	12/13	1.00	0.99 [0.76, 1.30]	12/13	0.96
stock solver, presolve on	0.85	1.10 [1.06, 1.16]	3/22	–	–	–	–
classical crash	1.22	1.76 [1.19, 2.60]	9/16	–	–	–	–
Fan et al. (original budget)	0.50	1.10 [0.89, 1.38]	15/10	0.52	1.00 [0.78, 1.28]	15/10	0.96
Fan et al. (full budget)	0.49	1.10 [0.89, 1.35]	15/10	0.51	1.02 [0.78, 1.37]	15/10	0.96

Appendix

Table 21: Full version of Table 2 , with the ablation rows of CostStart-Shift and the supervised control (the predictor trained for one more pass over the 20k training data). Iterations relative to the all-slack dual simplex, charged time relative to the native solver; same conventions as Table 2 .

Figure 8: Per-class charged time on Test-50k (ratio to the native solver, geometric mean over the class’s LPs, all three windows; LP counts in parentheses). The predictor loses six classes; the shift policy and harm gate of CostStart-Shift turn four of them into wins, and the two remaining losses are classes where the primal simplex from a primal-feasible all-slack basis is hard to beat. Table 26 gives the same panel with more methods.

Method	time [95% CI]	W/L	iterations	summed	failures
W1 ( $\leq 10$ s): 1,052 LPs, 24 classes
native solver (reference)	1.00	–	0.86	1.00	0
all-slack dual	1.04 [0.85, 1.29]	10/14	1.00	0.91	0
stock solver, presolve on	1.13 [1.09, 1.18]	1/23	0.86	1.03	0
classical crash	1.84 [1.28, 2.72]	9/15	1.27	2.65	1
Fan et al.	1.09 [0.88, 1.37]	14/10	0.46	1.20	0

Appendix

Table 22: Charged time on Test-20k by window (the all-slack dual simplex’s time at generation). Time: class-balanced geometric-mean ratio to the native solver with 95% bootstrap interval (2,000 draws over classes, then generator instances) and classes won/lost; iterations: class-balanced geometric-mean ratio to the all-slack dual simplex of one plus the iteration count; summed: total charged time over that of the native solver; failures count at twice the window’s time limit (120, 600 and 3,600 s). Numbers are averaged within LP over two timing repetitions.

		baselines				CostStart
Class	LPs	all-slack	Fan et al.	Lu & Yan	predictor	Shift	Alg	Full
bin packing	50	0.46	0.96	1.00	0.83	0.54	0.50	0.74
crop planning	11	1.05	0.74	0.80	0.68	0.92	0.70	0.69
energy	104	0.74	0.79	0.81	0.58	0.64	0.53	0.50
facility location	37	2.92	2.07	1.63	1.39	1.19	1.02	0.91
graph optimization	156	1.26	1.09	1.12	0.76	0.69	0.36	0.63

Appendix

Table 23: Per-class charged time on Test-20k relative to the native solver: geometric mean over the class’s LPs of the per-LP ratio, all three windows, failures at twice the time limit, lowest entry per row in bold. The last rows give the class-balanced geometric mean over the 25 classes, the classes won/lost against the native solver, and the failures. Every learned arm runs the optimality check inline; numbers are averaged within LP over two timing repetitions.

					DSE pricing			Devex pricing
System	window	LPs	native	primal	$\delta<0$	$\delta=0$	$\delta>0$	$\delta<0$	$\delta=0$	$\delta>0$
CostStart-Full	W1	1,052	8.1	7.2	0.0	12.9	16.7	41.8	0.0	13.2
	W2	267	16.1	25.8	0.0	7.9	27.3	20.2	0.0	2.6
	W3	37	0.0	29.7	0.0	0.0	24.3	29.7	0.0	16.2
	all	1,356	9.4	11.5	0.0	11.6	19.0	37.2	0.0	11.2
CostStart-Alg	W1	1,052	13.9	12.6	8.6	32.1	32.8	–	–	–

Appendix

Table 24: Actions taken on Test-20k , as shares of LPs (%). Top: action groups by pricing rule and shift

\delta

; for CostStart-Shift the native column is the harm gate’s fallback, and for all three systems

\delta=0

under DSE includes the LPs that the novelty gate returns to the unshifted start. Bottom: the shift chosen by the shift policy of CostStart-Shift before the harm gate, and the gate’s fallback rate. Numbers are averaged within LP over two timing repetitions; actions and gate decisions are the same in every repetition.

predictor
	W1		W2		W3		all
Component	ms	%	ms	%	ms	%	ms	%
features	9.1	1.28	9.0	0.05	10.4	0.01	9.1	0.89
inference	6.7	0.99	8.9	0.05	11.1	0.01	7.0	0.69
decode	8.6	1.31	10.6	0.06	19.0	0.01	9.0	0.90
setBasis	5.5	0.70	9.6	0.05	8.8	0.01	6.3	0.49

Appendix

Table 25: Charged overhead per LP on Test-20k : median wall time in milliseconds and median share of the LP’s total charged time (%), by window. Decode includes the policy (with its novelty gate) and the crash; the harm gate (features and model) is charged on every LP, including those it hands to the native solver, which then need no setBasis. Total is the sum of the five components. Numbers are averaged within LP over two timing repetitions.

		baselines
Class	LPs	all-slack	Fan et al.	Lu & Yan	predictor	CostStart-Shift
bin packing	16	0.34	0.76	0.77	1.38	0.50
crop planning	4	1.04	0.58	0.63	0.46	0.65
energy	21	0.56	0.54	0.64	0.47	0.50
facility location	8	2.21	2.27	1.69	1.30	1.22
graph optimization	41	1.15	0.95	0.92	0.58	0.57

Appendix

Table 26: Per-class charged time on Test-50k relative to the native solver: geometric mean over the class’s LPs of the per-LP ratio, all three windows, failures at twice the time limit, lowest entry per row in bold. This panel runs without the optimality check; Fan et al. comes from a separate paired panel on the same LPs with its own native-solver solves. The last rows give the class-balanced geometric mean, the classes won/lost against the native solver, and the failures.

Label	time [95% CI]	iterations	summed time
instructions (I)	0.927 [0.877, 0.978]	0.943	0.918
iterations (N)	0.953 [0.899, 1.008]	0.932	0.947
wall time (T)	0.951 [0.907, 0.993]	0.955	0.963
I relative to N	0.973 [0.934, 1.010]	by repetition 0.9735, 0.9735, 0.9719
on the 202 LPs without a twin in training	0.939 [0.886, 0.984]
I relative to T	0.974 [0.951, 0.996]

Appendix

Table 27: Training-label ablation on the 381 W1 LPs of Dev-20k : three shift policies that differ only in the label (I: instructions, N: iterations, T: wall time under load). Charged time, iterations and summed time relative to the predictor (class-balanced, three timing repetitions), then paired contrasts between the policies.

Method	W1 (1,052)	W2 (267)	W3 (37)	all [95% CI]
per-class lookup, restricted actions	0.585	0.479	0.663	0.537 [0.406, 0.672]
per-class lookup, two actions (start or native)	0.658	0.480	0.802	0.608 [0.460, 0.744]
best single action on training (predictor start)	0.738	0.530	0.802	0.683 [0.497, 0.899]
CostStart-Shift	0.671	0.457	0.822	0.614 [0.466, 0.763]
CostStart-Alg	0.600	0.331	0.217	0.510
CostStart-Full	0.551	0.362	0.334	0.489 [0.369, 0.619]

Appendix

Table 28: Per-class lookup control on Test-20k (two timing repetitions averaged): charged time relative to the native solver by window, class-balanced, and paired contrasts. The lookup uses class labels; our methods do not.

	seed 101	seed 202	seed 303
predictor	0.714	0.711	0.708
+ own shift policy	0.642	0.647	0.649
+ own shift policy, check and harm gate	0.621	0.616	0.619
shift policy relative to its predictor	0.90	0.91 [0.85, 0.96]	0.92 [0.87, 0.96]

Appendix

Table 29: Full-pipeline seeds on Test-20k : charged time relative to the native solver (class-balanced, two repetitions averaged, check inline), and the shift policy’s time relative to its own predictor. The deployed predictor, trained on 20k training data that include duplicates, takes 0.683, and CostStart-Shift 0.614.

Decoder (same model)
Method	Decoder or seed	W1	W2
Lu & Yan	our crash	1.41	1.21
	top- $m$	1.82	1.72
Fan et al.	our crash	1.50	2.84
	top- $m$	1.69	2.27 (n.s.)
Training seed (full budget, our crash)

Appendix

Table 30: Decoders and training seeds of the reimplemented published methods on Dev-20k : charged time relative to our predictor (class-balanced; W1: 392 LPs, W2: 69 LPs). Top-

m

installs the

m

highest-scoring columns and lets HiGHS repair the set. n.s.: not significantly different from the crash.

Test-NewClass : 234 LPs, 6 classes absent from training (reference: predictor)
Method	vs. native solver	vs. reference
predictor	1.42 [0.95, 2.30]	–
CostStart-Shift , harm gate off (policy abstains on 234/234)	1.42 [0.96, 2.32]	1.00
CostStart-Shift	1.21 [0.97, 1.62]	0.85 [0.62, 1.08]
Fan et al. (full budget)	1.37 [0.96, 2.09]	–
Lu & Yan (full budget)	0.94 [0.49, 1.70]	–

Appendix

Table 31: Full version of Table 4 b. Charged-time ratios, class-balanced, with 95% intervals. Test-Adapt : the shift policy adapted with

n

labeled LPs per new class, against the unadapted policy, whose novelty gate falls back to the predictor’s start on these classes. Test-Variant is a subset of the Test-20k panel.

	Test-50k (309)		Test-80k (63)
Method	time [95% CI]	summed	time [95% CI]	summed
all-slack dual simplex	0.94 [0.72, 1.22]	0.87	0.90 [0.63, 1.28]	1.13
native solver with Devex	1.06 [0.89, 1.34] (6)	1.63	1.07 [0.93, 1.26]	1.28
predictor	0.65 [0.48, 0.87] (1)	0.72	0.83 [0.54, 1.27] (1)	1.70
predictor, Devex on every LP	0.66 [0.46, 0.96]	0.89	0.78 [0.48, 1.30] (1)	2.29
CostStart-Shift	0.58 [0.46, 0.72]	0.50	0.67 [0.48, 0.88]	0.84

Appendix

Table 32: Full version of Table 4 a: the W1 and W2 LPs of Test-50k (309 of 382 LPs) and Test-80k (63 of 81). Charged time relative to the native solver, class-balanced, with 95% intervals, failures in parentheses, and summed time. Every learned method runs the optimality check inline; gate evaluation is charged. The table omits W3, where Table 2 shows the largest gains.

Figure 9: Few-shot adaptation to unseen classes; the

n

axis is ordinal. Line: replay on the training LPs with one class held out at a time, instructions relative to the unshifted start after adapting with

n

labeled LPs of the held-out class (the 13 classes with long enough streams; Table 33 ). Squares: the charged panel on Test-Adapt , time relative to the unadapted policy (the predictor’s start).

$n$	0	10	25	50	100	200
13 classes with at least 220 LPs	1.098	0.965	0.952	0.946	0.934	0.924
all classes with enough LPs	1.076	0.944	0.932	0.929	0.912	0.924

Appendix

Table 33: Few-shot replay on the training LPs, one class held out at a time (three stream orders): instructions relative to shift 0 on the rest of the held-out class’s stream after adapting with

n

labeled LPs. At

n=200

only the 13 classes with at least 220 LPs qualify. The in-class reference is 0.929.

Linear Programming

Linear programming optimizes linear objectives under linear constraints, powering resource allocation, planning, and provable optimization methods.

See all 26 papers

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts
May 10, 2026Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed +2Neural Network Optimization Combinatorial Optimization
Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.
WARP: A Benchmark for Primal-Dual Warm-Starting of Interior-Point Solvers
May 7, 2026Dhruv Suri, Helgi Hilmarsson, Shourya BosePrimal-Dual Optimization Graph Neural Networks
Pravah
Learned Preconditioning for a Primal-Dual Interior-Point Method
Sep 28, 2026Abhinav Madabhushi, Jialin Liu, Minxin ZhangPrimal-Dual Optimization Learning to Optimize
Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida

May 10, 2026J/K move · Enter open · S save

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

Ilay Yavlovich, Jad Agbaria, Muhamed Mhamed, Nir Weinberger+1

Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology, Haifa, Israel.

Neural Network Optimization Combinatorial Optimization Learning-Augmented Algorithms

Open paper AskPDF arXiv

The Linear Assignment Problem is a fundamental combinatorial optimization task where classical exact solvers ensure optimality but suffer from an

\mathcal{O}(N^{3})

bottleneck, while recent neural approximations struggle with scalability and exactness. We propose a learning-augmented framework that accelerates exact solvers by predicting dual variables to warm-start the search, backed by a fallback mechanism to preserve worst-case guarantees. Central to our approach is RowDualNet, a lightweight, row-independent architecture that avoids the

\mathcal{O}(N^{2})

memory bottleneck of graph models, enabling scalable neural warm-starting up to

N=16{,}384

. Feasibility is guaranteed by construction via the Min-Trick mechanism, completely eliminating the need for costly iterative projections. Empirically, our method drastically reduces the search effort of the Jonker-Volgenant (LAPJV) algorithm, yielding robust zero-shot generalization with strict optimality and end-to-end speedups of over 2x on complex synthetic data, 1.25x on real-world tracking, and 1.5x on transportation networks.

Abstract

Linear Programming

Explore similar work

Learning-Augmented Scalable Linear Assignment Problem Optimization via Neural Dual Warm-Starts

WARP: A Benchmark for Primal-Dual Warm-Starting of Interior-Point Solvers

Learned Preconditioning for a Primal-Dual Interior-Point Method