14
$\begingroup$

Gurobipy is a fast solver and can convert a mathematical programming model to its underneath language very fast compared to some open source wrappers (e.g., PuLP, OR-tools, etc.). However, a commercial license is a big issue in some cases.

Is there any way to use a wrapper to convert models as fast as gurobipy, and solve with open source solvers? Alternatively, can we pass the model written with gurobipy to an open source solver?

$\endgroup$
12
$\begingroup$

You can use model.write("mymodel.lp") to generate an LP file (similarly for .mps and other common formats) that you can pass in open source solvers, provided that they can read that respective format.

Since LP files are also human readable it is not too hard to transform a gurobipy model script into a script using only plain Python file operations that generates your LP file.


In order to make the second part of my answer a bit (in hindsight, it got out of hand) more succinct, I just give an example on how to generate an LP file "by hand" instead of using the gurobipy Model.write() method. For a minimal working example, consider the binpacking problem (how cliché). $$ \begin{aligned} \text{minimize } & \sum_{j=0}^{n-1} y_j\\ \text{subject to } & \sum_{i=0}^{n-1} w_i x_{ij} \leq Cy_j & j \in \{0, \ldots, n-1\}\\ & \sum_{j=0}^{n-1} x_{ij} \geq 1 & i \in \{0, \ldots, n-1\}\\ & x_{ij}, y_j \in \{0, 1\} & i, j \in \{0, \ldots, n-1\} \end{aligned} $$ Using gurobipy, your file looks somewhat similar to this:

from gurobipy import *

# params
w = [5, 4, 1, 2, 3] 
C = 6
n = len(w)

model = Model('Binpacking')

x = {}
for i in range(n):
  for j in range(n):
    x[i,j] = model.addVar(vtype=GRB.BINARY, name="x#{}#{}".format(i, j))

y = {}
for j in range(n):
  y[j] = model.addVar(vtype=GRB.BINARY, name="y#{}".format(j))

model.setObjective(quicksum(y[j] for j in range(n)), GRB.MINIMIZE)

for j in range(n):
  model.addConstr(quicksum(w[i] * x[i,j] for i in range(n)) <= C * y[j], name="capacity#{}".format(j))

for i in range(n):
  model.addConstr(quicksum(x[i,j] for j in range(n)) >= 1, name="assignment#{}#{}".format(i, j))

model.write("binpacking.lp")

Using the same program structure (which is meant to be human readable, not necessarily optimal w.r.t. execution time), we can also create a similar file only using write(). It is a bit tedious but given the simple structure of LP files straight-forward:

# params
w = [5, 4, 1, 2, 3] 
C = 6
n = len(w)

model = open("binpacking.lp", 'w')

model.write("Minimize\n")
model.write("bins: ")
for j in range(n):
  model.write("+ y#{} ".format(j))

model.write("\n\nSubject to\n")
for j in range(n):
  model.write("capacity#{}:\n".format(j))
  for i in range(n):
    model.write(" + {} x#{}#{}".format(w[i], i, j))
  model.write(" - {} y#{} <= 0\n".format(C, j))

for i in range(n):
  model.write("assignment#{}:\n".format(i))
  for j in range(n):
    model.write(" + x#{}#{}".format(i, j))
  model.write(" >= 1\n")

model.write("\n\nBounds\n")
model.write("Binaries\n")
for j in range(n):
  for i in range(n):
    model.write(" x#{}#{}\n".format(i, j))
  model.write(" y#{}\n".format(j))

model.write("End\n")
model.close()
$\endgroup$
  • 8
    $\begingroup$ Note that, in some numerically unstable edge cases, going from internal binary representation to text file (LP, MPS, ...) and then back to binary at the other end can introduce problems, due to the rounding/truncation in moving from binary to text. I think most models will survive the process pretty well. $\endgroup$ – prubin Sep 11 at 17:59
  • 2
    $\begingroup$ You cannot instantiate a model with gurobipy unless you have a valid license, so this answer is probably not applicable in the case when no license is available. (just tried it - you get an error if you execute m = grb.Model("somemodel")) $\endgroup$ – JakobS Sep 13 at 10:19
  • 1
    $\begingroup$ @prubin If you want to have a look at the model you can use LP - If you want to preserve precision, you should always use the MPS file format as it uses a higher precision compared to the LP file format. $\endgroup$ – JakobS Sep 13 at 10:21
  • $\begingroup$ @JakobS In the question is asked how to pass a model written by gurobipy to another solver. If this is already an issue one can build the LP file him/herself by just replacing addConstr and similar gurobipy commands by Python write operations which is also (very briefly) mentioned in the answer. $\endgroup$ – ttnick Sep 13 at 10:50
  • $\begingroup$ @JakobS: MPS is still an ASCII format, so there is still precision loss going to and from it. From the Wikipedia entry (en.wikipedia.org/wiki/MPS_(format)): "Numeric fields have 12 characters width therefore limiting the precision." $\endgroup$ – prubin Sep 14 at 15:50
8
$\begingroup$

If you do a lot of looping in Python to build your model, then model building is going to be slow. We have illustrated this for Pyomo (and the same undoubtedly holds for Pulp) in a notebook that implements the socalled Wasserstein model. Note this shows Mosek Fusion and Cvxpy is much faster than Pyomo for this particular model.

We tried to use the fast expressions in Pyomo but it made no difference.

The key to the speed of MOSEK Fusion (and Cvxpy) is that it employs a vectorized notation which allows Fusion to move a lot of the model generation and input from Python to C based code.

Btw we are currently implementing the model using Julia JuMP. It is slower than both Mosek Fusion and Cvxpy. We are quite surprised by that and do not konw yet why.

$\endgroup$
  • $\begingroup$ Nice. Do you work around Python loops with similar tricks as Gurobi's quicksum? $\endgroup$ – Robert Schwarz Sep 13 at 9:49
  • 1
    $\begingroup$ See my expanded answer and the notebook referenced. I do not know the quicksum you reference. $\endgroup$ – ErlingMOSEK Sep 13 at 11:25
  • $\begingroup$ Thanks. See quicksum. I think it avoids building up all of the intermediate results of adding one term to the partial sum so far. $\endgroup$ – Robert Schwarz Sep 13 at 12:08
  • $\begingroup$ I'm also curious about JuMP being slower than your Python example. I think the original benchmarks in the paper only covered MIP problems, but you probably have some cone problems to express? $\endgroup$ – Robert Schwarz Sep 13 at 12:08
  • 1
    $\begingroup$ The Julia JuMP notebook will be published soon. It is the same problem as in the Python notebook. $\endgroup$ – ErlingMOSEK Sep 13 at 12:35
6
$\begingroup$

So I experimented somewhat with the formulation generation in pulp and profiled it. The biggest time sink hole was string creation.

This can be resolved by using f strings in Python 3.6+

This lead to a more than 2X speed up for formulating models.

$\endgroup$
2
$\begingroup$

Do you need a Python library in particular? If you are happy using Julia, you should give JuMP a try. It will give you high-level modeling with fast model generation and connection to most solvers.

$\endgroup$
  • 1
    $\begingroup$ Jump can be slower than the best Python APIs. See my reply above. We will soon release a notebook showing that. $\endgroup$ – ErlingMOSEK Sep 13 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.