  Linear Programs (LPs) appear in a large number of applications and offloading
them to the GPU is viable to gain performance. Existing work on offloading and
solving an LP on GPU suggests that performance is gained from large sized LPs
(typically 500 constraints, 500 variables and above). In order to gain
performance from GPU for applications involving small to medium sized LPs, we
propose batched solving of a large number of LPs in parallel. In this paper, we
present the design and CUDA implementation of our batched LP solver library,
keeping memory coalescent access, reduced CPU-GPU memory transfer latency and
load balancing as the goals. The performance of the batched LP solver is
compared against sequential solving in the CPU using an open source solver GLPK
(GNU Linear Programming Kit). The performance is evaluated for three types of
LPs. The first type is the initial basic solution as feasible, the second type
is the initial basic solution as infeasible and the third type is the feasible
region as a Hyperbox. For the first type, we show a maximum speedup of
$18.3\times$ when running a batch of $50k$ LPs of size $100$ ($100$ variables,
$100$ constraints). For the second type, a maximum speedup of $12\times$ is
obtained with a batch of $10k$ LPs of size $200$. For the third type, we show a
significant speedup of $63\times$ in solving a batch of nearly $4$ million LPs
of size 5 and $34\times$ in solving 6 million LPs of size $28$. In addition, we
show that the open source library for solving linear programs-GLPK, can be
easily extended to solve many LPs in parallel with multi-threading. The thread
parallel GLPK implementation runs $9.6\times$ faster in solving a batch of
$1e5$ LPs of size $100$, on a $12$-core Intel Xeon processor. We demonstrate
the application of our batched LP solver in the domain of state-space
exploration of mathematical models of control systems design.
