CODEWITHSUNDEEP
pythonnumpyoptimizationramcvxpy
SMA.D
SMA.D

Reputation: 161

How to reduce used memory for a repetitive optimization constraint in python?

I have a mathematical optimization problem of the following simplified form:

min ∑Pxy
s.t. Pxy≥Pyz, ∀x,y,z
Pxy ∈ {0,1}

This problem has XYZ constraints. I write the following code to perform the optimization. The only way that came to my mind was introducing two new matrices that by multiplication with the vectors Pxy and Pyz repeat the constraints. These matrices have size of (XYZ* YZ) and (XYZ* XY). As the dimensions of the problem increases the size of these matrices will become huge and my RAM cannot handle it. Is it possible to re-write this code in a way that requires less memory for constraints? (Probably less memory usage might lead to faster speed).

The following code used all of the RAM on google colab and crashed! (while the optimization problem is easy and can be solved by hand)

import cvxpy as cp
import numpy as np

np.random.seed(55)
X_max, Y_max, Z_max = 70, 70, 50

P_yz = np.random.choice([0, 1], size=(Y_max, Z_max), p=[9./10, 1./10])
P_yz = P_yz.reshape(-1)

z_repetition = np.zeros((X_max, Y_max, Z_max, X_max, Y_max), dtype=np.int8)
for x in range(X_max):
  for y in range(Y_max):
    for z in range(Z_max):
      z_repetition[x,y,z,x,y] = 1
z_repetition = z_repetition.reshape(X_max * Y_max * Z_max, -1)

x_repetition = np.zeros((X_max, Y_max, Z_max, Y_max, Z_max), dtype=np.int8)
for x in range(X_max):
  for y in range(Y_max):
    for z in range(Z_max):
      x_repetition[x,y,z,y,z] = 1
x_repetition = x_repetition.reshape(X_max * Y_max * Z_max, -1)

P_xy = cp.Variable((X_max * Y_max), boolean=True)
constraints = [] 
constraints.append(z_repetition * P_xy >= np.matmul(x_repetition, P_yz))
problem = cp.Problem(cp.Minimize(cp.sum(P_xy)), constraints) 
objective = problem.solve(verbose=True)
# print(P_xy.value.reshape(X_max,-1))

Upvotes: 0

Views: 476

Answers (1)

SMA.D
SMA.D

Reputation: 161

Thanks to the comment of @sascha I have re-wrote the code using scipy.sparse.coo_matrix and the memory problem has solved.

I post the modified code here:

import cvxpy as cp
import numpy as np
import scipy.sparse as sp

np.random.seed(55)
X_max, Y_max, Z_max = 70, 70, 50

P_yz = np.random.choice([0, 1], size=(Y_max, Z_max), p=[9./10, 1./10])
P_yz = P_yz.reshape(-1)

row = []
col = []
for x in range(X_max):
  for y in range(Y_max):
    for z in range(Z_max):
      ids = np.unravel_index(np.ravel_multi_index((x,y,z,x,y), (X_max, Y_max, Z_max, X_max, Y_max)), (X_max * Y_max * Z_max, X_max * Y_max))
      row.append(ids[0])
      col.append(ids[1])
z_repetition_sparse = sp.coo_matrix((np.ones(len(row)), (row, col)), shape=(X_max * Y_max * Z_max, X_max * Y_max))

row = []
col = []
for x in range(X_max):
  for y in range(Y_max):
    for z in range(Z_max):
      ids = np.unravel_index(np.ravel_multi_index((x,y,z,y,z), (X_max, Y_max, Z_max, Y_max, Z_max)), (X_max * Y_max * Z_max, Y_max * Z_max))
      row.append(ids[0])
      col.append(ids[1])
x_repetition_sparse = sp.coo_matrix((np.ones(len(row)), (row, col)), shape=(X_max * Y_max * Z_max, Y_max * Z_max))

P_xy = cp.Variable((X_max * Y_max), boolean=True)
constraints = [] 
constraints.append(z_repetition_sparse * P_xy >= sp.csr_matrix.dot(x_repetition_sparse, P_yz))
problem = cp.Problem(cp.Minimize(cp.sum(P_xy)), constraints) 
objective = problem.solve(verbose=True)
print(P_xy.value.reshape(X_max,-1))

Upvotes: 1

Related Questions