Liyuan Distinguished Scholar twenty-four: Recent Computational Progress on Linear Programming Solvers

Title: Recent Computational Progress on Linear Programming Solvers

Speaker: Prof. Yip Yinyu (Stanford University)

Lecture time: April 17, 2024 (Wednesday) 10:00-11:00

Lecture location: No. 1 Lecture Hall ofFinancial Science and Technology College, Huixing Building, Yuehai Campus, SZU

Overview: We describe some recent algorithmic advances in the development of general-purpose linear and semidefinite programming (LP/SDP) solvers. They include: 1) LP pre-solver based on a fast online LP algorithm; 2) Smart crossover from approximate LP solution to optimal basic solution; 3) ADMM-based methods for LP and SDP and 4) 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.

Speaker Introduction: Professor Ye Yinyu currently holds the prestigious position of a Distinguished Lifetime Professor at Stanford University's Department of Management Science and Engineering and the Institute for Computational and Mathematical Engineering. He earned a Bachelor's degree in Systems Engineering from Huazhong University of Science and Technology, a Master's degree in Engineering Economic Systems from Stanford University, and a Ph.D. in Engineering Economic Systems and Operations Research from the same institution. His research primarily focuses on optimization, complexity theory, algorithm design and analysis, applications of mathematical programming, operations research, and systems engineering. Additionally, Professor Ye is interested in developing optimization software for various practical applications. His current research directions include linear programming algorithms, Markov decision processes, computational game/market equilibrium, metric geometry of distances, dynamic resource allocation, and stochastic and robust decision-making.

Professor Ye is a Fellow of INFORMS (Institute for Operations Research and the Management Sciences) and has received multiple research awards. These include the inaugural Farkas Prize in Optimization in 2006, the IBM Faculty Award in 2009, and the prestigious John von Neumann Theory Prize in the same year, in recognition of his sustained contributions to the theory of operations research and management sciences. In 2012, he became the first recipient of the Tseng Lectureship Award at the International Symposium on Mathematical Programming (ISMP); and in 2014, Professor Ye was awarded the triennial Optimization Prize by the Society for Industrial and Applied Mathematics (SIAM). According to Google Scholar, his publications have been cited more than 52,000 times.

Teachers and students are welcome to participate!

Invited by: School of Mathematical Sciences

School of Mathematical Sciences

April 2, 2024