Recent Computational Progresson Linear Programming Solvers

Abstract:

We describe some recent algorithmic advances in the development ofgeneral-purpose linear and semidefinite programming (LP/SDP) solvers. Theyinclude:

.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 emergingoptimization numerical solver COPT, and they increased the average solutionspeed by over 3x in the past three years on a set of benchmark LP/SDPproblems. For certain problem types, the speedup is more than 50x, andproblems that have taken days to solve or never been solved before are nowsolved in minutes to high accuracy.

Speaker:

Yinyu Ye is currently the K.T. Li Professor of Engineering at Department ofManagement Science and Engineering and Institute of Computational andMathematical Engineering, Stanford University. His current research topicsinclude Continuous and Discrete Optimization, Data Science and Applications,Numerical Algorithm Design and Analyses, Algorithmic Game/Market Equilibrium,Operations Research and Management Science, etc. He was one of thepioneers of Interior-Point Methods, Conic Linear Programming, DistributionallyRobust Optimization, Online Linear Programming and Learning, AlgorithmAnalyses for Reinforcement Leaming and Markov Decision Process, etc. He hasreceived several scientific awards including the 2009 John von Neumann TheoryPrize for fundamental sustained contributions to theory in Operations Researchand the Management Sciences, the inaugural 2012 ISMP Tseng LectureshipPrize for outstanding contribution to continuous optimization (every three years),the 2014 SlAM Optimization Prize (every three years), etc. According to GoogleScholar, his publications have been cited 58,000 times.