CPLEX中二次约束线性化相关技术问题咨询

一、对CPLEX自动线性化二次约束的理解 #

你的理解是正确的：当处理混合整数二次约束规划（MIQCP）问题时，若CPLEX检测到二次约束为凸性，且未禁用自动线性化机制，它会将二次约束转化为线性约束，输出中以“Reduced MIQCP ...”开头的行就是该线性化过程的明确标识。

二、问题1：无需CPLEX简化、直接使用原约束的方法 #

CPLEX仅支持凸二次约束的直接求解（无需线性化），若你的二次约束为非凸性，CPLEX本身无法直接处理原约束——这也是你设置reduce=0后无法运行的核心原因。若想绕开CPLEX的自动线性化，可尝试以下两种方向：

• 更换支持非凸MIQCP的求解器：例如Gurobi（针对非凸二次约束有专门的分支定界处理逻辑）、SCIP（开源求解器，支持非凸二次约束的直接求解）。
• 手动重构约束：如果二次约束存在特殊结构（如可分解为凸分量、或为特定形式的二次等式），可尝试手动将其转化为CPLEX支持的凸约束形式，但这依赖于约束的具体结构细节。

三、问题2：线性化过程细节与间隙停滞原因 #

线性化过程的核心逻辑

CPLEX针对凸二次约束的线性化主要采用两种技术：

• McCormick包络：针对变量乘积项（如x*y），基于变量的上下界生成线性松弛约束，这是MIQCP场景中最常用的线性化方法。
• 分片线性近似：对非线性二次项（如x²），将变量定义域划分为多个区间，用分段线性函数近似二次曲线，生成对应的线性约束。

间隙停滞的常见原因

最优解间隙快速降至0.05%后停滞，通常源于以下两点：

• 线性化后的松弛问题已足够紧致，剩余间隙来自线性化松弛与原问题的微小偏差，或整数变量的候选组合已接近最优，但分支定界需遍历大量节点才能验证最优性。
• 可通过调整CPLEX参数尝试加速收敛：
  • 设置mip.tolerances.mipgap=0.0005（收紧目标间隙阈值）
  • 开启mip.strategy.probe=2（加强节点探测）
  • 切换分支策略为mip.strategy.branch=1
  • 增加mip.limits.nodes的上限，允许求解器遍历更多节点

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