Search code examples
pythonlinear-programmingcvxpy

CVXPY: Efficiently writing constraints for pairwise sums

I'm trying to implement this LP in CVXPY:

LP

but am struggling to find an efficient way to implement the first constraint here. The only way I've found that works is to add each sum as its own constraint, but that quickly explodes in size as the size of the problem gets bigger. Is there an easier/more efficient way to specify this constraint?

import cvxpy as cp
import numpy as np

n_j = 10
n_i = 100

a = cp.Variable(n_j, nonneg=True)
b = cp.Variable(n_i, nonneg=True)

g = np.random.randint(low=1, high=10, size=n_j)
v = np.random.normal(size=(n_i, n_j))

obj = cp.Minimize(cp.sum(cp.multiply(g, a)) + cp.sum(b))

constraints = [a[j] + b[i] >= values[i, j] 
               for j in range(n_j) for i in range(n_i)]

prob = cp.Problem(obj, constraints)
prob.solve()
Solution

  • We can translate this into matrix notation:

    enter image description here

    where e are column vectors of all ones. Of course the e vectors should have the appropriate size: each term should be an (n_i x n_j) matrix.

    In CVXPY this can be written as:

    # changed into using explicit column vectors
a = cp.Variable((n_j,1), nonneg=True)
b = cp.Variable((n_i,1), nonneg=True)
g = np.random.randint(low=1, high=10, size=(n_j,1))

# column vectors of ones
e_i = np.ones((n_i,1))
e_j = np.ones((n_j,1))

# matrix style inequality
constraints = [e_i * a.T + b * e_j.T >= v]