Skip to yearly menu bar Skip to main content


Solving Linear Programs with Fast Online Learning Algorithms

Wenzhi Gao · Dongdong Ge · Chunlin Sun · Yinyu Ye

Exhibit Hall 1 #606
[ ]
[ Slides [ PDF [ Poster

Abstract: 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.

Chat is not available.