Search code examples
pythonlinear-programmingcupy

Linear programming with cupy

I am trying to improve codes efficiency with cupy. But I find no ways to carry linear programming within cupy. This problem comes from the following parts:

N = hull_points.shape[0]
c = ones(N)
A_eq = concatenate((hull_points, ones((N, 1))),
                   1).T   # rows are x, y, z, 1
b_eq = concatenate((pnt, (1,)))
result = linprog(c, A_eq=A_eq, b_eq=b_eq)

Is there something I can use directly? Or the only way out is to implement a linear programming package based on cupy?

Solution

  • I’ve seen papers that propose to use GPU for linear programming. Some of them even reported outstanding improvement. But from what I saw, they compare their GPU implementation of the simplex method with their sequential implementation, not with Gurobi, Cplex, or even CLP. And I never heard about an efficient GPU-base LP solver that beats good LP solvers. Such flagman like Gurobi does not support GPU. And I know there are some doubts that GPU actually can help in large-scale LP.

    • Large-scale LPs are sparse, and GPU is not good for sparse.
    • Optimization in general is mostly a sequential process (paralleling in modern LP solvers is very specific and cannot utilize GPU).

    If you want to try to implement your own GPU-base LP solver, I encourage you to try. Whatever you get it would be a great experience.

    But if you only need to speed up your solution process then get a different solver. Linprog from SciPy may be a good choice to prototype. But GLPK or CLP/CBC will give you much better speed. You can invoke them through Pyomo or PULP.