Gurobi Python API: model.addVars() too slow

Question

I'm currently working on using Gurobi Python API to solve a large-scale LP. I found that the process of adding variables takes too much time, in some cases even more than the optimizing time. My code is roughly like this (I deleted the read data part to make it simpler):

from gurobipy import *
import numpy as np
import time

height = 32
width = 32
size = height * width

# set dummy data
supply = [1.0] * size
demand = [1.0] * size

# compute cost
costs = ((np.arange(size) // height  - 
             np.arange(size).reshape(size,1) // height) ** 2 + \
             (np.arange(size) % width - 
              np.arange(size).reshape(size,1) % width) ** 2).ravel().tolist()

# now build up the model
model = Model("model")
model.Params.Threads = 8

# add variables to model, and record the time spent: too long (around 7.3sec ~ 7.4sec on my computer)
time_1 = time.time()
plan = model.addVars(size, size, name = "plan")
time_2 = time.time()
print(time_2 - time_1)
model.update()

# set objective
obj = LinExpr(costs, model.getVars())
model.setObjective(obj, GRB.MINIMIZE)

# add constraints
model.addConstrs(plan.sum(i, '*') == supply[i] for i in range(size))
model.addConstrs(plan.sum('*', j) == demand[j] for j in range(size))

model.optimize()

I ran this modified code on my laptop, and I found out that with these dummy data the process of adding variables takes about 7.3sec ~ 7.4sec, while the solving time is around 6 ~ 7 seconds. So the model.addVars() function is too slow. Is there anyway to improve this? I tried the following (of course with this change I have to modify other part of my code too):

plan = model.addVars(size * size, name = "plan")

Adding variables to the model is a little faster now, but still not acceptable when compared with the solving time.

Frizzly

This only happens for very easy LPs. Most real models do not fall in this category. If you are really worried about this, you can create the whole matrix yourself in a high-performance language like C. I would not be really upset that generating a million variables takes a few seconds. – Jessy

@ErwinKalvelagen Thanks for reply. But I don't think what you said is true. When I change height and width from 32 to 64, the number of variables is 4096*4096=16777216>millions of variables. I then ran the code on a linux server (my PC no longer have enough memory for this), the adding variables cost around 120sec while the solving cost around 250sec. I think the time cost of adding variables can not be ignored. – Frizzly

This is still a very easy LP (an assignment problem). These models solve very quickly. Most models are not that easy. – Jessy

Answer 1

I came across the same problem today and found two partial solutions.

First off, to address the comments - I agree that the only thing that makes the slowness of constructing this problem problematic is that it's so simple to solve; as a result, the solving happens very quickly and the slowness of constructing it really becomes a problem.

However, I disagree this makes the problem irrelevant. There are a lot of applications in which what is needed is the solution of thousands of very easy problems sequentially, rather than the solution of one huge problem. In those situations, the time it takes to construct the problem is a real issue.

There are two possible solutions I found to the scenario above - both involve first building a "generic" version of the problem, and then "editing it" every time the problem needs to be solved. The "model editing" process is much faster than the model construction process, thus alleviating the issue above. The two methods are as follows

• Write the model to a MPS file using the write function. Every time you need to solve the program, edit the MPS file directly to customize the program, read the MPS file in and solve it. In my benchmarks, this was roughly 4 times faster than constructing the model from scratch.

• Construct the model normally and keep it in memory. Store the constraint object when you create it. Later, each time the model needs to be solved, use the chgCoeff function to change the relevant coefficient. In my benchmarks, this was roughly 17-18 times faster than constructing the model from scratch.

Of course, the above assumes that the structure of each program to be solved is similar enough that one can be obtained from another by simply changing some coefficients. In not, this wouldn't help, and as far as I can tell, there's no easy solution - though I'd love someone to prove me wrong, it seems surprising Gurobi doesn't include a solution for this kind of problem.

Charily

I’m having the same problem when solving a large number of small LPs. I’m thinking of writing an external module in C and calling that code from Python using the Numpy C API. – Salahi

Note that the new version of Gurobi includes a matrix interface for Python - this might help! – Charily

Do you mean addMConstrs and such? Unfortunately it still seems slower than cvxopt.solvers.lp with GLPK for example. – Salahi

Ugh, the worst. I had such high hopes for that new interface. Apologies for the red herring. – Charily

No worries. I’ll probably just have to go with talking to the C API. – Salahi

Answer 2

This problem solves quickly because you don't actually need the optimizer to solve it. All demand and supply are one, and the diagonal of the cost matrix are only zeros. This makes the solution to be the diagonal of the variable matrix equal to 1.

Sommelier