Python非线性优化求解座位安排问题的求解器咨询

你的问题属于混合整数非线性规划（MINLP），因为目标函数包含布尔变量的乘积项，且变量是离散的布尔型。以下是针对问题的具体分析和解决方案：

原代码的问题 #

1. 约束写法错误：不能用NumPy的np.sum、np.max处理CVXPY变量，必须使用CVXPY内置的cp.sum等函数，否则无法生成正确的优化问题模型。
2. 目标函数逻辑表述：原目标的计算逻辑方向正确，但需要确保用CVXPY的算子而非NumPy函数处理变量。

适合的求解器 #

针对这类MINLP问题，CVXPY支持以下求解器：

• SCIP：开源的MINLP求解器，对整数非线性问题支持良好，适合中小规模问题，需单独安装。
• Gurobi/CPLEX：商业求解器，性能强劲，处理大规模问题效率更高，但需要官方授权。
• Bonmin：开源MINLP求解器，属于COIN-OR套件，可通过CVXPY调用。

修正后的代码示例 #

import numpy as np
import cvxpy as cp

# 数据定义
PEOPLE = 6
TABLES = 3
SIZE_TABLES = 2

score = np.array([
    [0, 5, 3, 2, 10, 9],
    [10, 0, 3, 2, 10, 9],
    [8, 5, 0, 2, 10, 9],
    [0, 5, 3, 0, 10, 9],
    [20, 5, 3, 2, 0, 9],
    [15, 5, 3, 2, 10, 0]
])

# 变量：a[i,t] = 1 表示第i个人坐在第t张桌子
a = cp.Variable((PEOPLE, TABLES), boolean=True)

# 约束条件
constraints = [
    # 每个人仅能分配到一张桌子
    cp.sum(a, axis=1) == 1,
    # 每张桌子人数不超过容量
    cp.sum(a, axis=0) <= SIZE_TABLES
]

# 目标函数：最大化所有同桌人员的得分总和
objective = cp.Maximize(cp.sum(cp.multiply(score @ a, a)))

# 构建问题并求解
problem = cp.Problem(objective, constraints)

# 使用SCIP求解（需先安装：pip install pyscipopt）
# 若有Gurobi授权，可替换为 solver=cp.GUROBI
problem.solve(solver=cp.SCIP)

# 输出结果
print("座位安排矩阵：")
print(np.round(a.value))

注意事项 #

• 安装SCIP：执行pip install pyscipopt即可，若遇编译问题需参考SCIP官方文档配置依赖环境。
• 商业求解器：Gurobi和CPLEX在处理大规模问题时性能远超开源求解器，但需获取合法授权才能使用。
• 变量处理：所有涉及CVXPY变量的运算必须使用CVXPY内置算子，不能混用NumPy函数，否则会导致模型构建失败。

内容的提问来源于stack exchange，提问作者Nöldoran