在 cvxpy 中指定约束时违反了 DCP 要求，可能需要重新考虑问题的整个表述

Question

这是较早前的后续，但随着我为问题的表述增加更多的复杂性，我意识到我需要退后一步，考虑一下 cvxpy 是否是最好的工具我的问题。

我要解决的问题：创建平均值高于特定阈值的类别和公司的最大集群。诀窍在于，如果我们在集群中包含一家公司的特定类别，为了添加另一家公司，那家公司也应该对相同的类别具有高价值。

我将其表述为一个整数线性优化问题，其中我展开了所有变量。主要有两个问题：

约束 8 违反了 DCP 规则。约束 8 旨在使集群中包含的值保持在特定阈值之上。我通过取非零变量的平均值来检查这一点。
实际问题需要指定数千个变量和约束（有 100 个类别和 >10K 个公司）。这让我怀疑这是否是正确的方法。

import numpy as np
import cvxpy as cp
import cvxopt 

util = np.array([0.7, 0.95, 0.3, 2, 1.05, 2.2, 4, 1, 3])

# The variable we are solving for
dec_vars = cp.Variable(len(util), boolean = True)

tot_util = util @ dec_vars

is_zero_bucket1= cp.Variable(1, boolean = True)
is_zero_bucket2= cp.Variable(1, boolean = True)
is_zero_bucket3= cp.Variable(1, boolean = True)

is_zero_cat1 = cp.Variable(1, boolean=True)
is_zero_cat2 = cp.Variable(1, boolean=True)
is_zero_cat3 = cp.Variable(1, boolean=True)

# at least 2 categories should be included for a given company
constr1 = sum(dec_vars[0:3]) >= 2 * is_zero_bucket1
constr2 = sum(dec_vars[3:6]) >= 2 * is_zero_bucket2
constr3 = sum(dec_vars[6:9]) >= 2 * is_zero_bucket3

# at least 2 columns (companies) for a given category that's selected
constr4 = dec_vars[0] + dec_vars[3] + dec_vars[6] >= 2 * is_zero_cat1
constr5 = dec_vars[1] + dec_vars[4] + dec_vars[7] >= 2 * is_zero_cat2
constr6 = dec_vars[2] + dec_vars[5] + dec_vars[8] >= 2 * is_zero_cat3

constr7 = np.ones(len(util)) @ dec_vars >= 2

constr8 = (tot_util/cp.sum(dec_vars)) >= 1.3

cluster_problem = cp.Problem(cp.Maximize(tot_util), [constr1, constr2, constr3, constr4, constr5, constr6, constr8])

cluster_problem.solve()

更新

我按照建议修改了。现在的问题是决策变量矩阵本身没有包含相邻公司/类别的规则。为此，我可以使 objective 函数成为最终决策变量矩阵与 zero_comp_vars 和 zero_cat_vars 向量的乘积。但是，当我这样做时出现 Problem does not follow DCP rules 错误。一定是因为将 2 个矩阵乘以两个向量。另外，我想知道是否有一种方法可以让程序在决策矩阵中适当位置的变量不满足至少 2 家公司和 3 个类别为非零的标准时将其归零，以便被包括在内。就目前而言，决策变量矩阵将有 rows/columns 的 1，实际上由 zero_comp_vars 和 zero_cat_vars 变量

归零

util = np.array([[0.7, 0.95, 0.3], [2, 1.05, 2.2], [4, 1, 3]])

# The variable we are solving for
dec_vars = cp.Variable(util.shape, boolean = True)

zero_comp_vars = cp.Variable(util.shape[0], boolean = True)
zero_cat_vars = cp.Variable(util.shape[1], boolean = True)

# define constraints
zero_comp_constr = cp.sum(dec_vars, axis=1) >= 2 * zero_comp_vars
zero_cat_constr = cp.sum(dec_vars, axis=0) >= 3 * zero_cat_vars
# need the following two constraints, otherwise all the values in the zero_comp_constr and zero_cat_constr vectors can be 0
above_one_non_zero_comp = cp.sum(zero_comp_vars) >= 1
above_one_non_zero_cat = cp.sum(zero_cat_vars) >= 1

# min tin array
min_comp_array=np.empty(dec_vars.shape[0])
min_comp_array.fill(2)

min_comp_constr = cp.sum(dec_vars, axis=1) >= min_comp_array
tot_avg_constr = tot_util >= 2.0 * cp.sum(dec_vars)

# this is the section that gives error
temp = cp.multiply(util, dec_vars)
temp2 = cp.multiply(temp, cp.reshape(zero_comp_vars, (3,1)))
temp3 = cp.multiply(temp2, cp.reshape(zero_cat_vars, (3,1)))

tot_util = cp.sum(temp3)
#tot_util = cp.sum(cp.multiply(util, dec_vars))

cluster_problem = cp.Problem(cp.Maximize(tot_util), [zero_comp_constr, zero_cat_constr, 
                                                     above_one_non_zero_comp, above_one_non_zero_cat,
                                                     min_comp_constr, tot_avg_constr])

cluster_problem.solve()

Answer 1

改造一下：

constr8 = (tot_util/cp.sum(dec_vars)) >= 1.3

->

constr8 = tot_util >= 1.3 * cp.sum(dec_vars)

您可能需要强制 cp.sum(dec_vars) 为正数，否则：0 >= 0 是有效解。

另请参阅：lpsolve docs: Ratios

旁注

是的，您的目标是使用通用优化工具的机器学习规模数据，这将很快达到极限，即使对于纯连续的情况也是如此。在您的情况下，使用离散优化，您可能会运行陷入可伸缩性问题（听起来像 1M 二进制变量），尤其是在仅限于开源求解器时。

在 cvxpy 中指定约束时违反了 DCP 要求，可能需要重新考虑问题的整个表述

DCP requirement violated when specifying constraing in cvxpy, perhaps need to rethink entire formulation of problem

python

optimization

integer-programming

cvxpy

更新

旁注