ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations

paper MINLP global optimization branch-and-cut GAMS
Authors: Ruth Misener, Christodoulos A. Floudas
Source: J Glob Optim (2014) 59:503–526 · DOI: 10.1007/s10898-014-0166-2
Affiliations: Princeton University (现 Imperial College London)

问题

混合整数非线性规划（MINLP）是优化领域最难的问题之一——连续变量 + 整数变量 + 非凸非线性约束。2014 年前，全局 MINLP 求解器要么只能处理二次问题（GloMIQO），要么只能处理 signomial 问题（MISO），没有一个统一框架。

ANTIGONE 的目标：将 MIQCQP 和 MISO 两个框架统一起来，扩展到包含 exponential 和 logarithmic 函数的通用 MINLP，并在 2,571 个标准测试问题上与其他全局求解器对比。

翻译

一个类比：乐高积木式的优化器

想象你要搭一座很复杂的建筑（求解一个 MINLP）。传统方法是为每种建筑风格（二次/signomial/exponential）设计专用工具。ANTIGONE 的做法不同：

Term-based underestimation = 乐高积木

把任何复杂的非线性表达式拆成一堆标准「积木」（Term）：bilinear、signomial、exponential、logarithmic、fractional、composite……每种积木都有预制的凸化方法（McCormick envelope、αBB、secant line……）。

搭建新的优化器 = 选择合适的积木 + 组合。添加新的非线性类型 = 设计一块新积木，插入框架。

ANTIGONE 的核心贡献不是某个单一算法——而是一个可扩展的面向对象架构，让每种非线性 term 都能被独立凸化、独立识别特殊结构、独立参与 branch-and-cut。

架构

三阶段流水线

User-defined MINLP │ ▼ [1. Reformulate] │ Factorable decomposition → Term-based representation │ Flatten: log(x₁^a · x₂^b) → a·log(x₁) + b·log(x₂) │ Flatten: e^x₁ · e^x₂ → e^(x₁+x₂) │ ▼ [2. Detect Special Structure] │ RLT equations (reformulation-linearization) │ Convexity/concavity detection (interval arithmetic) │ Edge-convexity/edge-concavity (vertex polyhedral) │ αBB underestimators (univariate quadratics) │ Term-specific underestimators (Table 1) │ ▼ [3. Branch-and-Cut Global Optimization] │ Generate tight convex underestimators │ Separating hyperplanes / cutting planes │ Bound variables → branch on search space │ Find feasible solutions (CONOPT/SNOPT) │ ▼ Global Optimum (or ε-optimal certificate)

Term 继承体系（面向对象设计）

ANTIGONE 的 C++ 实现基于一个精心设计的类继承树：

Term Type数学形式凸化策略
Bilinear$x_1 \cdot x_2$McCormick Hull, Outer approximation
Multivariate Signomial$x_1^{a_1} \cdot x_2^{a_2} \cdots$Edge-Concave, Exponential transformation, Fractional
Exponential$e^{a \cdot x + b}$Secant line, Outer approximation
Logarithmic$\log(a \cdot x + b)$Secant line, Outer approximation
Absolute Value$|a \cdot x + b|$Equivalent MILP representation
Composite (Exp/Frac/Log)$(a_1x+b_1) \cdot e^{a_2x+b_2}$, etc.Secant line, Outer approximation

每种 Term 都「知道」自己的：参与变量、凸性区域、偏导数、对应的 underestimator。多态性让添加新 term 类型零改动 branch-and-cut 代码。

特殊结构利用

关键结果

2,571 问题的全面 Benchmark

ANTIGONE 1.1 与 BARON 12.7.3、Couenne 0.4、LINDO 8.0、SCIP 3.0 在 GAMS 24.2.1 上对比。2,112 个含非凸分量的问题上，ANTIGONE 和 BARON 在整体性能曲线上并驾齐驱，明显领先于其他求解器。

测试集问题数ANTIGONE 优势
minlp.org115工业相关问题上特别强，如 ngw-r1-53050 (2.20% gap vs 其他 >50%)
MIQCQP482与 GloMIQO 等价（因为 ANTIGONE 继承了 MIQCQP 框架）
GLOBALLib368竞争力强，如 ex6_2_9 相平衡问题全局最优
MINLPLib249与 BARON 接近
PrincetonLib1,116凸子集上最强（CONOPT 作为 local solver）；非凸子集上 gap 最小

按非线性类型分类

非线性类型问题数ANTIGONE 表现
纯二次1,397与 BARON 并驾齐驱（继承 GloMIQO）
含 signomial759竞争力强（继承 MISO）
含 exp/log/power415改进最大——ANTIGONE 新增的凸化能力
含离散变量528显著优于非 MILP 专用求解器

评价

⚖️ ANTIGONE 是全局 MINLP 求解器设计的里程碑——不是因为某个单一算法突破，而是因为它展示了如何将多个 specialized 框架（MIQCQP, MISO）统一到一个可扩展的面向对象架构中。这个设计哲学影响了后续所有全局求解器的开发。

亮点：Term-based 面向对象架构（可扩展性极强）、2,571 问题的全面 benchmark（2014 年最大规模）、MIQCQP + MISO 统一框架、Flatten 操作减少辅助变量。

局限：2014 年的 benchmark（现已过时）、不支持 trigonometric/errorf 函数、不做函数组合的凸性检测、依赖 GAMS 接口。

博导审稿

🎓 「这篇是 Floudas 组的经典工作。」

——一位带了 20 年全局优化方向研究生的博导

选题眼光
统一 MIQCQP 和 MISO 框架是自然且必要的下一步——两个框架都是 Floudas 组自己的前期工作。选题不是「发现新问题」而是「解决自己制造的整合需求」，但这种整合本身就有巨大价值。
方法成熟度
Term-based 面向对象架构是真正的软件工程贡献。大多数优化论文只关心算法，ANTIGONE 同时展示了如何把算法组织成可维护、可扩展的代码。C++ 继承体系的设计（Fig. 2）是全文最有价值的图。Flatten 操作（Eq. 1）简洁优雅。
实验诚意
2,571 问题在 2014 年是最大规模的全局优化 benchmark。Performance profile 方法论正确（Dolan-Moré）。按问题类型分类（Fig. 3-16）让读者能精确判断 ANTIGONE 在哪些问题上强/弱。缺点：没有与 GloMIQO/MISO 的直接对比来量化统一框架的 overhead。
影响力预判（实际已验证）
截至 2026 年已被引用 700+ 次。ANTIGONE 成为 GAMS 标配求解器之一。Term-based 架构被后续求解器（包括 BARON 的更新版本）借鉴。这篇论文证明了全局优化求解器可以像编译器一样模块化设计。
📋 Strong Accept（经典论文）
Term-based 面向对象架构是全局优化求解器设计的 paradigm shift。2,571 问题的 benchmark 在 2014 年无人能及。这篇论文的价值不会随时间递减——它定义了一种设计哲学。

一句话总结

ANTIGONE 将 MIQCQP 和 MISO 两个全局优化框架统一到一个 term-based 面向对象架构中，通过多态的 underestimator 继承体系实现可扩展的非凸 MINLP 全局优化，在 2,571 个标准问题上与 BARON 并驾齐驱。