MILP模型中整数变量除法的线性化方法求解咨询

针对你给出的Cost加权平均等式：

Cost = sum(CV[i]*Q[i] for i in range(10)) / sum(Q[i] for i in range(10))

我们可以通过引入辅助变量和线性约束消除除法与非线性项，适配混合整数线性规划（MILP）模型，具体步骤如下：

1. 基础变量定义 #

在Docplex中定义原变量与必要辅助变量：

from docplex.mp.model import Model

# 初始化模型
mdl = Model("cost_linearization")

# 定义整数变量Q[i]（共10个，假设非负，可按需调整下界）
Q = mdl.integer_var_list(10, lb=0, name="Q")

# 辅助整数变量S：代表Q[i]的总和，设置lb=1避免除以0
S = mdl.integer_var(lb=1, name="S")

# 连续变量Cost：目标加权平均值，边界设为CV的最值
CV = [/* 你的常量参数列表 */]
C_min = min(CV)
C_max = max(CV)
Cost = mdl.continuous_var(lb=C_min, ub=C_max, name="Cost")

2. 绑定总和约束 #

将S与Q[i]的和建立线性关联：

mdl.add_constraint(S == mdl.sum(Q[i] for i in range(10)), "sum_Q_constraint")

3. 线性化非线性乘积项 #

原式等价于 sum(CV[i]*Q[i]) = Cost * S，其中Cost*S是非线性乘积项，这里用二进制变量+大M法完成线性化：

3.1 确定变量边界 #

根据Q[i]的实际取值范围计算S的最大可能值：

Q_max = /* 单个Q[i]的上界，按需设置 */
S_max = 10 * Q_max

3.2 添加二进制变量与约束 #

引入二进制变量标记S的取值，将乘积项转化为线性形式：

# 二进制变量z_k：对应S=k的情况（k从1到S_max）
z = mdl.binary_var_list(range(1, S_max+1), name="z")

# 约束S等于对应k的加权和
mdl.add_constraint(S == mdl.sum(k * z[k] for k in range(1, S_max+1)), "S_def")

# 约束仅能有一个z_k为1
mdl.add_constraint(mdl.sum(z[k] for k in range(1, S_max+1)) == 1, "z_unique")

# 线性化核心约束：sum(CV[i]*Q[i]) = Cost * S
mdl.add_constraint(
    mdl.sum(CV[i] * Q[i] for i in range(10)) == mdl.sum(k * Cost * z[k] for k in range(1, S_max+1)),
    "cost_linear_constraint"
)

4. 高效优化方案（可选） #

若S_max过大导致二进制变量过多，可利用Cost的加权平均性质简化约束（仅保证Cost取值符合加权平均范围，严格等式仍需二进制方法）：

sum_CVQ = mdl.sum(CV[i] * Q[i] for i in range(10))
# 基础边界约束
mdl.add_constraint(sum_CVQ >= C_min * S, "cost_lower")
mdl.add_constraint(sum_CVQ <= C_max * S, "cost_upper")
# 细化加权贡献约束
for i in range(10):
    mdl.add_constraint(sum_CVQ >= CV[i] * Q[i] + C_min * (S - Q[i]), f"cost_bound_{i}")

后续处理 #

你已掌握整数变量乘积的线性化方法，只需将线性化后的Cost代入目标函数与另一整数变量的乘积项即可完成模型构建。

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