Research map / Graph learning / GNN architectures
Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a tripartite-graph GNN with basic-variable and feasibility losses plus label preprocessing to predict LP initial bases that warm-start the HiGHS dual simplex solver faster than the bipartite-GNN SOTA.
Problem
Learning good initial simplex bases for general-form linear programs so that a warm-started solver needs fewer iterations and less time; prior GNN bipartite approaches predict bases close to optimal but this does not always speed up the solver.
Approach
A duality-inspired tripartite graph (variables, their bounds as dual-half nodes, constraints, and a global node) for general-form LP, combined with a basic-variable-selection loss, a multi-level feasibility loss using feasible bases sampled along the simplex path, and a preprocessing/masking scheme that resolves label inconsistency for equality constraints.
Key results
- On presolved Mirp1, the tripartite model with BMP reduces average solver iterations to 32.12% of default (bipartite SOTA 61.89%) and solving time to 41.99% (SOTA 73.31%).
- Geomean solving time on presolved datasets is 2.46 s for tripartite BMP vs 2.98 s for bipartite BMP and 3.35 s default.
- In cross-dataset evaluation the tripartite BMP model accelerates the solver in 6 of 12 settings versus 3 of 12 for the bipartite baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| warm start HiGHS with a predicted initial basis from Tripartite BMP instead of the default solve | HiGHS · presolved datasets (geomean) | solving time: 3.35 -> 2.46 | Helped |
| warm start HiGHS with Tripartite BMP instead of the bipartite GNN | HiGHS · presolved datasets (geomean) | iterations: 11664 -> 9482 | Helped |
| warm start HiGHS with Tripartite BMP instead of the bipartite GNN | HiGHS · presolved datasets (geomean) | solving time: 2.98 -> 2.46 | Helped |
| add basic variable selection loss (ablation) | Tripartite GNN · presolved datasets (geomean) | solving time: 2.80 -> 2.46 | Helped |
| add feasibility loss (ablation) | Tripartite GNN · presolved datasets (geomean) | solving time: 2.42 -> 2.46 | No clear effect |
| add label preprocessing (ablation) | Tripartite GNN · presolved datasets (geomean) | solving time: 2.40 -> 2.46 | No clear effect |
| add basic variable selection loss, feasibility loss, and label preprocessing (ablation) | Tripartite GNN · presolved datasets (geomean) | solving time: 2.93 -> 2.46 | Helped |
| add basic variable selection loss (ablation) | Bipartite GNN · presolved datasets (geomean) | solving time: 2.92 -> 2.75 | Helped |
| add feasibility loss (ablation) | Bipartite GNN · presolved datasets (geomean) | solving time: 2.92 -> 2.75 | Helped |
| add label preprocessing (ablation) | Bipartite GNN · presolved datasets (geomean) | solving time: 3.13 -> 2.75 | Helped |
Surprising findings
- A closer predicted initial basis does not always accelerate the solver; an initial basis very close to optimal can incur costly Phase I work.
- Removing the label preprocessing component (P) improved performance on Mirp1, where the closer basis was invalid and needed extra Phase I effort.
Limitations
- On simpler LP instances the added GNN overhead can slightly increase total solving time.
- Cross-dataset generalization is limited; only 6 of 12 settings accelerate the solver.
- Mirp2 default-mode acceleration is weak or negative for some variants, and some settings show slowdowns.
Experimental setup
Datasets: Load Balance (NeurIPS 2021 competition) Anonymous (NeurIPS 2021 competition) MIRP Mirp1 MIRP Mirp2
Benchmarks: Load Balance Anonymous Mirp1 Mirp2
Metrics: precision recall accuracy basic variable accuracy iterations ratio solving time ratio geometric mean speedup
Baselines: Fan et al. 2023 bipartite GNN default HiGHS dual simplex with logical basis
Builds on: Fan et al. 2023 bipartite GNN initial basis selection Ding et al. 2020 tripartite MIP representation Qasim et al. 2019 GNN message passing Gasse et al. 2019 bipartite MIP GNN
Closest papers by meaning
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.91)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.88)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.87)
- Learning to Pivot as a Smart Expert (AAAI 2024 · similarity 0.87)
- Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems (ICML 2025 · similarity 0.87)
- PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.