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

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 13, 2026 01:29

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  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

Post is closed for comments.