- 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
-
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.
-
The paper takes a careful approach to performance measurement and reports useful negative results.
Critical weaknesses
-
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.
-
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.
-
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
-
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?
-
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.
-
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?
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).
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.
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).