如何在CVXPY中正确实现静态武器目标分配（WTA）问题？

我正尝试使用CVXPY分析静态武器目标分配（WTA）问题，先通过2武器2目标的小实例验证目标函数与约束的正确性（后续将扩展规模并添加参数），但遇到了无法解决的错误。

测试代码如下（决策变量为布尔型）：

import cvxpy as cp
import numpy as np

# Parameters
m = cp.Parameter(nonneg=True, value=2)  # Number of weapons
n = cp.Parameter(nonneg=True, value=2)  # Number of targets
q = cp.Parameter((m.value, n.value), nonneg=True)  # Probability of weapon i not destroying target j, q_{ij}=(1-p_{ij})

# Other values
ones_w = np.ones((m.value, 1))
ones_t = np.ones((n.value, 1))

# Specify notional values for q
q.value = np.array([[0.9, 0.8], [0.5, 0.7]])

# Variables
x = cp.Variable(q.shape, boolean=True) # Assignment of weapon i to target j

# Constraints
constraints = []
constraints += [x @ ones_t == ones_w]  # A weapon must be assigned to only one target

# Objective
objective = cp.Minimize(cp.sum(cp.exp(cp.multiply(x, cp.log(q)))))

# Form and solve problem
swta = cp.Problem(objective, constraints)
swta.solve(solver=SCIPY)

预期分配结果为武器1→目标2、武器2→目标1，但运行时出现错误：

cvxpy.error.SolverError: Either candidate conic solvers (['SCIPY']) do not support the cones output by the problem (ExpCone, Zero), or there are not enough constraints in the problem.

尝试了CBC、CPLEX等多种CVXPY求解器，均出现相同错误。即使添加限制每个目标仅分配一件武器的约束，错误仍未消除。若替换为简单目标函数objective = cp.Minimize(cp.sum(cp.multiply(x, q)))，问题可求解，但该函数无法反映静态WTA的真实目标。

请问如何在CVXPY中正确实现该问题？是否需要重构目标函数？该问题是否与CVXPY不兼容？

问题分析与解决方案 #

核心问题：目标函数形式不兼容整数规划求解器 #

你当前的目标函数cp.sum(cp.exp(cp.multiply(x, cp.log(q))))会生成指数锥（ExpCone）约束，而CBC、CPLEX这类整数规划求解器不支持锥约束，这是报错的根本原因。

重构目标函数：匹配WTA真实逻辑 #

静态WTA的核心目标是最小化所有目标未被摧毁的概率乘积。对于布尔变量x_ij（1表示武器i分配给目标j），每个目标j未被摧毁的概率是所有分配给它的武器未命中概率的乘积，即$\prod_{i} q_{ij}^{x_{ij}}$；整体未被摧毁的概率是所有目标的该值乘积：$\prod_{j} \prod_{i} q_{ij}^{x_{ij}}$。

由于对数函数单调递增，最小化这个乘积等价于最小化其对数形式（既避免数值下溢，又将乘积转为线性求和）：
$$\text{minimize} \quad \sum_{i,j} x_{ij} \cdot \log(q_{ij})$$

这个目标函数属于线性整数规划问题，完全兼容CVXPY的整数规划求解器。

修改后的代码 #

import cvxpy as cp
import numpy as np

# Parameters
m = cp.Parameter(nonneg=True, value=2)  # Number of weapons
n = cp.Parameter(nonneg=True, value=2)  # Number of targets
q = cp.Parameter((m.value, n.value), nonneg=True)  # Probability of weapon i not destroying target j, q_{ij}=(1-p_{ij})

# Other values
ones_w = np.ones((m.value, 1))
ones_t = np.ones((n.value, 1))

# Specify notional values for q
q.value = np.array([[0.9, 0.8], [0.5, 0.7]])

# Variables
x = cp.Variable(q.shape, boolean=True) # Assignment of weapon i to target j

# Constraints
constraints = []
constraints += [x @ ones_t == ones_w]  # Each weapon is assigned to exactly one target
# 若需要每个目标最多分配一件武器，可添加以下约束
# constraints += [ones_w.T @ x == ones_t.T]

# 重构后的目标函数：最小化未摧毁概率的对数和
objective = cp.Minimize(cp.sum(cp.multiply(x, np.log(q.value))))

# Form and solve problem
swta = cp.Problem(objective, constraints)
# 使用CBC求解器（需提前安装：pip install cylp）
swta.solve(solver=cp.CBC)

# 输出结果
print("最优分配矩阵：")
print(x.value)
print("目标函数值（未摧毁概率的对数）：", swta.value)
print("实际未摧毁概率：", np.exp(swta.value))

结果验证 #

运行修改后的代码，会得到预期的分配结果：

最优分配矩阵：
[[0. 1.]
 [1. 0.]]
目标函数值（未摧毁概率的对数）： -0.9162907318741553
实际未摧毁概率： 0.4

该结果对应武器1→目标2、武器2→目标1，未摧毁概率为0.4，确实是所有可行分配中的最小值（另一种分配的未摧毁概率为0.9*0.7=0.63）。

注意事项 #

• 确保安装对应求解器：CBC需安装cylp，CPLEX需安装官方Python包。
• 后续扩展规模时，线性整数规划形式的目标函数依然能高效求解，远优于原指数形式的非凸问题。

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