如何线性化二值分类变量与非负连续变量的乘积？求解优化问题

已知二进制（0-1）变量与连续变量乘积的线性化方案，但不清楚二值分类变量（取两个固定常量值）与连续变量乘积的线性化方法，长期寻找答案无果。

问题变量 #

• var1：连续变量，取值范围 [0, 5000]
• var2：连续变量，取值范围 [0, 5000]

约束条件 #

• var1 + var2 = 3000

成本函数 #

成本函数为：C = var1*coeff1 + var2*coeff2
其中：

• coeff2 是正浮点数常量
• coeff1 是二值变量，取值规则为：若 var1 > threshold，则 coeff1 = x；否则 coeff1 = y（x、y、threshold 均为正浮点数常量）

直接定义 coeff1 会导致成本函数中的 var1*coeff1 成为非线性项，无法直接用线性规划求解。现有线性化方案仅适用于二进制（0-1）变量与连续变量的乘积，不清楚如何套用到二值分类变量的场景。

通过引入二进制辅助变量将非线性项转化为线性约束，具体步骤如下：

1. 引入二进制变量：定义 z（0-1变量），用来表示 coeff1 的取值状态：

   • z = 1：对应 var1 > threshold，此时 coeff1 = x
   • z = 0：对应 var1 ≤ threshold，此时 coeff1 = y

2. 线性化乘积项：将 var1*coeff1 拆分为 x*var1*z + y*var1*(1-z)，但该式仍为非线性。为此引入两个连续辅助变量 v1 和 v2，令：

   • v1 = var1 * z
   • v2 = var1 * (1 - z)
     目标函数转化为线性形式：C = x*v1 + y*v2 + var2*coeff2

3. 添加辅助约束：用大M法（M取var1的上限5000）保证辅助变量与原变量的关系：

   • v1 ≤ z * 5000：当z=0时，v1必须为0
   • v1 ≥ var1 - (1 - z)*5000：当z=1时，v1必须等于var1
   • v2 ≤ (1 - z)*5000：当z=1时，v2必须为0
   • v2 ≥ var1 - z*5000：当z=0时，v2必须等于var1

4. 添加阈值关联约束：处理var1与threshold的关系（用极小值ε近似严格大于，避免线性规划中无法处理严格不等式的问题）：

   • var1 ≥ threshold + 1e-6 - 5000*(1 - z)：当z=1时，var1至少为threshold+ε
   • var1 ≤ threshold + 5000*z：当z=0时，var1不超过threshold

import pulp
from pulp import PULP_CBC_CMD

# 创建问题实例
problem = pulp.LpProblem("Power_Cost_Minimization", pulp.LpMinimize)

# 定义变量
var1 = pulp.LpVariable("var_1", lowBound=0, upBound=5000, cat="Continuous")
var2 = pulp.LpVariable("var_2", lowBound=0, upBound=5000, cat="Continuous")

# 定义辅助二进制变量
z = pulp.LpVariable("z", cat="Binary")
# 定义辅助连续变量，用于线性化乘积
v1 = pulp.LpVariable("v1", lowBound=0, upBound=5000, cat="Continuous")
v2 = pulp.LpVariable("v2", lowBound=0, upBound=5000, cat="Continuous")

# 定义参数
x = 0.6
y = 0.9
coeff2 = 0.3
threshold = 1000
M = 5000  # 大M值，取var1的上限
epsilon = 1e-6  # 极小值，用于近似严格大于

# 添加约束
problem.addConstraint(var1 + var2 == 3000, name="constraint_sum")

# 辅助变量与原变量的关联约束
problem.addConstraint(v1 <= z * M, name="v1_upper")
problem.addConstraint(v1 >= var1 - (1 - z) * M, name="v1_lower")
problem.addConstraint(v2 <= (1 - z) * M, name="v2_upper")
problem.addConstraint(v2 >= var1 - z * M, name="v2_lower")

# var1与阈值的关联约束
problem.addConstraint(var1 >= threshold + epsilon - M * (1 - z), name="var1_above_threshold")
problem.addConstraint(var1 <= threshold + M * z, name="var1_below_threshold")

# 定义目标函数（线性形式）
problem += x * v1 + y * v2 + var2 * coeff2

# 求解问题
problem.solve(PULP_CBC_CMD(msg=1))

# 输出结果
print(f"最优解：")
print(f"var1 = {pulp.value(var1):.2f}")
print(f"var2 = {pulp.value(var2):.2f}")
print(f"z = {pulp.value(z)}")
optimal_cost = pulp.value(problem.objective)
print(f"最优成本 = {optimal_cost:.2f}")

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