含指数目标函数的指派问题：Gurobi替代方案与解决方法

方案一：对数变换（推荐，无需更换工具） #

最大化(∏(r_ij * x_ij))^0.5等价于最大化0.5 * ∑(ln(r_ij) * x_ij)——由于对数函数严格单调递增，两者的最优解完全一致。通过这个变换，原本的非线性目标会转化为线性形式，Gurobi可以直接处理。

修改你的目标函数代码：

import math

# 预计算每个评分的对数值
log_ratings = {(i,j): math.log(ratings[(i,j)]) for (i,j) in permutations}
# 构建线性目标函数
m.setObjective(0.5 * gp.quicksum(log_ratings[(i,j)] * assign[(i,j)] for (i,j) in permutations), sense=GRB.MAXIMIZE)

方案二：使用支持混合整数非线性规划（MINLP）的工具 #

如果对数变换不适用（比如问题包含其他无法线性化的非线性约束），可以换用支持MINLP的求解器：

• Pyomo + Bonmin/IPOPT：Pyomo是通用建模框架，Bonmin专门处理混合整数非线性问题，IPOPT适用于连续非线性场景
• SciPy.optimize：适合小规模问题，但处理整数变量需要结合分支定界或启发式方法
• CPLEX：部分非线性表达式支持比Gurobi更灵活（仍优先推荐线性变换方案）

以Pyomo为例的简化建模示例：

from pyomo.environ import ConcreteModel, Var, Objective, Constraint, Binary, maximize, log
import pyomo.opt as po

model = ConcreteModel()
model.assign = Var(permutations, within=Binary)

# 添加个体分配约束
model.individual_constr = Constraint(individuals, rule=lambda m, i: sum(m.assign[(i,j)] for j in groups) == 1)
# 添加组容量约束
model.capacity_constr = Constraint(groups, rule=lambda m, p: sum(m.assign[(i,p)] for i in individuals) <= capacity[p])

# 目标函数（同样用对数变换简化，若需保留原形式可直接写乘积的平方根）
model.obj = Objective(expr=0.5 * sum(log(ratings[(i,j)]) * model.assign[(i,j)] for (i,j) in permutations), sense=maximize)

solver = po.SolverFactory('bonmin')
solver.solve(model)

关键注意事项 #

• 确保所有ratings值大于0，否则对数运算会报错（你的示例中是0-1的随机数，满足要求）
• 若存在r_ij=0的情况，可给每个值加极小正数（如1e-8）避免异常

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