Gurobi taking too long (?) to set up problem with enormous matrix
AnsweredI'm a beginner Gurobi user, so apologies if there is a trivial solution that I'm not aware of.
I have a giant real constant matrix B, with dimensions on the order of 10^11 by 10^11 but which is very sparse. I am trying to minimize f(x) = Bx + c_1, where c is a constant vector and x is a realvalued vector. Here is how I currently have this problem set up (in Gurobipy):
Define realvalued vector x with no constraints
Define realvalued vector N with constraints
(c + B @ x) * (c + B @ x) <= N * N
0 <= N
Minimize the objective function ones @ N, where ones is a vector of 1's (i.e. minimize the sum of the components of N).
When I try to run my Python script, it seems that it never makes it past the setup step. I added print statements after key lines of code, and they show that the variable x is set up correctly. However, due to the computing cluster that I'm running it on, it's unclear to me whether it gets stuck trying to set up N and the constraints, or whether the problem is somewhere else. The file for the giant matrix B is about 7 GB, but it seems to load fine into the program.
Anyone have any ideas what the problem could be?

Hi Ming,
Your code doesn't seem consistent with the definition of  . _1.
I think the fastest way of creating the model you want is to first define this "auxiliary model":
min 0
s.t.
Bx = cA feasible solution to this model would be one where Bx + c_1 = 0, and in general won't exist. But if you then use the feasRelaxS method, with
relaxobjtype=0
minrelax=False
vrelax=False
crelax=Truethen the resulting model will be equivalent to min Bx + c_1.
 Riley
0 
Hi Riley,
Sorry for the late reply! I have just tried your suggestion, and while the program does now run, it doesn't seem to be finding the optimal solution  perhaps a local minimum of some sort? For example, it seems to find x = 0 as an optimal solution most of the time.
Best wishes
0 
Hi Ming,
See the following example and check whether you're implementation is the same.
import numpy as np
# make some data
B = np.random.random(size=(10,10))0.5
c = np.random.random(size=10)
# model from scratch
import gurobipy as gp
m = gp.Model()
x = m.addMVar(10)
z = m.addMVar(10)
m.addConstr(z == B@x + c)
y = m.addVar()
m.addGenConstrNorm(y, z.tolist(),1)
m.setObjective(y)
m.optimize()
# model using feasRelaxS
m = gp.Model()
x = m.addMVar(10)
m.addConstr(B@x + c == 0)
m.feasRelaxS(relaxobjtype=0, minrelax=False, vrelax=False, crelax=True)
m.optimize()Do your x variables have a lower bound of 0? This is the default in Gurobi. If your x variables have a lower bound of 0 and your B matrix is nonnegative then x = 0 will be the optimal solution.
 Riley
0
Please sign in to leave a comment.
Comments
3 comments