Improve performance of constraint-adding in Gurobi (Python-Interface)

Question

i got this decision variable:

x={}
for j in range(10):
    for i in range(500000):
        x[i,j] = m.addVar(vtype=GRB.BINARY, name="x%d%d" %(i,j))

so i need to add constraints for each x[i,j] variable like this:

for p in range(10):
    for u in range(500000):
        m.addConstr(x[u,p-1]<=x[u,p])

this is taking me so much time, more that 12hrs and then a lack of memory pop-up appears at my computer. Can someone helpme to improve this constraint addition problem

I'm surprised it doesn't throw an error when you index with p=0 and p-1. — sascha
– sascha, Commented Aug 6, 2016 at 13:35

Greg Glockner · Accepted Answer · 2016-08-07 17:04:45Z

2

Most likely, you are running out of physical memory and using virtual (swap) memory. This would not cause your computer to report an out-of-memory warning or error.

I rewrote your code as follows:

from gurobipy import *

m = Model()

x={}
for j in range(10):
  for i in range(500000):
    x[i,j] = m.addVar(vtype=GRB.BINARY, name="x%d%d" %(i,j))
m.update()

for p in range(10):
  for u in range(500000):
    try:
      m.addConstr(x[u,p-1]<=x[u,p])
    except:
      pass
m.update()

I tested this using Gurobi Optimizer 6.5.2 on a computer with an Intel Xeon E3-1240 processor (3.40 GHz) and 32 GB of physical memory. It was able to formulate the variables and constraints in 1 minute 14 seconds. You might be able to save a small amount of memory using a list, but I believe that Gurobi Var and Constr objects require far more memory than a Python dict or list.

answered Aug 7, 2016 at 17:04

Greg Glockner

5,6732 gold badges23 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jmparejaz Over a year ago

thanks Greg Glockner, now understanding that the problem is because the lack of memory, do you know if Gurobi can be executed with GPU programming?t

sascha Over a year ago

@jmparejaz Gurobi does not support GPU programming yet (and maybe not in the near future). Ignoring a lot of stuff which could be said about the problems being solved with Gurobi and GPU-approaches therefore, just let me tell you, that with GPU-programming, usually memory is just an even bigger problem (especially in Deep-Learning; GPU-memory in general more expensive than main-memory). It's quite cheap to obtain 32GB memory for a workstation, a 32GB GPU will be very expensive (if it exists).

sascha · Accepted Answer · 2016-08-06 13:53:42Z

1

General Remark:

It looks quite costly to add 5 million constraints in general

Specific Remark:

Approach

You are wasting time and space by using dictionaries
- Despite having constant-access complexity, these constants are big
- They are also wasting memory
In a simple 2-dimensional case like this: stick to arrays!

Validity

Your indexing is missing the border-case of the first element, so indexing breaks!

Try this (much more efficient approach; using numpy's arrays):

import numpy as np
from gurobipy import *

N = 10
M = 500000

m = Model("Testmodel")
x = np.empty((N, M), dtype=object)
for i in range(N):
    for j in range(M):
        x[i,j] = m.addVar(vtype=GRB.BINARY, name="x%d%d" %(i,j))
m.update()

for u in range(M):  # i switched the loop-order
    for p in range(1,N):  # i'm handling the border-case
        m.addConstr(x[p-1,u] <= x[p,u])

Result:

~2 minutes
~2.5GB memory (complete program incl. Gurobi's internals)

edited Aug 6, 2016 at 13:53

answered Aug 6, 2016 at 13:42

sascha

33.7k6 gold badges80 silver badges117 bronze badges

4 Comments

jmparejaz Over a year ago

Thanks Sascha I will try this inmediately

Greg Glockner Over a year ago

numpy is not helpful in this case: most of the memory is taken by the Gurobi Var and Constr objects.

sascha Over a year ago

@GregGlockner numpy surely is more memory-efficient as a dictionary (and of course it's faster to index). But of course you are right, that Gurobi's internals will dominate the time/memory taken in this snippet. Out of curiosity: is there some benefit (i don't think it's available within gurobipy yet) in giving constraints in vectorized/matrix-form (instead of one-after-another; e.g. A <= B where A and B are matrices = basic library-design in modelling-tools like cvxpy although it's way different internally reasoning about convex.)? This should help somehow with efficiency internally, or not?

Greg Glockner Over a year ago

@sascha There are no real benefits. In practically every application, the solution algorithms require far more time and memory than the API.

Collectives™ on Stack Overflow

Improve performance of constraint-adding in Gurobi (Python-Interface)

2 Answers 2

2 Comments

General Remark:

Specific Remark:

Approach

Validity

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

General Remark:

Specific Remark:

Approach

Validity

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related