如何在PuLP中适配abs()与max()？改写ILP求解Python代码

PuLP确实不支持直接在目标函数或约束中使用abs()和max()，需要将非线性的表达式转换为线性等价形式，以下是具体的改写方案和完整代码：

核心转换思路 #

1. 目标函数：Min Σ|a_i * x_i| #

因为x_i只能取{-1,0,1}，所以|a_i * x_i|等价于|a_i| * |x_i|。我们引入辅助变量y_i（取值0或1）来表示|x_i|，并通过约束确保y_i与x_i的关系：

• 当x_i=±1时，y_i必须为1；当x_i=0时，y_i为0。
• 对应的线性约束：x_i ≤ y_i 和 -x_i ≤ y_i

这样目标函数就转化为线性的Σ(|a_i| * y_i)。

2. 约束条件：max{|x_i|} = 1 #

该约束要求至少有一个x_i取±1（即至少一个y_i=1），用线性约束表示为：Σy_i ≥ 1，避免所有x_i都为0的情况。

完整可运行代码 #

import pulp
import numpy as np
import pandas as pd

# 示例数据，替换为你的实际数据框
df = pd.DataFrame([[3, -2, 5]])
c = np.array(df.iloc[0].values)
n = len(c)

# 定义ILP问题（最小化）
myilp = pulp.LpProblem("ILP", pulp.LpMinimize)

# 定义变量x_i ∈ {-1, 0, 1}
x = {i: pulp.LpVariable(name=f"x{i}", lowBound=-1, upBound=1, cat=pulp.LpInteger) for i in range(n)}

# 定义辅助变量y_i ∈ {0,1}，表示|x_i|
y = {i: pulp.LpVariable(name=f"y{i}", lowBound=0, upBound=1, cat=pulp.LpInteger) for i in range(n)}

# 添加x与y的关联约束
for i in range(n):
    myilp += x[i] <= y[i]
    myilp += -x[i] <= y[i]

# 添加max{|x_i|}=1的等价约束：至少一个y_i=1
myilp += pulp.lpSum(y[i] for i in range(n)) >= 1

# 定义线性目标函数
myilp += pulp.lpSum(np.abs(c[i]) * y[i] for i in range(n))

# 求解问题
myilp.solve()

# 输出结果
print("求解状态:", pulp.LpStatus[myilp.status])
for var in myilp.variables():
    print(f"{var.name}: {var.varValue}")
print("最小目标值:", pulp.value(myilp.objective))

结果说明 #

以示例数据c=[3,-2,5]为例，最优解是x1=-1（对应y1=1），其余x_i=0，目标值为2，符合预期——选择绝对值最小的系数对应的x_i取非零值，实现目标函数最小化。

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