TY - JOUR
AU - London, Palma
AU - Vardi, Shai
AU - Wierman, Adam
AU - Yi, Hanling
PY - 2018/04/29
Y2 - 2023/03/20
TI - A Parallelizable Acceleration Framework for Packing Linear Programs
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 32
IS - 1
SE - AAAI Technical Track: Machine Learning
DO - 10.1609/aaai.v32i1.11778
UR - https://ojs.aaai.org/index.php/AAAI/article/view/11778
SP -
AB - <p> 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. </p>
ER -