Timezone: »

Solving Linear Programs with Fast Online Learning Algorithms
Wenzhi Gao · Dongdong Ge · Chunlin Sun · Yinyu Ye

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #606
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