CVXPY求解含方差最小化的MIP分组问题报错求助

问题背景 #

尝试用CVXPY求解混合整数规划（MIP）学生分组优化问题：将学生分配到班级，同时最大化分配人数、最小化班级内学生年龄方差。仅移除方差计算部分时，求解正常；加入方差后则报错。

依赖版本 #

cvxopt==1.3.0
cvxpy==1.2.2
numpy==1.22.0
pandas==1.5.2

核心代码 #

导入模块：

import pandas as pd 
import numpy as np 
import cvxpy as cp 

均值与方差定义：

def mean(x):
    return cp.sum(x) / x.size

def variance(X:cp.Variable, mode='unbiased'):
    if mode == 'unbiased':
        scale = X.size - 1
    elif mode == 'mle':
        scale = X.size
    else:
        raise ValueError('unknown mode: ' + str(mode))
    return cp.sum_squares(X - mean(X)) / scale

年龄方差成本函数：

def age_cost(df:pd.DataFrame,X:cp.Variable):
    cost=0
    for i,age in df.Age.items():
        cost+=variance(X[:][i]*age)
    return cost

目标函数与求解：

# 最大化分配人数的等价最小化形式
objective_component1=students_num-assigned @ np.ones(DAYS*SLOTS) @ np.ones(students_num)
# 年龄方差成本
objective_component2=age_cost(my_data,assigned)
# 组合目标
objective=cp.Minimize(objective_component1+objective_component2)

# 构建并求解问题
problem1=cp.Problem(objective,constraints)
problem1.solve(verbose=True)

报错信息 #

===============================================================================
                                     CVXPY                                     
                                     v1.2.2                                    
===============================================================================
(CVXPY) Jan 04 03:09:59 PM: Your problem has 4550 variables, 3382 constraints, and 0 parameters.
(CVXPY) Jan 04 03:10:01 PM: It is compliant with the following grammars: DCP, DQCP
(CVXPY) Jan 04 03:10:01 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)
(CVXPY) Jan 04 03:10:01 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.
...
<error stack omitted>
...

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

疑问解答 #

1. 是否使用了错误的求解器？ #

是的，你当前使用的GLPK_MI不适合加入方差后的问题：

• 移除方差时，目标函数是线性的，属于线性混合整数规划（MIP），GLPK_MI可以处理这类问题；
• 加入方差后，目标函数包含cp.sum_squares（平方项），问题会被转化为混合整数二阶锥规划（SOCP-MIP），而GLPK_MI仅支持线性MIP，不支持二阶锥（SOC）类型的约束/目标，因此报错。

2. 如何判断当前问题适合的求解器？ #

• 明确问题类型：加入方差后，你的问题是凸混合整数二阶锥规划（SOCP-MIP）——方差计算是凸二次函数，加上二进制整数变量，属于SOCP-MIP范畴；
• 筛选支持的求解器：CVXPY支持的这类求解器包括：
  • 商业求解器：Gurobi、CPLEX、MOSEK（均支持SOCP-MIP）；
  • 开源求解器：SCIP（需安装cvxpy-scip接口）；
• 检查已安装求解器：通过print(cp.installed_solvers())查看本地已安装的求解器，再确认每个求解器支持的问题类型；
• 指定求解器：调用solve()时显式指定合适的求解器，例如：

  problem1.solve(solver=cp.SCIP, verbose=True)
  

3. "compliant with DCP grammar"是否意味着问题形式正确？ #

是的，但仅代表问题符合有向无环规划（DCP）规则：

• DCP合规说明CVXPY可以正确解析你的问题，且问题是凸优化问题（这是求解的前提）；
• 但DCP合规不代表当前求解器能支持该问题的具体类型——比如你的问题是SOCP-MIP，GLPK_MI不支持这类问题，即使DCP合规也无法求解。

内容的提问来源于stack exchange，提问作者Andrea Montalbani