A Parallelizable Acceleration Framework for Packing Linear Programs
- Creators
- London, Palma
- Vardi, Shai
- Wierman, Adam
- Yi, Hanling
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.
Additional Information
© 2018 Association for the Advancement of Artificial Intelligence. PL, SV, and AW were supported in part by NSF grants AitF-1637598, CNS-1518941, CPS-154471 and the Linde Institute. HY was supported by the International Teochew Doctors Association Zheng Hanming Visiting Scholar Award Scheme.Attached Files
Submitted - 1711.06656.pdf
Files
Name | Size | Download all |
---|---|---|
md5:e0c64db9b41340d5635c6e74cd7b0fc1
|
221.3 kB | Preview Download |
Additional details
- Eprint ID
- 90570
- Resolver ID
- CaltechAUTHORS:20181101-121244788
- CCF-1637598
- NSF
- CNS-1518941
- NSF
- CPS-154471
- NSF
- Linde Institute of Economic and Management Science
- International Teochew Doctors Association
- Created
-
2018-11-01Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field