Gurobi taking too long (?) to set up problem with enormous matrix

Answered

Ming Yin

February 23, 2024 01:07

• 
• 
• 

I'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 real-valued vector. Here is how I currently have this problem set up (in Gurobipy):

Define real-valued vector x with no constraints
Define real-valued 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?

0

• 

  Riley Clement

  • Gurobi Staff

  February 23, 2024 11:58

  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 = -c

  A 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=True

  then the resulting model will be equivalent to min ||Bx + c||_1.

  - Riley

  0
• 

  Ming Yin

  June 18, 2024 21:58

  • 
  • 
  • 

  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
• 

  Riley Clement

  • Gurobi Staff

  June 19, 2024 11:35

  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 non-negative then x = 0 will be the optimal solution.

  - Riley

   

  0

Please sign in to leave a comment.