CODEWITHSUNDEEP
pythonconstraintslinear-programminggurobi
jmparejaz
jmparejaz

Reputation: 162

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

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

Upvotes: 0

Views: 2196

Answers (2)

Greg Glockner
Greg Glockner

Reputation: 5653

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.

Upvotes: 2

sascha
sascha

Reputation: 33542

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)

Upvotes: 1

Related Questions