Solving Linear Programs with very Tall Constraint Matrices

Abstract

Given an LP with tall and skinny constraint matrix, we exploit this property and study an algorithm invented by Clarkson [8]. Although this algorithm has been around for over 30 years, there were no software or implementation that could be found online, nor there be any benchmarks for these special tall and skinny LP s. We describe some variants and changes to the algorithm aiming for practical performances to close this gap. We also study a first order algorithm (based on the Primal-Dual Hybrid Gradient al- gorithm) aimed for large scale LP s proposed by a group of researchers from Google [2], [3] called PDLP. And compare it with Clarkson’s algorithm.