An implementation of steepest-descent augmentation for linear programs

DOI10.1016/J.ORL.2020.04.004MaRDI QIDQ6329523arXivFDO

Authors Steffen Borgwardt, Charles Viss

Publication date 19 November 2019

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.ORL.2020.04.004

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

arXiv classification

math.OC

Abstract: Generalizing the simplex method, circuit augmentation schemes for linear programs follow circuit directions through the interior of the underlying polyhedron. Steepest-descent augmentation is especially promising, but an implementation of the iterative scheme is a significant challenge. We work towards a viable implementation through a model in which a single linear program is updated dynamically to remain in memory throughout. Computational experiments exhibit dramatic improvements over a naive approach and reveal insight into the next steps required for large-scale computations.

This page was built for publication: An implementation of steepest-descent augmentation for linear programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329523)