如何减少 python 中重复优化约束的已用内存？

Question

我有以下简化形式的数学优化问题：

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

这个问题有 XYZ 个约束条件。我编写了以下代码来执行优化。我想到的唯一方法是引入两个新矩阵，通过与向量 Pxy 和 Pyz 相乘来重复约束。这些矩阵的大小为 (XYZ* YZ) 和 (XYZ* XY)。随着问题维度的增加，这些矩阵的大小将变得巨大，我的 RAM 无法处理它。是否有可能以需要更少内存的方式重写此代码？（可能较少的内存使用量可能会导致更快的速度）。

以下代码使用了 google colab 上的所有 RAM 并崩溃了！（而优化问题很简单，可以手工解决）

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))

Answer 1

感谢@sascha 的评论，我 re-wrote 使用 scipy.sparse.coo_matrix 的代码，内存问题已解决。

我post这里修改代码：

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))

如何减少 python 中重复优化约束的已用内存？

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

python

optimization

ram

numpy

cvxpy