Department of Industrial Engineering & Decision Analytics [Joint IE/OM seminar] - Recent Computational Progress on Linear Programming Solvers
We describe some recent algorithmic advances in the development of general-purpose linear and semidefinite programming (LP/SDP) solvers. They include
- LP pre-solver based on a fast online LP algorithm
- Smart crossover from approximate LP solution to optimal basic solution
- ADMM-based methods for LP and SDP
- First-order method PDHG using GPU architecture
Most of these techniques have been implemented in the emerging optimization numerical solver COPT, and they increased the average solution speed by over 3x in the past three years on a set of benchmark LP/SDP problems. For certain problem types, the speedup is more than 50x, and problems that have taken days to solve or never been solved before are now solved in minutes to high accuracy.
Yinyu Ye is currently the K.T. Li Professor of Engineering at Department of Management Science and Engineering and Institute of Computational and Mathematical Engineering, Stanford University. His current research topics include Continuous and Discrete Optimization, Data Science and Applications, Numerical Algorithm Design and Analyses, Algorithmic Game/Market Equilibrium。Operations Research and Management Science etc.; and he was one of the pioneers of Interior-Point Methods, Conic Linear Programming, Distributionally Robust Optimization, Online Linear Programming and Learning, Algorithm Analyses for Reinforcement Learning and Markov Decision Process, and etc. He has received several scientific awards including, including the 2009 John von Neumann Theory Prize for fundamental sustained contributions to theory in Operations Research and the Management Sciences, the inaugural 2012 ISMP Tseng Lectureship Prize for outstanding contribution to continuous optimization (every three years), the 2014 SIAM Optimization Prize awarded (every three years), etc.. According to Google Scholar, his publications have been cited 58,000 times.