GLOP求解LP模型时约束用==返回INFEASIBLE但预期可行

问题背景 #

使用GLOP默认线性求解器处理已知存在最优解的LP问题时，当约束使用==时求解器返回INFEASIBLE；将约束改为>=时能得到有效解。手动推导了一个自认为满足等式约束的解，但尝试设置MPSolverParameters的容差参数后问题仍未解决，需排查是模型设置错误还是参数配置不当。

复现代码 #

from ortools.linear_solver import pywraplp
from ortools.glop.parameters_pb2 import GlopParameters


def solveRMP(patterns, orders):
    """ Solve the relaxed LP problem of minimizing sum(c*X_j) given the current patterns.

        Output: solution   - solution to the relaxed LP problem. ndarray of size(n)
    """
    n = len(patterns[0])
    num_patterns = len(patterns[1])

    solver = pywraplp.Solver.CreateSolver('GLOP')
    if not solver:
        return -1

    constraint = []
    # 声明变量数组
    X = [solver.NumVar(0.0, orders[i], f'x_{i}') for i in range(num_patterns)]

    cost = sum(X[j] for j in range(num_patterns))
    solver.Minimize(cost)

    # 创建等式约束：sum(A_ij*X_j) == orders_i
    for i in range(n):
        constraint.append(solver.Add(sum(X[j] * patterns[i][j] for j in range(num_patterns)) ==
                                     orders[i]))

    # 原尝试的参数设置（无效）
    # params = pywraplp.MPSolverParameters()
    # params.DUAL_TOLERANCE = 1e-3
    # params.PRIMAL_TOLERANCE = 1e-3
    # status = solver.Solve(params)

    status = solver.Solve()

    # 状态检查
    if status != solver.OPTIMAL:
        print('The problem does not have an optimal solution!')
        if status == solver.FEASIBLE:
            print('A potentially suboptimal solution was found.')
        elif status == solver.INFEASIBLE:
            print('There is not a feasible solution')
        elif status == solver.ABNORMAL:
            print('The solver encountered a problem.')

    solution = [X[i].SolutionValue() for i in range(num_patterns)]
    dual = [constraint[i].DualValue() for i in range(n)]
    obj = solver.Objective().Value()

    return solution, dual, status, obj


orders = [20, 18, 16, 14, 12, 10, 20, 18, 18, 14, 12, 25, 22]
A = [[2, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
     [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
     [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
     [0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0],
     [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 1, 0, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0],
     [0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
     [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1]]


sol, dual, stat, obj = solveRMP(A, orders)
print(sol, dual, obj, stat)

问题分析 #

1. 模型核心错误 #

原代码中num_patterns = len(patterns[1])是错误的，应为num_patterns = len(patterns[0])——patterns是二维数组，列数对应变量（模式）数量，行数对应约束数量。这个维度匹配错误会导致变量声明和约束构建逻辑混乱，是等式约束下无解的主要原因。

2. 参数配置错误 #

GLOP求解器的容差参数不能通过MPSolverParameters设置，需使用GLOP专属的参数配置方式：

• 方法一：通过GlopParameters protobuf对象构建参数
• 方法二：使用solver.setSolverSpecificParametersAsString()直接传入参数字符串

3. 手动解验证 #

将你提供的解[4.8, 5.3, 5.3, 3.6, 12.7, 5.0, 3.8, 7.0, 1.4, 9.0, 3.7, 7.0, 6.0]代入约束验证，所有等式均成立，说明模型修正后确实存在可行解。

正确的参数配置与模型修正 #

修正后的代码（含GLOP容差设置） #

from ortools.linear_solver import pywraplp
from ortools.glop.parameters_pb2 import GlopParameters


def solveRMP(patterns, orders):
    """ Solve the relaxed LP problem of minimizing sum(c*X_j) given the current patterns.

        Output: solution   - solution to the relaxed LP problem. ndarray of size(n)
    """
    n = len(patterns)  # 约束数量（行数）
    num_patterns = len(patterns[0])  # 变量/模式数量（列数）

    solver = pywraplp.Solver.CreateSolver('GLOP')
    if not solver:
        return -1

    # 配置GLOP可行性容差
    params = GlopParameters()
    params.solution_feasibility_tolerance = 1e-3
    solver.setSolverSpecificParametersFromString(params.SerializeToString())

    # 或者使用字符串方式配置：
    # solver.setSolverSpecificParametersAsString('solution_feasibility_tolerance: 1e-3')

    constraint = []
    # 声明变量数组，若没有明确上限可设为inf，需根据业务逻辑调整
    X = [solver.NumVar(0.0, float('inf'), f'x_{i}') for i in range(num_patterns)]

    cost = sum(X[j] for j in range(num_patterns))
    solver.Minimize(cost)

    # 创建等式约束：sum(A_ij*X_j) == orders_i
    for i in range(n):
        lhs = sum(X[j] * patterns[i][j] for j in range(num_patterns))
        constraint.append(solver.Add(lhs == orders[i]))

    status = solver.Solve()

    # 状态检查
    if status != solver.OPTIMAL:
        print('The problem does not have an optimal solution!')
        if status == solver.FEASIBLE:
            print('A potentially suboptimal solution was found.')
        elif status == solver.INFEASIBLE:
            print('There is not a feasible solution')
        elif status == solver.ABNORMAL:
            print('The solver encountered a problem.')
    else:
        print('Optimal solution found!')

    solution = [X[i].SolutionValue() for i in range(num_patterns)]
    dual = [constraint[i].DualValue() for i in range(n)]
    obj = solver.Objective().Value()

    return solution, dual, status, obj


orders = [20, 18, 16, 14, 12, 10, 20, 18, 18, 14, 12, 25, 22]
A = [[2, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
     [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
     [0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2],
     [0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0],
     [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 1, 0, 0, 0, 0, 2, 0, 1, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0],
     [0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
     [0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1]]


sol, dual, stat, obj = solveRMP(A, orders)
print("Solution:", sol)
print("Dual values:", dual)
print("Objective value:", obj)
print("Status:", stat)

关键修正点 #

1. 维度匹配：调整n和num_patterns的计算逻辑，确保约束与变量维度对应。
2. 参数配置：使用GLOP专属的参数设置方式，确保容差参数生效。
3. 变量上限：原代码中变量上限设为orders[i]可能不符合业务逻辑，若无明确限制可设为float('inf')，需根据实际场景调整。

总结 #

问题根源是模型维度计算错误导致约束与变量不匹配，其次是参数配置方式错误（GLOP不支持MPSolverParameters设置容差）。修正维度并使用正确的GLOP参数配置后，求解器可找到等式约束下的最优解。

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