Timezone: »
Poster
Solving Linear Programs with Fast Online Learning Algorithms
Wenzhi Gao · Dongdong Ge · Chunlin Sun · Yinyu Ye
This paper presents fast first-order methods for solving linear programs (LPs) approximately. We adapt online linear programming algorithms to offline LPs and obtain algorithms that avoid any matrix multiplication. We also introduce a variable-duplication technique that copies each variable $K$ times and reduces the optimality gap and constraint violation by a factor of $\sqrt{K}$. Furthermore, we show how online algorithms can be effectively integrated into sifting, a column generation scheme for large-scale LPs. Numerical experiments demonstrate that our methods can serve as either an approximate direct solver, or an initialization subroutine for exact LP solving.
Author Information
Wenzhi Gao (Shanghai University of Finance and Economics)
Dongdong Ge (Shanghai University of Finance and Economics)
Chunlin Sun (Stanford University)
Yinyu Ye (Standord)
More from the Same Authors
-
2023 Poster: Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming »
Chunlin Sun · Shang Liu · Xiaocheng Li -
2021 Poster: The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks »
Xiaocheng Li · Chunlin Sun · Yinyu Ye -
2021 Oral: The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks »
Xiaocheng Li · Chunlin Sun · Yinyu Ye -
2017 Poster: Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions »
Yichen Chen · Dongdong Ge · Mengdi Wang · Zizhuo Wang · Yinyu Ye · Hao Yin -
2017 Talk: Strong NP-Hardness for Sparse Optimization with Concave Penalty Functions »
Yichen Chen · Dongdong Ge · Mengdi Wang · Zizhuo Wang · Yinyu Ye · Hao Yin