using numpy with gurobi to generate LinExpr

[Renato Negrinho]

Hi,

I'm using the Python bindings to Gurobi. I was wondering if using numpy array to generate LinExpr or QuadExpr is a good idea, i.e., if it efficient when compared to other alternatives.

What I do is to generate the variables for the model and store them in a python list; then I convert that python list to a numpy array and reshape it to suit my needs, yielding a matrix with the model's variables; finally, the LinExpr or QuadExpr are generated by means of numpy dot products with this matrix of variables.

I'm currently using this method for generating the constraints and objective for the problem that I'm solving and I'm surprised to verify that it takes longer to generate the variables and the constraints than to solve the problem.

Can you provide any insight about this?

Thanks for all the help,
Renato

[Jakob Sch.]

Hi Renato,

Can you post some example code? Usually gurobi and numpy do not work together flawlessl, but there may be another mistake in your code.

Best regards,
Jakob

[Ed Rothberg]

Usually gurobi and numpy do not work together flawlessly...

We improved our numpy support quite a bit in 5.6.2.  I wouldn't claim 'flawless', but they should work quite well together now.

Ed

[Jakob Sch.]

Hi Ed,

Of course you are right. You did a good job and in the newer versions much has been done to achieve a better interaction with numpy which is a huge improvement especially for the scientific community. Since I'm not sure which version is used by Renato, I tend to be careful. An example of the code would help to shed some light on the problem.

Best regards,
Jakob

[Renato Negrinho]

Hi,

Sorry for the delay. I forgot to subscribe to the thread.

I'm using Gurobi version 5.6.1.

Here is some sample code. There is probably a better way to do this.
This takes 50sec on my computer.

Thanks
Renato

Code starts below:
---------

import numpy as np
import gurobipy as grb

# Create the variables corresponding to a doubly stochastic matrix, i.e
# entries are nonnegative and the entries on each row and column sum to one.
# This is sample code akin to what I'm doing.

dim = 1000

grb_model = grb.Model()

M = [grb_model.addVar(lb=0.0, ub=1.0, name="m" + str(v)) for v in xrange(dim * dim)]
M = np.array(M).reshape((dim, dim)).T
           
grb_model.update()
       
ones_v = np.ones((dim, 1), dtype=np.float)

row_constr = M.dot(ones_v)
col_constr = M.T.dot(ones_v)
               
for c in row_constr.ravel():
    grb_model.addConstr(c, grb.GRB.LESS_EQUAL, 1.0)

for c in col_constr.ravel():
    grb_model.addConstr(c, grb.GRB.LESS_EQUAL, 1.0)

grb_model.update()

[Ed Rothberg]

row_constr = M.dot(ones_v)
col_constr = M.T.dot(ones_v)

My guess is that you are running into the same issue we ran into with sum() - it is fine when you are doing a reduction, but its runtime is quadratic when building an expression.  You can read about performance issues for linear expressions here...

http://www.gurobi.com/documentation/5.6/reference-manual/py_linexpr

Can you try using quicksum() instead?

Ed

 

[Renato Negrinho]

Thanks for the help.

I've used quicksum and the LinExpr and both of them yield much better performance than the dot solution. Now I'm generating the LHS of the constraints directly through the LinExpr constructor.

A thing that I've noticed while I was experimenting was that

M = np.array(M).reshape((dim, dim)).T

is a lot (orders of magnitude) slower than

M = np.array(M, dtype='object').reshape((dim, dim)).T
.

Thanks,
Renato