A Parallelizable Acceleration Framework for Packing Linear Programs

Authors

  • Palma London California Institute of Technology
  • Shai Vardi California Institute of Technology
  • Adam Wierman California Institute of Technology
  • Hanling Yi The Chinese University of Hong Kong

Keywords:

optimization, linear programs, parallel algorithms

Abstract

This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is small compared to the variable dimension n. The framework can be used as a black box to speed up linear programming solvers dramatically, by two orders of magnitude in our experiments. We present worst-case guarantees on the quality of the solution and the speedup provided by the algorithm, showing that the framework provides an approximately optimal solution while running the original solver on a much smaller problem. The framework can be used to accelerate exact solvers, approximate solvers, and parallel/distributed solvers. Further, it can be used for both linear programs and integer linear programs.

Downloads

Published

2018-04-29

How to Cite

London, P., Vardi, S., Wierman, A., & Yi, H. (2018). A Parallelizable Acceleration Framework for Packing Linear Programs. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11778