We propose two simple polynomial-time algorithms to find a positive solution to Ax = 0. Both algorithms iterate between coordinate descent steps similar to von Neumann’s algorithm, and rescaling steps. In both cases, either the updating step leads to a substantial decrease in the norm, or we can infer that the condition measure is small and rescale in order to improve the geometry. We also show how the algorithms can be extended to find a solution of maximum support for the system Ax =0, x ≥ 0. This is an extended abstract. The missing proofs will be provided in the full version
Additional Metadata
THEME Logistics (theme 3)
Publisher Springer
Editor Q. Louveaux , M. Skutella
Persistent URL dx.doi.org/10.1007/978-3-319-33461-5_3
Series Lecture Notes in Computational Science and Engineering
Conference International Conference on Integer Programming and Combinatorial Optimization
Citation
Dadush, D.N, Végh, L.A, & Zambelli, G. (2016). Rescaled coordinate descent methods for linear programming. In Q Louveaux & M Skutella (Eds.), Proceedings of International Conference on Integer Programming and Combinatorial Optimization 2016 (IPCO 18) (pp. 26–37). Springer. doi:10.1007/978-3-319-33461-5_3