acceptodds
Under review as a conference paper at ICLR 2027

From Approximate to Vertices: Set Distribution Matching for Linear Programming Crossover

Abstract

First-order solvers such as PDLP substantially accelerate large-scale linear programming (LP). However, crossover procedures developed for interior-point solutions perform poorly on PDLP outputs, leaving costly vertex and basis recovery for industrial applications such as simplex reoptimization and tableau-based cut generation. We propose Basis-SDM to learn basis recovery from continuous solver states. We identify three challenges overlooked by variable-label supervision: a basis is an unordered set, its columns are interdependent, and degeneracy and multiple optima permit many correct bases. Basis-SDM addresses these challenges through a distribution over complete bases. It assigns order-invariant probabilities to sets; models column interactions through a determinant factor that excludes singular sets; and uses optimality certificates to define target distributions over compatible optimal bases. Shared updates move an initial distribution toward a target under exact KL supervision, followed by conditional-greedy basis selection for simplex cleanup. On 111 unseen LPs, Basis-SDM reduces cleanup iteration sGM from 367.99 to 43.66 relative to native COPT crossover with primal–dual hybrid gradient inputs, and from 518.52 to 4.74 with interior-point inputs. The KKT-adapted LP-GNN baseline obtains 274.40 on the latter, while Basis-SDM requires no cleanup on 64 instances. Controlled ablations demonstrate the benefit of supervising optimal-basis families. On 20 large MILPs, replacing native crossover in a hybrid GPU PDLP solver reduces mean complete solving time by 11.0%. Partial integer-assignment prediction further demonstrates the applicability of distributional supervision to other optimization decisions.

Primary area:
optimization
Keywords:
Linear programming, Crossover, Learning to optimize, Set distribution matching

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_GBPkOpenReview ↗
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
  1. 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.

  2. 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
  1. 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 qθ(0)q_{\theta^{(0)}} 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 PcP_c and ZcZ_c, how nonemptiness of EcE_c is checked, or how often the resulting family actually contains multiple bases. Since the compatible family reduces to a single basis when ∣Pc∣=m|P_c|=m, statistics on non-singleton families, family sizes, or target entropy are important for understanding the actual contribution of family-level supervision.

  2. Some implementation and efficiency details needed to reproduce and evaluate the method are missing. Eqs. (26) and (29) use log⁡(pdst/psrc)\log(p_{\mathrm{dst}}/p_{\mathrm{src}}), but the paper does not explain how zero probabilities are handled, even though valid LPs can produce psrc=pdst=0p_{\mathrm{src}}=p_{\mathrm{dst}}=0. 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
  1. Could the authors report a no-update baseline in which the initial distribution qθ(0)q_{\theta^{(0)}} 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.

  2. 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 PcP_c and ZcZ_c, and how is the nonemptiness of EcE_c 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.

  3. How are zero probabilities handled in Eqs. (26) and (29)? The pair feature uses log⁡(pdst/psrc)\log(p_{\mathrm{dst}}/p_{\mathrm{src}}), which becomes undefined when psrc=0p_{\mathrm{src}}=0 or pdst=0p_{\mathrm{dst}}=0. 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?

  4. 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?

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

The paper proposes Basis-SDM, a learned crossover method that predicts a full LP basis from the state of an IPM or PDHG solver.

  • Model. Bases are modeled with a determinantal law q_θ(B) ∝ exp(2Σ_{i∈B} θ_i) · det(A_B)². This law holds exactly for nonsingular m-column sets and does not depend on the selection order.
  • Targets. Training targets come from optimality certificates: the initial law is conditioned on the family of bases compatible with a primal–dual optimum (P_c ⊆ B ⊆ Z_c).
  • Training. Because the model and teacher share the determinant factor, the KL divergence and its gradient (2(π(θ) − π*)) can be computed exactly from QR factorizations, with no enumeration or sampling. A GNN/Transformer module updates the potentials four times, and conditional-greedy decoding returns a basis for simplex cleanup.
  • Evaluation. Experiments cover 111 LPs with IPM and PDHG inputs, direct prediction from (A, b, c), coefficient perturbations, supervision ablations, 20 MILPs solved inside SCIP with a hybrid GPU-PDLP backend, and an extension to partial integer assignments.
Critical strengths
  1. Well-motivated formulation. The paper identifies three issues with variable-status supervision: order dependence, interdependent column choices, and multiple optimal bases. The determinantal set distribution addresses all three, and rank and cardinality hold by construction.
  2. Exact, sampling-free supervision of whole optimal-basis families. Defining the teacher by conditioning the initial law keeps it in the closure of the model family, and the factor-based computation avoids basis enumeration. The proofs I checked are correct (normalization and support, order-independent sampling, and the KL lower bound on family mass in Proposition 3).
  3. A convincing core ablation. With the encoder, updates, and decoder held fixed, supervising compatible families instead of a single optimal basis reduces cleanup sGM from 91.48 to 4.74 (Table 6). This isolates the paper's central idea.
  4. Broad, failure-aware evaluation. Several input types are tested, failures are penalized and counted, and the method has zero failures in every LP setting.
Critical weaknesses
  1. Iteration counts are not comparable across methods, and the headline overstates the gain.

    • Basis-SDM's count leaves out the work done by the network and decoder. HiGHS's count leaves out its crossover pushes. COPT reports its own native counter.
    • The abstract leads with 518.52 → 4.74 against COPT, but the only timing reported (Table 2) shows a much smaller gap. Basis-SDM takes 0.0359 s vs 0.0438 s for COPT on medium LPs, and 0.3075 s vs 0.5016 s on large ones. That is 1.2–1.6×, not two orders of magnitude.
    • Section 5.2 compares timing against Smart crossover (0.3387 / 2.0097 s) rather than against the faster native COPT.
    • Please make wall-clock time the headline metric and compare against the strongest baseline on each metric. For IPM iterations, that is Smart → HiGHS (37.06).
  2. There is no timing for the PDHG setting, which is the paper's main motivation. Table 3 reports iterations only. Since the case for learned crossover rests on first-order outputs, end-to-end time (prediction + decoding + cleanup) relative to native COPT and HiGHS at the same PDHG endpoints is essential. The hardware used for timing (CPU model, threads, whether inference runs on a GPU) is also not stated anywhere.

  3. The native-crossover baselines may be handicapped by their inputs.

    • The IPM state is the last iterate before relative complementarity drops below 1e-4 (Appendix C.2). Native IPM crossover is designed for, and normally called after, convergence to much tighter tolerances.
    • HiGHS native crossover receives only the primal solution, while COPT also receives dual values and reduced costs.
    • Please add native crossover from IPM solutions converged to the solvers' default tolerances, and give HiGHS dual information where its interface allows. Otherwise, explain why the chosen setting is the relevant one in practice.
  4. The tested scale does not match the motivation. PDLP matters most for very large LPs. Here, "large" means n > 8,000 (16 instances). The method relies on QR factorizations that cost O(nm²), and Appendix E says that around 80,000 rows approach GPU memory limits. Please state the current scale limit clearly in the main text, report how runtime and memory grow with m and n, and discuss sparse or low-rank alternatives.

  5. The provenance of the test set is unclear. The paper names the training sources (Netlib; Mészáros MISC/STOCHLP) but not where the 111 test LPs come from. In addition, about 99% of the 11,702 training instances are augmentations or generated variants of 125 originals (Table 8). If the test LPs come from the same collections, related instance families may fall on both sides of the split. Please list the test sources and confirm that the split is by family.

  6. An ablation separating the determinantal decoder from learning is missing. The initialization θ⁽⁰⁾ = ½ log(x/s) followed by conditional-greedy decoding is already a non-learned crossover heuristic, closely related to the diagonal-weighting and volume-maximization baselines. Please report results with zero learned updates (T = 0) and with T ∈ {1, 2, 4, 8}. That would show how much of the improvement comes from the decoder and how much from learning.

  7. The downstream experiments are statistically thin.

    • MILP (Table 7). There are 20 instances, apparently one run each, summarized by arithmetic means with no per-instance results or seeds. An 11% difference in mean time is within typical MILP performance variability. Please report shifted geometric means, per-instance results, several seeds, and the share of total time spent in crossover.
    • Partial assignments (Section 6/Appendix D). Results use only the 8 validation problems, while the 16 reserved test problems are not reported. Also, family supervision yields worse final SCIP scores than the quality-weighted target and the LP rule (59.30 vs 56.27/56.99 at 10 s; 69.65 vs 67.40 at 2 s). This undercuts the claim of "broader applicability". I suggest evaluating on the test split or presenting this section as preliminary.
  8. Baseline coverage.

    • Lu & Yan (2025) is excluded because its code is unreleased. As the most closely related learned method, a reimplementation would be informative.
    • The KKT-adapted LP-GNN fails on 20 of 111 IPM instances. Please confirm that its rank-repair step and training were adequately tuned.
    • Smart's PDHG adapter fails on 65 of 111 instances, so its failure-penalized sGM (1102.78) should not count as evidence.
  9. The theory mostly assembles known results. Cauchy–Binet normalization, projection-DPP conditioning, the exponential-family identity ∇log Z = E[1_B], and −log q(E) ≤ KL are all standard. They are correct, but they should be presented as tools. The novel element is the certificate-conditioned target.

  10. Minor issues.

    • Table 2 omits the Small group and an "All" column.
    • Figures 1–2 are very dense.
    • The submission has no code-availability statement.
Questions for authors
  1. What is the end-to-end wall-clock time of each method with PDHG inputs, and on what hardware?
  2. How do native COPT and HiGHS crossover perform from IPM solutions converged to default tolerances?
  3. Where do the 111 test LPs come from, and is the train/test split by family?
  4. What does the untrained determinantal decoder (T = 0) achieve, and how does performance change with the number of updates?
  5. For the MILP study, can you report multiple seeds, per-instance results, and the fraction of time spent in crossover?
  6. What are the partial-assignment results on the 16 reserved test problems?
  7. How does training behave on highly degenerate LPs where Z_c is very large and the teacher is close to uniform over many bases? Were there failure cases?
  8. How do runtime and memory scale with m and n, and what is the practical size limit?
Reviewer_n5A4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Basis-SDM, a learning-based crossover method that predicts a complete LP basis from an approximate IPM or PDHG state. It uses a determinantal point process (DPP) to represent distributions over full-rank bases, derives target distributions from primal-dual optimality certificates over compatible optimal-basis families, and trains a shared iterative update module with exact KL supervision. A conditional-greedy decoder returns a complete basis for simplex cleanup. Experiments on 111 unseen LPs show large reductions in cleanup iterations, and additional experiments cover PDHG crossover, direct prediction, perturbations, and MILP solving.

Critical strengths
  1. Well-motivated formulation. The paper correctly identifies key limitations of variable-status supervision: order invariance, column dependence, and multiple optimal bases. The DPP formulation naturally enforces cardinality and full rank, while certificate-derived families avoid single-basis labels.

  2. Strong empirical results on the primary task. Basis-SDM achieves cleanup sGM 4.74 on IPM crossover, versus 37.06 for Smart Crossover and 518.52 for native COPT, with zero cleanup on 64 of 111 LPs. PDHG and direct-prediction results are also substantial.

  3. Convincing evidence for family-level supervision. Table 6 is a valuable controlled comparison: with architecture, inputs, updates, and decoder fixed, family supervision reduces cleanup sGM from 91.48 to 4.74 relative to single-basis supervision.

Critical weaknesses
  1. The contribution of DPP-based joint modeling is not sufficiently isolated. The DPP interaction structure is fixed by the LP matrix; the model mainly learns column potentials. Exact normalization and the KL gradient are standard DPP/exponential-family identities. The novelty lies more in integrating certificate-family supervision with DPP tractability than in a new distribution-learning mechanism. The independent-score baseline changes supervision and decoding, so it does not isolate the benefit of joint modeling. A rank-aware joint predictor trained with the same family supervision, encoder, and budget would strengthen the claim.

  2. A single certificate family need not cover all optimal bases, and teacher selection may bias supervision. Eq. (9) selects one teacher for the whole path, and Proposition 3 guarantees mass only for the selected family. Other equally optimal bases outside that family are not explicitly recognized. The paper should report how many certificate families are available, how much they overlap, and whether multi-teacher or union-family objectives help.

  3. The necessity of the iterative architecture and decoder is unclear. The paper does not ablate one, two, and four update steps, nor compare against direct prediction of final potentials under the same family supervision. Conditional-greedy decoding is also not compared with simpler rank-aware selection on the same learned potentials.

  4. Runtime and generalization evidence are incomplete. Direct-prediction timing excludes feature preparation, neural inference, decoding, and basis import, so end-to-end runtime advantage is not fully established. The integer-assignment extension uses only eight validation instances, not the 16 reserved test instances, and improved feasible-start generation does not translate into the best final SCIP score in Table 12.

Questions for authors
  1. Can the authors compare against a simpler rank-aware column-selection model trained with the same certificate-family supervision, features, encoder, and budget?

  2. How many distinct compatible optimal-basis families are typically available, and how much do they overlap? Would multi-teacher or union-family supervision improve results?

  3. How do one, two, and four distribution updates compare? Would direct prediction of final potentials perform comparably? How does conditional-greedy decoding compare with simpler rank-aware decoding?

  4. Can the authors report end-to-end runtime for direct prediction and results on the 16 reserved integer-assignment test instances with matched tuning budgets?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.