Search code examples
pythonscipylinear-programmingsolvergurobi

Gurobi-style model construction for Scipy.linprog?

I want to compare Gurobi and Scipy's linear programming tools, such as linprog. Scipy requires to specify problems in a matrix-list-vector-form while Gurobi works like here such that

m = Model()
m.addVar(...) %for variables
m.addConstr(..>) %for constraints
m.update() %for updating the model
m.optimize % for optimizing the model
m.params %for getting parameters
m._vars %for getting variables

in comparison Scipy

Minimize: c^T * x

Subject to: A_ub * x <= b_ub
A_eq * x == b_eq


c : array_like
Coefficients of the linear objective function to be minimized.
A_ub : array_like, optional
2-D array which, when matrix-multiplied by x, gives the values of the upper-bound inequality constraints at x.
b_ub : array_like, optional
1-D array of values representing the upper-bound of each inequality constraint (row) in A_ub.
A_eq : array_like, optional
2-D array which, when matrix-multiplied by x, gives the values of the equality constraints at x.
b_eq : array_like, optional
1-D array of values representing the RHS of each equality constraint (row) in A_eq.
bounds : sequence, optional

My goal is to write the code in only one method and still benchmark the results with both solvers. In order to speed up comparing the solvers:

  1. Does there exist Gurobi-style model construction of LP problems for Scipy?

  2. Does there exist some package to make the two methods interchangeable (I could write scipy-style for Gurobi or in Gurobi-style for Scipy)?

  3. Does scipy provide any other interface to specify linear programming problems?

Solution

  • That sounds like a lot of work to show the obvious:

    • Commercial solvers like Gurobi are much faster and much more robust than non-commercial ones
      • There are also high-quality benchmarks showing this by H. Mittelmann (CLP and GLPK beeing the most popular non-commercial ones)
    • While scipy's linprog is ok, it's much worse than the open-source competition including CBC/CLP, GLPK, lpSolve...
      • Speed and robustness!
      • Also: scipy's linprog really seems unmaintained open issues

    There are some ways you could do that:

    • A) Use linprog's way of problem-definition and convert this to Gurobi-style
      • very easy to convert-matrix form to Gurobi's modelling
    • B) Use cvxpy as modelling-tool, grab the standard-form and write a wrapper for Gurobi (actually: there is one) and linprog (again easy). This would allow a very powerful modelling-language to be used by both
      • Disadvantage: Intransparent transformations according to the problem (e.g. abs(some_vector) might introduce auxiliary variables)
    • C) Write some MPS-reader / or take one from other tools to model you problems within Gurobi, output these and read & solve within linprog
      • Candidate tools: cvxopt's mps-reader (well-hidden in the docs), some GLPK-interface or even some CBC-interface
      • (Maybe hidden transformations)

    No matter what you do, solution-process analysis will be a big part of your code as linprog might fail a lot. It's also not able to handle big sparse models.

    Remarks based on your gurobi-example

    • Your example (TSP) is a MIP, not an LP
    • For MIP, everything said above get's worse (especially performance differences between commerical and open-source)
    • There is no MIP-solver within scipy!