Research map / Learning theory and algorithms / Combinatorial and search optimization
Solving Linear Programs with Fast Online Learning Algorithms
Wenzhi Gao, Dongdong Ge, Chunlin Sun, Yinyu Ye
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Initialize the sifting working problem with the online algorithm's output | CPLEX sifting solver · 13 large-scale benchmark LPs | overall CPU solve time: speedup on 6 of 13, neutral on 3, slowdown on 4 | Mixed |
| Initialize the working problem with the online algorithm on scp instances | Sifting solver · scp benchmark instances | basic columns identified: all basic columns with fewer than 5% of columns | Improved |
| Use online algorithm initialization on large benchmark LPs | Sifting solver · Benchmark LPs | basic column recovery and working problem size: more than 90% of basic columns with less than 20% of LP size | Improved |
| Slow-down on rail507 and rail516 from online initialization | Sifting solver · rail507 | CPU time (s): 0.50 -> 0.72 | Hurt |
| Online initialization on scpn2 | Sifting solver · scpn2 | CPU time (s): 51.38 -> 12.99 | Improved |
| Online initialization on s100 | Sifting solver · s100 | CPU time (s): 151.65 -> 38.30 | Improved |
| Online initialization on synthetic LPs | Sifting solver · Synthetic (m,n)=(1e2,1e6) | CPU time (s): 82.79 -> 38.20 | Improved |
| Online initialization on synthetic LPs with tau=0.10 | Sifting solver · Synthetic (m,n)=(1e2,1e6), sigma 15% | CPU time (s): 52.40 -> 53.79 | No clear effect |
| Increase variable duplication K from 1 to 32 (ablation) | Online LP algorithms (explicit and implicit) · Synthetic LPs | optimality gap and constraint violation | Improved |
| Increase duplication K when tau is close to 0 (ablation) | Explicit update · Synthetic LPs | performance gap to implicit update | Improved |
Closest papers by meaning
- Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods (ICML 2024 · similarity 0.87)
- Wait-Less Offline Tuning and Re-solving for Online Decision Making (ICML 2025 · similarity 0.87)
- The Geometry of Linear Program Compression: An Exact Characterization and Learning Algorithm (NeurIPS 2026 · similarity 0.85)
- Learning Generalized Linear Programming Value Functions (NeurIPS 2024 · similarity 0.84)
- Learning to Generate Projections for Reducing Dimensionality of Heterogeneous Linear Programming Problems (ICML 2025 · similarity 0.84)
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances (ICLR 2024 · similarity 0.84)
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.
