用ECOS_BB慢解，CBC错误“约束不够”

Question

我有一个二进制MIP优化问题，其中我想选择最好的候选人，给出一个预算和一些其他属性的限制。对于每个候选人，我都有一个样本向量，说明他们可能的效用是从单独的贝叶斯分析中得到的。候选人之间是相互关联的。所以，我不想仅仅根据他们的平均效用来选择最好的候选人，我想对那些过于相关的候选对进行负向加权。有点类似于金融中的均值-方差优化投资组合。

下面是带有玩具示例数据的代码

import numpy as np
import pandas as pd
import cvxpy as cvx

N = 256
N_SAMPLES = 2**10
N_AGENCIES = 16

static_data = {'style':np.random.randint(4, size=N), 'agency':np.random.randint(N_AGENCIES, size=N), 'hourly_rate':np.random.normal(160, 32, size=N).astype(np.int)}
df = pd.DataFrame(static_data)
#df.head()

S = np.random.randn(N,N)
cov = S.dot(S.T)
cov = np.divide(np.divide(cov, np.sqrt(np.diag(cov).reshape(-1,1))), np.sqrt(np.diag(cov).reshape(1,-1)))
mu = static_data['hourly_rate']
mu = (mu - mu.mean())/mu.std()
samples = np.random.multivariate_normal(mu, cov, size=N_SAMPLES)
#samples.shape


HOURLY_BUDGET = 1000
REQUIRED_STYLES = np.array([3, 2, 1, 4])
MAX_PER_AGENCY = 2
M_AGENCIES = np.eye(N_AGENCIES)[df['agency']].astype(np.int)
M_STYLES = np.eye(4)[df['style']].astype(np.int)

### Optimization in cvxPy
selection = cvx.Variable(N, boolean=True)
utility = samples@selection
total_utility = cvx.sum(utility)
avg_utility = total_utility / utility.size
utility_over_avg = utility - avg_utility
risk = cvx.norm(utility_over_avg, 2)

constraint_number = cvx.sum(selection)==np.sum(REQUIRED_STYLES)
constraint_styles = selection@M_STYLES == REQUIRED_STYLES
constraint_agencies = cvx.max( selection@M_AGENCIES ) <= MAX_PER_AGENCY
constraint_budget = cvx.sum( selection*df['hourly_rate'].values ) <= HOURLY_BUDGET
constraints = [constraint_number, constraint_styles, constraint_agencies, constraint_budget]

alpha_value = 0.01
alpha = cvx.Parameter(pos=True, value=alpha_value)
prob = cvx.Problem(cvx.Maximize(total_utility - risk*alpha), constraints=constraints)

prob.solve(solver='ECOS_BB')
print( 'solverName', prob.solver_stats.solver_name )
print( 'solverStatus', prob.status )

selected_flags = selection.value.round().astype(np.bool)
print( selected_flags.dot(M_STYLES).astype(np.int), selected_flags.dot(M_AGENCIES).max(), selected_flags.dot(df['hourly_rate']) )
print( df.loc[selected_flags] )

这在cvxpy中有效，我得到了一个解决方案。然而，随着我将alpha_value增加到一个更高的数目来惩罚相关性，那么ECOS_BB需要很长的时间。在我的实际代码中，无论是解决问题还是返回不可行的问题，都需要超过24小时。在实际代码中，alpha_value的较低值在2到5分钟内解决。实际数据有8000个样本，约150种候选数据，以及相同的约束设置。

如果我尝试使用solver='CBC‘，那么它将立即失败，并发出错误消息。

SolverError: Either candidate conic solvers (['CBC']) do not support the cones output by the problem (SOC), or there are not enough constraints in the problem.

几个问题：

总的来说，

• 比ECOS_BB更好吗？
• ，我是否可以使用另一个更适合的自由解决程序？
• ，我能重新定义这个问题吗，这样CBC才能工作？如果我移除风险并为平均实用程序进行优化，它就可以工作得很好。
• ，我能重新制定以使ECOS_BB更快吗？

Answer 1

让我试着回答你的个人问题。

• Is CBC一般比ECOS_BB好？是的，ECOS_BB只适用于很小的玩具问题。对于线性MIP模型，CBC要先进得多。但是你的模型不是线性的，所以CBC不是你问题的正确解决者。您正在尝试求解一个MISOCP/MIQP problem.
• Is，在那里我可以使用另一个自由的求解器，它可能更适合吗？取决于。如果你是一名学者，你可以免费使用Cplex或Gurobi。如果你不是一个学者，这些解决者是昂贵的。除了ECOS_BB之外，我不知道开源MISOCP/MIQP解决程序。有一些开源的MINLP解决程序可以解决MIQPs (但是这些不受CVXPY).
• Can的支持，我重新定义了这个问题，这样CBC就可以工作了？)如果我去掉风险，只对平均实用程序进行优化，它就可以工作得很好。 (1)可能很好，但不是那么容易。也许可以写下KKT条件并形成MIP。可能是一种切割平面策略可能会奏效。此外，当我们对二进制变量进行优化时，可能会将事情线性化(如果x'Qx是二进制的，x可以线性化)。总之:这一切都需要一些工作，也许不值得付出努力。(2)是的，如果去掉风险，模型就变成线性的。CBC可以解决这个线性model.
• Can，我重新制定，使ECOS_BB更快？不是我所知道的。再说一遍，ECOS_BB并不是一个强大的解决者。对于概念模型的验证(当然，它本身是有价值的)，它可能足够好，但是对于任何真正的工作，我会看看其他的求解者。