Gekko-APMonitor求解线性分式目标MINLP问题遇收敛困难求助

需求解最大化目标函数$\boldsymbol{a}^{T\boldsymbol{x}/\boldsymbol{b}}T\boldsymbol{x}$的MINLP问题，约束条件为$d \leq \boldsymbol{c}^T\boldsymbol{x} \leq e$。其中：

• 决策向量$\boldsymbol{x}=[x_1,x_2,\dots,x_n]$为非负整数向量
• 向量$\boldsymbol{a}、\boldsymbol{b}、\boldsymbol{c}$为正实数向量
• 常数$d、e$为正上下界

该问题具备可行性（将目标函数替换为0时可得到可行解）。使用Gekko-APMonitor求解时遇到障碍，需明确：

1. APMonitor是否支持求解线性分式目标函数的问题
2. 此类问题的处理方法
3. 可尝试调整的求解器选项以解决当前问题

使用的求解器配置代码 #

from gekko import GEKKO

model = GEKKO() 
model.options.SOLVER=1 

model.solver_options = ['minlp_maximum_iterations 100', \
                        'minlp_max_iter_with_int_sol 10', \
                        'minlp_as_nlp 0', \
                        'nlp_maximum_iterations 50', \
                        'minlp_branch_method 1', \
                        'minlp_print_level 8',  \
                        'minlp_integer_tol 0.05', \
                        'minlp_gap_tol 0.001']
model.solve(disp=True)

求解输出 #

apm 67.162.115.84_gk_model0

 ----------------------------------------------- #

APMonitor, Version 1.0.1
APMonitor Optimization Suite #

--------- APM Model Size ------------
Each time step contains
Objects : 7
Constants : 0
Variables : 5626
Intermediates: 0
Connections : 4914
Equations : 4913
Residuals : 4913

Number of state variables: 5626
Number of total equations: - 4919
Number of slack variables: - 2 #

Degrees of freedom : 705

---

Steady State Optimization with APOPT Solver #

Iter: 1 I: -9 Tm: 75.50 NLPi: 251 Dpth: 0 Lvs: 0 Obj: 0.00E+00 Gap:
NaN
Warning: no more possible trial points and no integer solution
Maximum iterations

---

Solver : APOPT (v1.0)
Solution time : 75.5581999999995 sec
Objective : NaN
Unsuccessful with error code 0 #

Creating file: infeasibilities.txt
Use command apm_get(server,app,'infeasibilities.txt') to retrieve file
@error: Solution Not Found
Not successful
Gekko Solvetime: 1.0 s

#################################################

APPINFO = 0 - a successful solution
APPSTATUS =1 - solver converges to a successful solution

Solver status - Not successful, exception thrown

decision variable =[0,0, ...,0].

1. APMonitor对线性分式目标函数的支持 #

APMonitor不直接支持线性分式目标函数（形如$\frac{\boldsymbol{a}^{T\boldsymbol{x}}{\boldsymbol{b}}T\boldsymbol{x}}$），但可通过变量替换将其转化为求解器可处理的形式。由于$\boldsymbol{b}$为正实数向量、$\boldsymbol{x}$是非负整数向量，$\boldsymbol{b}^T\boldsymbol{x} > 0$，这为转化提供了基础。

2. 线性分式目标函数的处理方法 #

最大化$\frac{\boldsymbol{a}^{T\boldsymbol{x}}{\boldsymbol{b}}T\boldsymbol{x}}$可通过以下两种方式转化：

方式一：变量替换转化为MINLP #

引入新变量$t = \frac{1}{\boldsymbol{b}^{T\boldsymbol{x}}$，目标函数变为最大化$\boldsymbol{a}}T\boldsymbol{x} \cdot t$，同时添加约束：
$$\boldsymbol{b}^T\boldsymbol{x} \cdot t = 1$$
$$d \leq \boldsymbol{c}^T\boldsymbol{x} \leq e$$
$$\boldsymbol{x} \geq 0, \boldsymbol{x} \text{为整数}, t > 0$$
转化后为标准MINLP问题，APOPT可处理，需注意给$t$设置合理初始值（基于已知可行解计算）。

方式二：二分法参数化目标 #

目标函数取值范围有界（$\boldsymbol{a},\boldsymbol{b}$为正向量，$\boldsymbol{x}$满足$d \leq \boldsymbol{c}^T\boldsymbol{x} \leq e$），可通过二分法寻找最大的$\lambda$，使得以下线性整数规划问题可行：
$$\boldsymbol{a}^T\boldsymbol{x} - \lambda \boldsymbol{b}^T\boldsymbol{x} \geq 0$$
$$d \leq \boldsymbol{c}^T\boldsymbol{x} \leq e$$
$$\boldsymbol{x} \geq 0, \boldsymbol{x} \text{为整数}$$
每次迭代求解上述MILP问题，判断可行性后缩小$\lambda$的范围，直到满足精度要求。该方法将MINLP转化为一系列MILP问题，求解稳定性更高。

3. 求解器选项调整建议 #

针对当前求解失败的情况，建议调整以下APOPT选项：

• 增加迭代次数：将minlp_maximum_iterations从100改为500或更高，给分支定界过程足够时间。
• 放宽整数容忍度：将minlp_integer_tol从0.05调整为0.1，避免因整数约束过严导致无解。
• 切换分支方法：将minlp_branch_method从1（最不可行分支）改为2（伪成本分支），更适合大规模问题。
• 开启热启动：添加minlp_hot_start 1，利用之前迭代信息加速求解。
• 增加NLP迭代次数：将nlp_maximum_iterations从50改为200，避免NLP子问题提前终止。
• 设置初始可行解：将已知的可行解（目标为0时的解）赋值给$\boldsymbol{x}$的初始值（x.value = [可行解向量]），帮助求解器快速找到整数解。

另外，求解输出中APPINFO和APPSTATUS与实际状态不一致是APMonitor的已知小问题，以求解器输出的Unsuccessful with error code 0和@error: Solution Not Found为准，可查看infeasibilities.txt分析约束违反情况。

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