添加约束后GEKKO求解无法得到最优解的技术问询

问题概述 #

在使用GEKKO进行图优化时，移除约束(b)后求解器能输出变量s的全局最优解；但添加约束(b)且将DEVICE_MEM设置为极大值（理论上该约束应为冗余约束，不影响结果）后，s的求解结果不再是最优解。已尝试APOPT(solvertype=1)和IPOPT(solvertype=3)两种求解器，结果一致。

问题背景 #

这是一个图优化问题：

• N：图中节点数量
• E：图中所有边的集合
• c/d/m：节点的三类成本参数
• r：边的成本参数
• 每个节点对应一个二进制向量s[i]，表示该节点的策略选择（向量中仅有一个元素为1，其余为0），目标是为每个节点选择最优策略以最小化总成本。

复现代码 #

核心逻辑代码 #

from gekko import GEKKO
import numpy as np
from random import randrange

# 测试用节点数
N = 5
DEVICE_MEM = 100000  # 极大值，理论上不会触发约束

gekko = GEKKO(remote=True)
# 创建二进制变量，每个节点对应一个长度为s_len[i]的向量
s_len = np.ones(N, dtype=int) * 10
s = []
for i in range(N):
    s.append(gekko.Array(gekko.Var, s_len[i], value=0, lb=0, ub=1, integer=True))

# 生成常量参数
def create_c_d_r_m_L():
    # c, d, m 节点成本：第i个节点的所有策略成本均为i
    c, d, m = [], [], []
    for i in range(N):
        c.append([i]*s_len[i])
        d.append([i]*s_len[i])
        m.append([i]*s_len[i])
    # r 边成本：每条边(i,j)的所有策略组合成本均为i*j
    E = [(0,1), (1,2), (2,3), (3,4)]  # 示例边集合
    r = []
    for (i,j) in E:
        cur_r = [i*j]*(s_len[i]*s_len[j])
        r.append(np.array(cur_r).reshape(s_len[i], s_len[j]))
    # L 随机生成每个t对应的节点集合
    L = []
    for i in range(N):
        cur_L = [randrange(N) for _ in range(10)]
        L.append(cur_L)
    return c, d, r, m, L

c, d, r, m, L = create_c_d_r_m_L()

# 定义目标函数
def objective():
    obj = 0
    for i in range(N):
        obj += np.dot(s[i], c[i]) + np.dot(s[i], d[i])
    for idx, (i, j) in enumerate(E):
        obj += np.dot(np.dot(s[i], r[idx]), s[j])
    return obj

# 添加约束
# (a) 每个节点的策略向量必须且只能选一个
for i in range(N):
    gekko.Equation(gekko.sum(s[i]) == 1)
# (b) 内存约束（冗余，因为DEVICE_MEM极大）
for t in range(N):
    peak_mem = gekko.sum([np.dot(s[i], m[i]) for i in L[t]])
    gekko.Equation(peak_mem < DEVICE_MEM)

# 求解
gekko.Obj(objective())
gekko.solve(disp=True)

# 输出结果
print("s变量取值：")
for i in range(N):
    print(f"节点{i}: {[v.value[0] for v in s[i]]}")

可能的原因分析 #

1. Numpy与GEKKO变量的兼容性问题
   代码中使用np.dot()处理GEKKO变量（如s[i]），虽然GEKKO对部分Numpy操作有兼容，但这种混合用法可能导致求解器无法正确识别变量的线性/非线性特性，尤其是在整数规划场景下，会干扰求解器的分支定界逻辑。

2. 不等式约束的方向与精度问题
   使用peak_mem < DEVICE_MEM而非peak_mem <= DEVICE_MEM，对于整数变量来说，虽然DEVICE_MEM极大，但求解器在处理严格小于约束时，可能引入数值精度误差，导致原本满足条件的最优解被误判为不满足，从而被迫选择次优解。

3. 冗余约束对整数规划求解的影响
   即使约束理论上冗余，整数规划求解器（如APOPT）在分支定界过程中，会将所有约束纳入搜索空间的剪枝逻辑。冗余约束可能改变求解器的搜索路径，使其提前终止于局部最优解，而非全局最优。

4. 求解器整数容忍度设置
   默认的整数容忍度（如APOPT的minlp_integer_tol）可能导致求解器将接近整数的非整数解判定为可行解，而冗余约束的存在可能放大这种误差，导致最终解偏离全局最优。

解决方案 #

1. 替换Numpy操作为GEKKO内置函数 #

将np.dot()替换为GEKKO的gekko.dot()，确保求解器能正确解析变量关系：

# 修正后的目标函数
def objective():
    obj = 0
    for i in range(N):
        obj += gekko.dot(s[i], c[i]) + gekko.dot(s[i], d[i])
    for idx, (i, j) in enumerate(E):
        obj += gekko.dot(gekko.dot(s[i], r[idx]), s[j])
    return obj

# 修正后的约束(b)
for t in range(N):
    peak_mem = gekko.sum([gekko.dot(s[i], m[i]) for i in L[t]])
    gekko.Equation(peak_mem <= DEVICE_MEM)

2. 调整约束不等式方向 #

将严格小于<改为小于等于<=，避免数值精度问题导致的误判。

3. 优化求解器参数 #

针对整数规划场景，调整APOPT的参数以强化全局最优搜索：

gekko.solver_options = ['minlp_maximum_iterations 10000',
                        'minlp_integer_tol 1e-6',
                        'minlp_gap_tol 1e-6']
gekko.solve(disp=True)

• minlp_maximum_iterations：增加最大迭代次数，确保求解器有足够时间搜索全局最优
• minlp_integer_tol：降低整数容忍度，减少非整数解被判定为可行的概率
• minlp_gap_tol：降低最优解间隙，确保求解结果更接近全局最优

4. 移除冗余约束（临时验证方案） #

如果确认约束(b)确实冗余，可在求解时动态判断是否添加：

if DEVICE_MEM < 某个实际阈值:
    for t in range(N):
        peak_mem = gekko.sum([gekko.dot(s[i], m[i]) for i in L[t]])
        gekko.Equation(peak_mem <= DEVICE_MEM)

验证建议 #

1. 先测试修正后的代码，确认替换np.dot为gekko.dot后，添加约束(b)是否能得到正确的最优解。
2. 单独调整约束方向，观察结果变化，验证数值精度是否为问题根源。
3. 逐步调整求解器参数，对比不同参数下的求解结果，找到最适合当前问题的参数组合。

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