Skip to main content

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

Answered

Comments

3 comments

  • Riley Clement
    Gurobi Staff Gurobi Staff

    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
    First Comment
    First Question

    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 Gurobi Staff

    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.