输入含零导致带斜率裕度的线性回归优化不可行问题排查

问题背景 #

使用Google OR-Tools实现带斜率裕度的无截距线性回归优化：模型为y ∈ [(a-m)x, (a+m)x]，目标是最小化斜率裕度m，同时让所有样本(x_i, y_i)满足y_i落在对应区间内。原示例在x_i非零时运行正常，但当某样本x_i=0且y_i≠0时，线性规划返回不可行解。

问题原因 #

当x_i=0时，原约束公式a*x_i ± m*abs(x_i) ≤ y_i简化为0 ≤ y_i和0 ≥ y_i，这强制要求y_i=0，但示例中对应的y_i=-2，导致约束完全矛盾，因此线性规划问题无可行解。本质就是x=0时，斜率项和裕度项全部失效，而原模型没有截距项来覆盖这种x为0时的输出偏差。

调整方案 #

方案1：特殊处理x=0样本（局限性大） #

若坚持不引入截距，只能对x_i=0的样本强制要求y_i=0，但这仅适用于y_i=0的场景，无法解决示例中的问题。

方案2：添加带裕度的截距项（推荐） #

修改模型，引入截距b和截距裕度n（n≥0），此时每个样本的输出区间变为[(a-m)x_i + (b-n), (a+m)x_i + (b+n)]，约束条件调整为y_i必须落在该区间内，目标函数可设置为最小化m+n（或根据需求加权裕度）。

修改后的代码如下：

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver('RegressionWithMarginAndIntercept', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)
# 定义变量：斜率a、斜率裕度m、截距b、截距裕度n
a = solver.NumVar(-solver.infinity(), solver.infinity(), 'a')
m = solver.NumVar(0, solver.infinity(), 'm')
b = solver.NumVar(-solver.infinity(), solver.infinity(), 'b')
n = solver.NumVar(0, solver.infinity(), 'n')

# 为每个样本添加区间约束
for x_i, y_i in zip([1, 2, 3, 0], [1, 3, 5, -2]):
    solver.Add((a - m) * x_i + (b - n) <= y_i)
    solver.Add((a + m) * x_i + (b + n) >= y_i)

# 最小化总裕度（可根据需求调整目标，比如只最小化m）
solver.Minimize(m + n)

# 求解并输出结果
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print(f"a = {a.solution_value()}")
    print(f"m = {m.solution_value()}")
    print(f"b = {b.solution_value()}")
    print(f"n = {n.solution_value()}")
else:
    print(f"求解状态码：{status}，无可行解")

该方案中，当x_i=0时，约束简化为b - n ≤ y_i ≤ b + n，能够覆盖y_i=-2的情况，同时保持其他样本的约束逻辑，使问题存在可行解。

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