A Parallelizable Acceleration Framework for Packing Linear Programs
Authors: Palma London, Shai Vardi, Adam Wierman, Hanling Yi
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The framework can be used as a black box to speed up linear programming solvers dramatically, by two orders of magnitude in our experiments. The results reported in this paper demonstrate this by accelerating the state-of-the-art commercial solver Gurobi on a wide array of randomly generated packing LPs and obtaining solutions with < 4% relative error and a more than 150 speedup. |
| Researcher Affiliation | Academia | Palma London California Institute of Technology plondon@caltech.edu Shai Vardi California Institute of Technology svardi@caltech.edu Adam Wierman California Institute of Technology adamw@caltech.edu Hanling Yi The Chinese University of Hong Kong yh014@ie.cuhk.edu.hk |
| Pseudocode | Yes | Algorithm 1: Core acceleration algorithm |
| Open Source Code | No | The paper does not contain an explicit statement about releasing source code for the methodology or a link to a code repository. It refers to 'London et al. 2017b' which is an arXiv link to the paper itself, not a code repository. |
| Open Datasets | No | The paper describes experiments run on 'randomly generated LPs'. It details the process of generating the matrix A, and vectors c and b, including dimensions and distributions. However, it does not use a publicly available, established dataset or provide access information for the generated data, such as a link, DOI, or formal citation. |
| Dataset Splits | No | The paper describes the generation of random LPs for experiments but does not provide specific details on training, validation, or test dataset splits (e.g., percentages, sample counts, or references to predefined splits). |
| Hardware Specification | Yes | The experiments are run on a server with Intel E5-2623V3@3.0GHz 8 cores and 64GB RAM. To emphasize the improvement in scalability, we run an experiment on a laptop with Intel Core i5 CPU and 8 GB RAM. |
| Software Dependencies | No | The paper states, 'We implement the accelerator in Matlab and use it to accelerate Gurobi.' While it names the software, it does not provide specific version numbers for either Matlab or Gurobi, which are required for reproducible ancillary software details. |
| Experiment Setup | Yes | Unless otherwise specified, the experiments use a matrix A Rm n of size m = 102, n = 106. Each element of A, denoted as aij, is first generated from [0, 1] uniformly at random and then set to zero with probability 1 p. Hence, p controls the sparsity of matrix A, and we vary p in the experiments. The vector c Rn is drawn i.i.d. from [1, 100] uniformly. Each element of the vector b Rm is fixed as 0.1n. By default, the parameters of the accelerator are set as ϵs = 0.01 and ϵf = 0, though these are varied in some experiments. |