Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to Pivot as a Smart Expert
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 two pivot experts for the primal simplex method that use the optimal basis plus steepest-edge scores, and imitation-learns a GCNN pivot rule that beats classical pivot rules on NETLIB and combinatorial LP benchmarks.
Problem
Simplex pivot rules rely only on local information and produce long pivot paths; the theoretical strongly polynomial bound for pivot path length is open, and practical rules can be improved.
Approach
Use the optimal basis as global information to guide pivot selection (entering optimal-basis variables first, leaving non-optimal-basis variables first), combined with steepest-edge local scores; then imitate these experts with a bipartite-graph GCNN so the learned rule does not need the optimal basis.
Key results
- On 77 NETLIB instances, EXP wins 52 and EXP-II 54 versus 16 for steepest-edge; geometric mean pivots 112 (EXP) vs 198 (Dantzig) and 121 (SE).
- EXP-LEARN geometric mean pivots on CO test sets: SC 336 vs SE 419, CA 223 vs SE 266, FL 239 vs SE 242, IS 113 vs SE 114.
- Top-1 imitation accuracy ranges from 0.257 (IS) to 0.533 (SC) on validation sets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Expert I instead of SE | Primal simplex on NETLIB · NETLIB subset | geometric mean of pivot numbers: 121 -> 112 | Helped |
| Use Expert II instead of SE | Primal simplex on NETLIB · NETLIB subset | geometric mean of pivot numbers: 121 -> 118 | Helped |
| Imitate EXP with a GCNN instead of using SE | Primal simplex · SC test sets | geometric mean of pivot numbers: 419 -> 336 (±6) | Helped |
| Imitate EXP with a GCNN instead of using SE | Primal simplex · CA test sets | geometric mean of pivot numbers: 266 -> 223 (±3) | Helped |
| Imitate EXP with a GCNN instead of using SE | Primal simplex · FL test sets | geometric mean of pivot numbers: 242 -> 239 (±2) | Helped |
| Imitate EXP with a GCNN instead of using SE | Primal simplex · IS test sets | geometric mean of pivot numbers: 114 -> 113 (±0) | Helped |
| Remove local steepest-edge information from EXP (ablation) | EXP on primal simplex · NETLIB subset | geometric mean of pivot numbers: 112 -> 139 | Hurt |
| Use GCNN imitation instead of the expert | Primal simplex on CA · CA test sets | geometric mean of pivot numbers: 115 -> 223 (±3) | Hurt |
| Use GCNN imitation instead of the expert | Primal simplex on SC · SC test sets | geometric mean of pivot numbers: 268 -> 336 (±6) | Hurt |
Surprising findings
- Removing local information (NO-LOCAL, random choice among optimal-basis candidates) performs worse than classical steepest-edge on NETLIB, showing local information is essential.
- The learned rule gives only a slight lead over steepest-edge on FL and IS, and is slower in solving time than classical rules due to GCNN forward passes.
Limitations
- Experts require the optimal basis, which is unavailable in practice; the learned rule only approximates them.
- Experiments use a Python prototype simplex solver with small random CO instances and a subset of NETLIB.
- Learned rule's Top-3/Top-5 accuracy cannot be directly applied; it is slower in wall-clock time.
Experimental setup
Datasets: NETLIB subset (77 instances) Set covering random instances Combinatorial auction random instances Capacitated facility location random instances Maximum independent set random instances
Benchmarks: NETLIB subset set covering combinatorial auction capacitated facility location maximum independent set
Metrics: geometric mean of pivot numbers number of wins top-k accuracy solving time
Baselines: Bland's rule Dantzig's rule steepest-edge rule greatest improvement rule largest distance rule
Builds on: Gasse et al. 2019 GCNN bipartite encoding steepest-edge rule Klee-Minty cube variants
Closest papers by meaning
- Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision (ICML 2025 · similarity 0.87)
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.85)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.84)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.84)
- PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming (ICML 2024 · similarity 0.84)
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy (NeurIPS 2024 · similarity 0.82)
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.