- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
Basis-SDM formulates LP basis recovery as structured prediction over complete unordered bases rather than independent variable labels. It defines a determinantal distribution over bases that captures dependencies among selected columns and excludes singular sets. The paper further introduces certificate-based family supervision, where primal-dual optimal certificates define sets of compatible optimal bases and an exact KL objective is used to train the predicted distribution without enumerating the basis space. A Global KKT encoder and iterative distribution-update module are used to refine the basis distribution, followed by conditional-greedy decoding to obtain a full-rank basis. Experiments on 111 held-out LPs show substantial reductions in simplex cleanup iterations across IPM, PDHG, and direct-prediction settings, and integration into a hybrid GPU-PDLP MILP solver reduces mean solving time by 11.0% on 20 large MILPs. The paper also demonstrates that the same family-level distributional supervision framework can be extended to partial integer assignments.
Critical strengths
-
The prediction and supervision formulation is well matched to the mathematical structure of LP bases. The determinant factor naturally captures compatibility among selected columns and excludes rank-deficient selections, while certificate-derived target families account for degeneracy and multiple valid optimal bases. This is a principled structured-prediction formulation rather than simply a new neural architecture. The use of exact normalizers and inclusion probabilities to train against an entire compatible family is particularly elegant because it makes family-level supervision tractable without enumerating bases or relying on sampling-based gradient estimates.
-
The method is evaluated under several practically relevant settings, including IPM states, PDHG states, static direct prediction, coefficient perturbations, and integration into complete MILP solving. The reductions in simplex cleanup are substantial across multiple baselines.
Critical weaknesses
-
The paper does not fully isolate the contribution of the learned distribution transformation. A key missing baseline is to apply the same conditional-greedy decoder directly to the initial distribution without the learned update steps. Without this comparison, it is difficult to determine how much of the improvement comes from the learned updates rather than from the initial primal-dual weighting, the determinant-based distribution, or the decoder itself. The construction of the compatible teacher families is also not sufficiently characterized. The paper does not clearly report how the certificates are generated, what numerical tolerances are used to define and , how nonemptiness of is checked, or how often the resulting family actually contains multiple bases. Since the compatible family reduces to a single basis when , statistics on non-singleton families, family sizes, or target entropy are important for understanding the actual contribution of family-level supervision.
-
Some implementation and efficiency details needed to reproduce and evaluate the method are missing. Eqs. (26) and (29) use , but the paper does not explain how zero probabilities are handled, even though valid LPs can produce . The paper also does not clearly specify how column pairs are selected for the Transformer or how the number of pair tokens scales with problem size. The runtime evidence is incomplete in several important settings: the IPM experiment reports complete crossover time, but the PDHG results mainly report simplex cleanup iterations, while the direct-prediction timing measures solver time only after basis import. Since neural inference, matrix factorization, distribution updates, and decoding all introduce additional cost, complete end-to-end timing is needed to establish the practical speedup of the method.
Questions for authors
-
Could the authors report a no-update baseline in which the initial distribution is passed directly to the same conditional-greedy decoder, without the learned distribution-update steps? I would like to see this comparison under the same preprocessing, basis-import, simplex-cleanup, and timing settings for both the IPM and PDHG experiments. This would help determine how much of the improvement comes from the learned distribution transformation itself rather than from the initial primal-dual weighting, the determinant-based distribution, or the decoder.
-
Could the authors provide more details on how the compatible teacher families are constructed in practice? How are the primal-dual certificates generated, what numerical tolerances are used to define and , and how is the nonemptiness of checked? What fraction of the training certificates produces a non-singleton compatible family? Statistics such as family sizes, effective support, or target entropy would help clarify how often family-level supervision is actually different from single-basis supervision.
-
How are zero probabilities handled in Eqs. (26) and (29)? The pair feature uses , which becomes undefined when or . Does the implementation use masking, clipping, smoothing, or another numerical convention to handle these cases? Could the authors also clarify how column pairs are selected for the Transformer and how the number of pair tokens scales with problem size?
-
Could the authors provide complete end-to-end timing for the PDHG crossover experiment, including input preparation, neural inference, matrix factorization, distribution updates, decoding, basis validation/import, and simplex cleanup? For the direct-prediction setting, it would also be useful to report the complete prediction pipeline time rather than only solver time after basis import. For the 20-MILP experiment, could the authors provide paired per-instance results or repeated-run variability to show whether the reported 11.0% mean improvement is broadly distributed across instances?