acceptodds
Under review as a conference paper at ICLR 2027

Learning Warm Starts for the Simplex Method from Measured Solver Cost

Abstract

Learned initial bases for the simplex method predict which variables are basic at optimality, before handing the resulting basis to an off-the-shelf solver. Prior work has shown that while solutions built from a well-tuned GNN-based architecture can successfully reduce iteration-count, the time they save may fall well short of the iterations they save. 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 the 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, and 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 show that on 25 classes of linear programs, a strong supervised basis predictor removes two thirds of the iterations of the HiGHS dual simplex but only a third of its time. 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, or no warm start. On unseen LPs of the training classes, including LPs four times the training size, CostStart roughly halves the solve time of HiGHS and is 1.4 to 2.2 times as fast as two published methods retrained on the same data.

Primary area:
optimization
Keywords:
learning-to-optimize, simplex algorithm, initial basis prediction, linear programming

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_nNt6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper examines why learned simplex warm starts can reduce the number of pivots without achieving comparable runtime improvements. It constructs a family of LPs in which initial bases with the same overlap and the same number of pivots can still incur asymptotically different amounts of solve-vector work. The authors also study how basis overlap and iteration counts relate to instruction counts and runtime. Their proposed method, COSTSTART, combines a supervised GNN for basis prediction and a triangular crash decoder with a lightweight cost-trained policy that selects score shifts, the simplex algorithm, the pricing rule, or whether to use a learned start at all. Deployment gates and optimality checks are used to mitigate failures. The experiments cover larger instances from trained problem classes, held-out variants, unseen classes, adaptation, and a separate public benchmark.

Critical strengths
  1. The paper provides a useful analysis of why improvements in optimization proxies do not necessarily translate into runtime gains. Theorem 1 shows that even when basis overlap and pivot count are held fixed, the amount of solve-vector work can differ asymptotically. The empirical study also examines multiple starting bases for the same LP, rather than relying solely on aggregate comparisons across different problems.

  2. The paper takes a careful approach to performance measurement and reports useful negative results.

Critical weaknesses
  1. The GNN predictor alone already reduces runtime to 0.68× that of native HiGHS, while the full system achieves 0.49×. The shift policy adds little once the harm gate is enabled, and a single selected action captures most of the gain on the public benchmark. It is therefore unclear how much of the overall improvement comes from instance-specific cost learning itself, rather than from the basis predictor and simpler selection or fallback strategies.

  2. The authors appropriately froze the shift-only system before generating fresh test sets. However, the ALG and FULL variants were developed after the TEST-20K pilot and TEST-NEWCLASS panel had been run, and the optimality check was introduced after inspecting failures on TEST-50K. Moreover, the held-out-variant evaluation uses a harm gate trained on those variants and dual forms. This makes the evidence for the final system's generalization less conclusive.

  3. Although the paper includes a separate public benchmark, it covers only four datasets and 80 test instances, with per-dataset fine-tuning. More importantly, the learned methods are slower than native HiGHS on the six unseen problem classes. Adapting to new classes requires labeled examples or a relatively long stream of online observations, and the reported gains do not consistently appear on shorter streams. These results leave the practical transferability of the method to new LP families insufficiently established.

Questions for authors
  1. Can the authors freeze the entire deployed pipeline—including the predictor, decision policy, both gates, and the optimality check—and evaluate it on a newly generated test panel without any subsequent design or threshold changes? For the held-out-variant evaluation, can all learned components, including the gates, be trained and selected without access to those variants and dual forms?

  2. On the same untouched test panel, how much additional benefit does the learned policy provide over the same predictor paired with (i) a fixed best action selected on training or development data, (ii) a per-class best-action lookup, and (iii) a simple feature-based algorithm selector? Please report paired per-instance differences in runtime and instruction count, with uncertainty estimates, for instruction-trained and iteration-trained full policies using identical action sets and training budgets.

  3. What is the end-to-end break-even workload for the full CostStart pipeline on realistic streams of known-class LPs, after accounting for predictor training, action-cost collection, gate training, and per-instance deployment overhead? Beyond the few-shot adaptation estimates in Appendix J.1, how many LP solves are required to amortize these costs, and how does this compare with native HiGHS on raw, unpresolved inputs (including presolve) and, where applicable, reuse of a previous solver basis for related LPs?

1 comment
AuthorsOpenReview ↗

Response to Reviewer nNt6

Thank you for the careful review and the precisely specified experiments, which we ran as asked.

W2 / Q1: Freeze everything and re-evaluate. We froze the predictor, the policies, both gates, the optimality check and all thresholds, then generated a new panel from new seeds and ran the pipeline once. On the new LPs the deployed system takes 0.53x native [0.39, 0.67], against 0.52x submitted, with no failures; every method also run in the submission reproduces within 3% at this size (Appendix I.1). Appendix H gives the complete chronology, including two exposures to the larger test sets, neither of which applies to the new panel. The optimality check was implemented after the first Test-50k pass, as you note; its rule and threshold were fitted on development data only.

Held-out variants, every component blind. The submission's 0.56x native on Test-Variant used a harm gate that had seen these types. With every learned component retrained without the ten variants and six dual forms, the system takes 0.57x [0.29, 0.86], so the exposure did not inflate the reported number. There the policy abstains and the gain comes from the predictor and the harm gate (Appendix J).

W1 / Q2: Where the gain comes from. Every row uses the same predictor, 20 actions and training LPs (and the same budget for the two policies), and was frozen before the new panel was solved. The last two columns are the policy's cost divided by the row's, paired per LP (below 1 favors the policy).

Decision rule on top of the predictorTime vs. nativeTime, paired [95% CI]Instructions, paired [95% CI]
(i) Best fixed action0.690.71 [0.61, 0.81]0.68 [0.60, 0.78]
Policy trained on iteration counts0.600.81 [0.70, 0.93]0.78 [0.67, 0.89]
CostStart-Full policy (instruction counts)0.49
(ii) Per-class lookup0.510.95 [0.87, 1.04]0.93 [0.86, 1.00]
(iii) kNN on plain LP statistics0.441.10 [1.04, 1.18]1.08 [1.03, 1.15]

Before the harm gate. Behind the deployed gates the best fixed action, the policy, the lookup and the kNN take 0.63x, 0.53x, 0.55x and 0.51x.

The gain over the predictor comes from choosing among the actions on measured cost: no fixed action improves on the predictor's start (0.69x), a cost-trained choice reaches 0.44x to 0.51x whichever rule makes it, and the policy trained on iteration counts stops at 0.60x. As you suspected, the instance-level network is not what carries it: the per-class lookup ties the policy, and the kNN is about 10% faster and ties it behind the deployed gates (Appendix I.3). The revision states the claim accordingly (Section 6.1). On the public benchmark each dataset is one family, so the best single action is the family-level choice.

W3: Public benchmark and new classes. The public benchmark now has eleven datasets; on the seven new ones (four real-world) the method takes 0.57x the dual simplex's time, against about 1.7x for the two published methods. Per-dataset training is the published protocol, and with our pretrained predictor it needs little data: ten training LPs per dataset, with their action costs, give 0.60x, against 0.89x with a predictor trained from scratch (Appendix K). We do not claim zero-shot transfer to unseen classes, as the abstract now says. Adaptation no longer needs cost labels: every ordinary solve returns an optimal basis, and fine-tuning the predictor on a class's first 50 such solves brings the time from 1.22x to 0.73x native [0.55, 0.92] on held-out LPs. Pooled over the classes this pays back only after about 1,000 LPs per class. A classical crash start does as well on these six classes (0.68x), although it is 1.78x native on the training classes (Appendices I.1, J).

Q3: Break-even, raw inputs and basis reuse. The deployed system saves 7.65 s per LP on the Test-20k mix (median 0.14 s; long solves supply the mean), with per-LP overhead already charged.

One-time costLPs to repay it
From scratch (381 core-hours + 11.3 H100-hours)about 350,000
Predictor given (381 core-hours)about 179,000, or 7,000 per class
Predictor given, 250-LP cost table (18 core-hours)about 8,500

In compute terms the from-scratch cost is repaid at about 1,400 core-hours of native solving. Half of it is the exhaustive cost table; the 250-LP row is a lower bound, since it assumes the full system's saving. GPU hours count as 32 core-hours each (Table 31); LP generation and the predictor's basis labels are not counted. From raw inputs with presolve and postsolve charged, CostStart takes 0.61x stock HiGHS (Appendix I.4). Reusing a previous optimal basis is better for perturbed copies of one model, but mostly undefined across distinct instances, whose dimensions differ; for streams of distinct instances a learned start is the tool (Appendix L).

Reviewer_dHU6OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates why learned warm starts for the simplex method often yield much smaller runtime savings than iteration reductions. It provides a theoretical construction showing that starts with identical optimal-basis overlap and pivot counts can have substantially different computational costs, supported by empirical analysis of HiGHS.

Motivated by these observations, the authors propose CostStart, combining a supervised GNN basis predictor with a cost-trained policy that selects initialization and solver configurations. On unseen LPs from training classes, the deployed system achieves approximately 0.52× the runtime of native HiGHS, substantially outperforming prior learned approaches.

Critical strengths
  1. The distinction between iteration count and actual computational cost is practically significant. The theoretical construction, solver experiments, and within-LP analysis provide complementary evidence.

  2. Training the decision policy using measured instruction counts, rather than iteration counts, directly addresses the identified problem. The ablation studies support this design choice.

  3. The paper accounts for inference and initialization overhead, uses class-balanced statistics and confidence intervals, and provides extensive comparisons and negative results. The authors are also transparent about several limitations.

Critical weaknesses
  1. Presolve has to be applied before the proposed method. This may make the proposed method less useful in practice.
  2. Unclear incremental benefit of the learned policy. A per-class lookup baseline achieves 0.54× runtime, close to CostStart-Full's 0.49× without the harm gate and 0.52× with it. The overall difference is not statistically significant. Furthermore, the improvement of CostStart-Shift over the predictor mainly comes from the harm gate.
Questions for authors
  1. Can the authors clarify the size and outcomes of the TEST-20K pilot, and which design decisions for CostStart-Alg and CostStart-Full were influenced by it?

  2. How much does the learned decision policy improve over per-class action selection on held-out problem variants? Can its benefit be distinguished from implicit class recognition?

  3. Can the authors provide more evidence on real-world LPs with standard presolve enabled, ideally including another simplex implementation?

1 comment
AuthorsOpenReview ↗

Response to Reviewer dHU6

Thank you for the detailed review, which led to several of the main experiments in the revision.

W1: Presolve. The learned start is applied after presolve, which is also where solvers apply their own crash bases. We now measure the full path from the raw LP, with presolve and postsolve charged, against stock HiGHS with presolve on: CostStart takes 0.61x its time [0.47, 0.74] and is faster on 21 of 25 classes. Presolve and postsolve are about a fifth of our end-to-end time, which is why the solve-only 0.50x becomes 0.61x (Appendix I.4).

W2: Incremental benefit of the learned policy. The new panel separates what the decision layer contributes from how the decision is made. Every row uses the same predictor, 20 actions and training LPs, and was frozen before the panel was solved.

Decision rule on top of the predictorTime vs. nativePolicy's time / this rule's, paired [95% CI]
Best fixed action0.690.71 [0.61, 0.81]
Policy trained on iteration counts0.600.81 [0.70, 0.93]
Policy trained on instruction counts (CostStart-Full)0.49
Per-class lookup (needs class labels)0.510.95 [0.87, 1.04]
kNN on plain LP statistics0.441.10 [1.04, 1.18]

Before the harm gate; a ratio below 1 favors the policy. Behind the deployed gates the policy, the lookup and the kNN take 0.53x, 0.55x and 0.51x.

Choosing the start, algorithm and pricing rule per LP from measured cost takes the predictor's 0.69x to 0.49x. No fixed action does this, and the same policy trained on iteration counts reaches only 0.60x. How the choice is made matters much less at this size, which agrees with your reading: a per-class lookup on the same cost table ties the policy, and a kNN selector is about 10% faster and ties it behind the deployed gates. Our claim is therefore that deciding on measured cost over these actions is what works, with the policy as one way of doing it, and the revision says so (Section 6.1, Appendix I.3). We agree that CostStart-Shift's gain over the predictor comes mostly from the harm gate, as Section 6.1 notes.

Q1: The pilot. The pilot ran 400 LPs of the shortest window and 80 of the next, with no algorithm or pricing action among its arms; its outcomes are now in Appendix H. CostStart-Shift was frozen before it. The algorithm actions of CostStart-Alg and CostStart-Full were motivated by the Test-NewClass panel and the pricing actions by development data, and neither design was based on the pilot results. The new panel, generated after every component was frozen, reproduces the submitted results.

Q2: Held-out variants and class recognition. We retrained every learned component, gates included, without the ten held-out variants and six dual forms. The submission reported 0.56x native on Test-Variant with a harm gate that had seen these types; fully blind, the system takes 0.57x [0.29, 0.86], and 0.58x on a new held-out slice, so the gate's exposure did not inflate the reported number (a system trained with these types takes 0.37x). On these LPs the policy abstains, so the gain comes from the predictor and the harm gate, and it is level with a per-class lookup fitted on the same blind data. On class recognition: on seen families the family is almost perfectly recoverable from the policy's input and the policy ties a per-class lookup, so we do not claim a benefit beyond a class-level rule, which it matches without labels (Appendices I.3, J).

Q3: Real-world LPs and another solver. In Gurobi and CPLEX the predictor's start, with nothing retrained, already shows the paper's effect: iterations fall by about two thirds, but each becomes roughly twice as costly. With the decision layer retrained on each solver's own deterministic cost, CostStart takes 0.59x the time of Gurobi and 0.52x of CPLEX, each running its default algorithm with no start and its own presolve off on the same HiGHS-presolved LPs, and is faster on 23 of 25 classes in each; in CPLEX the start alone gives only 0.85x, so the decision layer matters most there (Appendix I.5). On public data, end to end from the raw files with presolve charged and against stock HiGHS, the per-dataset system takes 0.76x on Lu & Yan's four datasets and 0.42x on the seven new families, or 0.62x without one family on which stock HiGHS is anomalously slow. Without adaptation the frozen system does not transfer to heterogeneous collections such as Netlib and MIPLIB (1.19x stock HiGHS), which is the scope the revision now states (Appendices I.4, K).

Reviewer_RyC2OpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a data-driven approach to select basic variables for the simplex algorithm. The central observation is that iteration savings is not equivalent to wall-clock saving. This paper proposes to map basic set prediction to measured instruction counts, which correlates well with wall-clock time. Additional guardrails at deployment time prevents applying predictions on instances that are out of distributions. Empirical evaluations show that COSTSTART reduces solving time and generalizes to larger instances.

Critical strengths

This paper describes the central observation well and designs COSTSTART to address the issue. The method is well-motivated and the empirical evaluations provide good validation evidence.

Critical weaknesses

The generalization section (section 6.3) points out the generalization is mainly larger scale problems from trained classes instead of to new classes of problems. It is also unclear whether the problems are realistic problems.

Questions for authors
  1. Equation (1): why is this particular decomposition chosen?

  2. Line 267: why does this particular greedy selection approach used?

  3. Section 2 has two missing references.

1 comment
AuthorsOpenReview ↗

Response to Reviewer RyC2

Thank you for the review and the specific questions.

Generalization. You are right that the evidence covers new instances, larger sizes and held-out variants of the training classes, and not new classes without adaptation; the abstract, introduction and limitations now state this scope. Two points of context. First, the two published methods we compare with train one model per dataset and test it on the same generator, whereas CostStart is a single model for 25 problem classes, and a new test panel generated after every component was frozen reproduces its results (general comment). Second, the revision adds an adaptation route for new classes that needs no extra solves: every ordinary solve returns an optimal basis, which is a training label for the predictor. Fine-tuning on the first 50 such solves of an unseen class brings the time from 1.22x to 0.73x the native solver's time on held-out LPs (Appendix J). On new public datasets, ten training LPs per dataset, with their action costs measured, recover nearly all of the gain (Appendix K).

Realism. The LPs come from domain formulations (transportation, blending, scheduling and others), so their constraint structure follows standard models and only the data are sampled; Appendix M compares them with Netlib (similar sparsity, less degenerate, a narrower range of coefficients). For real data we added seven public dataset families from Distributional MIPLIB, four of them real-world, under the per-dataset protocol of the published methods. There CostStart takes 0.57x the dual simplex's time (0.51x on the four real-world families), against about 1.7x for the two published methods (Appendix K).

Q1: Why Eq. (1)? Solve time is the product of the number of iterations, the time per iteration and an overhead factor for producing and installing the start. Eq. (1) is that identity in logs, so the three terms add up exactly and show where a speedup comes from. Learned starts cut iterations sharply but make each one costlier, so without the split a weak time ratio cannot distinguish a weak start from a strong start with expensive iterations (Section 6.2).

Q2: Why the greedy decoder? It is a triangular crash in the classical style (Bixby, 1992; Gould & Reid, 1989), chosen for three reasons: the basis is nonsingular by construction, so no repair is needed; it runs within the overhead charged in every timing; and shifting the scores changes how many predicted columns it admits, which gives the policy a lever. A new ablation shows that both of its scoring ingredients matter: removing the discount for dense columns or the comparison with the displaced slack costs 30% and 41% more instructions, respectively (Appendix D).

Q3: Missing references. Thank you. Both were citations of Lu & Yan (2025) that printed as "(?)"; they are fixed.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the response

We thank the reviewers for their careful and constructive reviews.

CostStart warm-starts the simplex method in two steps. A single basis predictor, shared across 25 problem classes, proposes a starting basis. A small policy then decides how to use it: how much of the predicted basis to keep, which algorithm and pricing rule to run, or whether to skip the warm start altogether. We train this policy on measured solver cost, because saving iterations does not always save time, an observation all three reviewers found of interest. On unseen LPs from the training classes, CostStart roughly halves the solver's time, while two published methods retrained on the same data save little or no time.

The reviews raised three main questions, and we ran new experiments for each.

Do the results hold on fresh data? We froze every deployed component, generated a new test panel from new seeds, and ran the pipeline once. The deployed system takes 0.53x the native solver's time, against 0.52x in the submission.

Where does the gain come from? From the predictor, whose start alone takes 0.69x native, and from deciding how to use it on measured cost, which brings this to 0.49x (0.53x with the safeguards for unfamiliar LPs). The same policy trained on iteration counts reaches only 0.60x. On this panel a kNN selector is about 10% faster and ties the policy behind the deployed gates, so the gain rests on the action set and the cost label rather than on the form of the selector.

How far does it carry? The gains hold with presolve charged end to end, in two commercial solvers once the decision layer is retrained on their cost, and on seven more public dataset families, where ten training LPs per dataset are nearly enough once the pretrained predictor is given. We do not claim zero-shot transfer to new problem classes, as the abstract, introduction and limitations now state, or to heterogeneous collections such as Netlib (Appendix K). On new classes, fine-tuning the predictor on the optimal bases that ordinary solves already return turns the zero-shot slowdown into a gain.

SettingTime ratio [95% CI]
New panel, training size, vs. native HiGHS0.53 [0.39, 0.67]
New panel, 2.5x and 4x the training size0.53 and 0.43
Raw LP with presolve and postsolve charged, vs. stock HiGHS0.61 [0.47, 0.74]
Gurobi 13 and CPLEX 22.1 on presolved LPs, each vs. its default algorithm with no start0.59 and 0.52
Seven new public dataset families, predictor fine-tuned per dataset, vs. dual simplex0.57 [0.53, 0.61]
The same with ten training LPs per dataset0.60 [0.56, 0.65]
Unseen classes, zero-shot -> after fine-tuning on 50 solved LPs1.22 -> 0.73

Based on the feedback we received, we have made targeted edits to the paper, which are highlighted in blue, and significant additions to the appendix to include the new experimental results.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.