介绍

ANTIGONE（连续/整数非线性方程全局优化算法，Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations）是一个确定性的通用混合整数非线性全局优化框架 [134, 135, 136, 137, 138]。

MINLP 定义如下：

\[ \begin{array}{rl} \tag{MINLP} \min \; & \phantom{b_m^{\mathrm{LO}} \leq {}} f_0(\boldsymbol{x}, \, \boldsymbol{y}, \, \boldsymbol{z}) \\[8pt] \text{s.t. } & b_m^{\mathrm{LO}} \leq f_m(\boldsymbol{x}, \, \boldsymbol{y}, \, \boldsymbol{z}) \leq b_m^{\mathrm{UP}} \quad \forall \; m \in \{ 1, \, \ldots, \, M \} \\[10pt] & \boldsymbol{x} \in \mathbb{R}^{C}; \; \boldsymbol{y} \in \left\{ 0, \, 1 \right\}^{B}; \; \boldsymbol{z} \in \mathbb{Z}^{I} \\ \end{array} \]

其中 \(C\)、\(B\)、\(I\) 和 \(M\) 分别表示连续变量、二元变量、整数变量和约束的数量。参数向量 \(\boldsymbol{b_m^{\mathrm{LO}}}\) 和 \(\boldsymbol{b_m^{\mathrm{UP}}}\) 是约束的边界。我们假设可以推断出参与非线性项 \(f_m\) 的变量的有限边界 \(\left[ x_i^L, \, x_i^U \right]\)，并且 \(f_m\) 在 \(\boldsymbol{x}\) 上的像是有界的。\(f_0(\boldsymbol{x}, \, \boldsymbol{y}, \, \boldsymbol{z})\) 和 \(f_m(\boldsymbol{x}, \, \boldsymbol{y}, \, \boldsymbol{z})\) 的典型表达式为：

\[ \begin{split} f_m(\boldsymbol{x}, \, \boldsymbol{y}, \, \boldsymbol{z}) = c_m & + a_m^T \, \left[ \boldsymbol{x}; \; \boldsymbol{y}; \; \boldsymbol{z} \right] + \left[ \boldsymbol{x}; \; \boldsymbol{y}; \; \boldsymbol{z} \right]^T \, Q_m \, \left[ \boldsymbol{x}; \; \boldsymbol{y}; \; \boldsymbol{z} \right] \\ & + \sum\limits_{s = 1}^{S_m} c_{s_m} \cdot \prod\limits_{c = 1}^C x_c^{p_{s_m, \, c}} + \sum\limits_{e = 1}^{E_m} c_{e_m} \cdot e^x + \sum\limits_{\ell = 1}^{L_m} c_{\ell_m} \cdot \log x \end{split} \]

其中幂指数 \(p_{s_m, \, c}\) 是常数实数；\(c_m, \, a_m, \, Q_m, \, c_{s_m}, \, c_{e_m}, \, c_{\ell_m}\) 是常数系数；\(S_m\)、\(E_m\)、\(L_m\) 分别是符号项、指数项和对数项的数量。

如下图所示，ANTIGONE 动态响应以利用 (MINLP) 中的特殊结构。ANTIGONE 大致属于分支定界全局优化范畴，因为它：生成并求解非凸 MINLP 的凸松弛（严格限定全局解的范围）；通过局部优化寻找可行解；分而治之地处理可行集，生成一系列收敛到全局最优解的凸松弛 [65, 64]。

给定一个 MINLP 优化问题，ANTIGONE 重构模型，检测重构后的 MINLP 中的特殊结构，求解优化问题，并返回相对于原问题变量的模型

许可和软件要求

使用 GAMS/ANTIGONE 需要：

ANTIGONE 许可证，
CPLEX 许可证，以及
CONOPT 或 SNOPT 许可证。

运行 GAMS/ANTIGONE

GAMS/ANTIGONE 求解：NLP、MINLP、RMINLP、QCP、MIQCP、RMIQCP、CNS。如果 GAMS/ANTIGONE 不是这些模型的默认求解器，可以在 solve 语句之前使用以下命令调用它：

option nlp=antigone, minlp=antigone, rminlp=antigone;

GAMS/ANTIGONE 输出

下面显示的日志输出是使用 MINLPLib 中的 MINLP 模型 cecil_13 生成的。

-------------------------------------------------------------------------------
ANTIGONE: Algorithms for coNTinuous/Integer Global Optimization; Version 1.0

          Ruth Misener and Christodoulos A. Floudas

          Computer-Aided Systems Laboratory (CASL)
          Department of Chemical & Biological Engineering; Princeton University
-------------------------------------------------------------------------------

Before Pre-processing:
          840 Variables
                  660 Continuous
                  180 Binary
          929 Equations

After Pre-processing:
          520 Variables
                  418 Continuous
                  102 Binary
          499 Equations
                  291 Linear
                  208 Nonconvex nonlinear
          232 Nonlinear Terms
                  232 Signomial
          730 Possible Reformulation Linearization Technique (RLT) equations
              34 RLT Equations Added Outright to Formulation

Constituent Libraries:
            CPLEX  Solving relaxations
            CONOPT Finding feasible points
            LAPACK Addressing linear systems
            Boost  Bounding Intervals
 
-------------------------------------------------------------------------------
Time (s) Nodes explored Nodes remaining Best possible   Best found Relative Gap
-------------------------------------------------------------------------------
 
      65              1               1    -1.158e+05   -1.157e+05   +1.032e-03
     134              1               1    -1.157e+05   -1.157e+05   +4.337e-04
     202              1               1    -1.157e+05   -1.157e+05   +4.334e-04
     258              1               1    -1.157e+05   -1.157e+05   +4.140e-06
     Solving MILP relaxation at tree level 0 ----------------------------------
     341              1               1    -1.157e+05   -1.157e+05   +4.091e-06
     413              1               1    -1.157e+05   -1.157e+05   +4.011e-06
     Solving MILP relaxation at tree level 0 ----------------------------------
     483              1               1    -1.157e+05   -1.157e+05   +4.001e-06
     571              1               1    -1.157e+05   -1.157e+05   +3.959e-06
     Solving MILP relaxation at tree level 0 ----------------------------------
     640              1               1    -1.157e+05   -1.157e+05   +3.880e-06
     Solving MILP relaxation at tree level 0 ----------------------------------
     702              1               0    -1.157e+05   -1.157e+05   +1.000e-06
 
-------------------------------------------------------------------------------
Termination Status : Global minimum
Best Feasible Point: -1.156565e+05
Best Possible Point: -1.156566e+05
       Relative Gap: +1.000000e-06
Algorithm analysis :

                  0 Nodes explored
                  0 Nodes remaining

                  0 Maximum tree depth

                183 Cutting Planes (183 Globally Valid)
                        183 Signomial
 
             702.38 Total time (CPU s)
                      0.07 Pre-processing
                    698.56 Solving MILP relaxations
                      0.95 Searching for feasible solutions
                      2.79 Variable bounds tightening
                             2.31 OBBT
                             1.48 FBBT (0.13 EC; 0.92 RLT; 0.00 Factoring)
                      0.00 Branching
                             0.00 Reliability branching
-------------------------------------------------------------------------------

ANTIGONE 选项摘要

常规选项

选项	说明	默认值
abs_opt_tol	绝对终止容忍度	`GAMS optca`
dumpsolutions	用于写入替代解的解决方案索引 gdx 文件名
max_number_nodes	节点限制	`GAMS nodlim`
max_time	资源限制	`GAMS reslim`
readparams	读取 ANTIGONE 语法的辅助选项文件
rel_opt_tol	相对终止容忍度	`GAMS optcr`
trydual	调用 CONOPT 或 SNOPT 生成对偶变量	`5`

求解 MILP 松弛的选项

选项	说明	默认值
cplex_optfile	读取应用于每个 LP 和 MILP 子求解的辅助 GAMS/CPLEX 选项文件
cut_generation_epsilon	分离超平面的绝对违反阈值	`1e-4`
nominal_time_limit	求解 MILP 子问题的标称时间限制	`100`
populate_solution_pool	生成起始点的侧重程度	`3`

寻找可行解的选项

选项	说明	默认值
conopt_optfile	读取应用于每个 NLP 子求解的辅助 GAMS/CONOPT 选项文件
feas_soln_time_limit	NLP 求解的时间限制（秒）	`30`
feas_tolerance	绝对可行性容忍度	`1e-6`
nlp_solver	使用 CONOPT 或 SNOPT 寻找可行解	`conopt`

分支选项

选项	说明	默认值
branching_bounds_push_away	分支距离变量边界的最小比例	`0.1`
branching_weight	在中点和解点的凸组合上进行分支	`0.25`
num_reliability_tests	强分支初始化测试的次数	`8`

定界选项

选项	说明	默认值
fbbt_frequency	可行性基界收紧的频率	`1`
obbt_frequency	最优性基界收紧的频率	`0`

控制台日志选项

选项	说明	默认值
log_interval	日志行之间的求解时间（秒）	`1`
quiet_mode	抑制日志行	`0`

处理特殊结构的选项

选项	说明	默认值
bda_strategy	处理双线性/双线性聚集项的策略	`0`
edge_convex_only	仅对始终边缘凸的项使用凸包络	`0`
implied_bounds	推断隐含约束（0=无，1=使用 gams 方程，2=使用 gams 方程和约束梯度）	`2`
linear_terms_relax	线性项松弛技术（0=MCCormick，1=凸包络）	`0`
propagate_eqs	传播等式约束	`1`
rlt	使用重构线性化技术	`1`
sdp	使用半定规划	`0`

ANTIGONE 选项详细说明

abs_opt_tol （实数）：绝对终止容忍度 ↵

范围：[0, ∞]

默认值：GAMS optca

bda_strategy （整数）：处理双线性/双线性聚集项的策略 ↵

默认值：0

值含义

0 将双线性项和双线性聚集项都松弛为 MILP。

1 仅将双线性聚集项松弛为 MILP。

2 将双线性项和双线性聚集项都保留为 NLP。

branching_bounds_push_away （实数）：分支距离变量边界的最小比例 ↵

范围：[0, 0.5]

默认值：0.1

branching_weight （实数）：在中点和解点的凸组合上进行分支 ↵

权重 0 = 在中点分支；权重 1 = 在解点分支。

范围：[0, 1]

默认值：0.25

conopt_optfile （字符串）：读取应用于每个 NLP 子求解的辅助 GAMS/CONOPT 选项文件 ↵

cplex_optfile （字符串）：读取应用于每个 LP 和 MILP 子求解的辅助 GAMS/CPLEX 选项文件 ↵

cut_generation_epsilon （实数）：分离超平面的绝对违反阈值 ↵

默认值：1e-4

dumpsolutions （字符串）：用于写入替代解的解决方案索引 gdx 文件名 ↵

edge_convex_only （整数）：仅对始终边缘凸的项使用凸包络 ↵

默认值：0

值含义

0 对所有项可能使用凸包络。

1 仅对始终边缘凸的项使用凸包络。

fbbt_frequency （整数）：可行性基界收紧的频率 ↵

在根节点处始终执行 FBBT；在树中每隔 fbbt_frequency 层递归执行。

范围：[0, ∞]

默认值：1

feas_soln_time_limit （实数）：NLP 求解的时间限制（秒） ↵

默认值：30

feas_tolerance （实数）：绝对可行性容忍度 ↵

默认值：1e-6

implied_bounds （整数）：推断隐含约束 ↵

默认值：2

值含义

0 无隐含约束。

1 使用 GAMS 方程推断隐含约束。

2 使用 GAMS 方程和约束梯度推断隐含约束。

linear_terms_relax （整数）：线性项松弛技术 ↵

默认值：0

值含义

0 McCormick 包络。

1 凸包络。

log_interval （实数）：日志行之间的求解时间（秒） ↵

每 log_interval 秒向控制台写入一条日志行。

默认值：1

max_number_nodes （整数）：节点限制 ↵

探索的最大分支定界节点数。

默认值：GAMS nodlim

max_time （实数）：资源限制 ↵

默认值：GAMS reslim

nlp_solver （字符串）：使用 CONOPT 或 SNOPT 寻找可行解 ↵

默认值：conopt

nominal_time_limit （实数）：求解 MILP 子问题的标称时间限制 ↵

默认值：100

num_reliability_tests （整数）：强分支初始化测试的次数 ↵

范围：[0, ∞]

默认值：8

obbt_frequency （整数）：最优性基界收紧的频率 ↵

每 obbt_frequency 个节点执行一次 OBBT。

默认值：0

populate_solution_pool （整数）：生成起始点的侧重程度 ↵

每次 MILP 求解后，ANTIGONE 使用 CPLEX 解池来生成 NLP 求解器的起始点。此选项控制 CPLEX 生成解池的积极程度。

默认值：3

值含义

0 不使用解池。

1 默认 CPLEX 解池设置。

2 适度的 CPLEX 解池侧重。

3 积极的 CPLEX 解池侧重。

propagate_eqs （整数）：传播等式约束 ↵

默认值：1

值含义

0 不传播。

1 传播等式约束。

quiet_mode （整数）：抑制日志行 ↵

默认值：0

值含义

0 正常日志输出。

1 抑制日志行。

readparams （字符串）：读取 ANTIGONE 语法的辅助选项文件 ↵

rel_opt_tol （实数）：相对终止容忍度 ↵

范围：[0, 1]

默认值：GAMS optcr

rlt （整数）：使用重构线性化技术 ↵

默认值：1

值含义

0 不使用 RLT。

1 使用 RLT。

sdp （整数）：使用半定规划 ↵

默认值：0

值含义

0 不使用半定规划。

1 使用半定规划。

trydual （整数）：调用 CONOPT 或 SNOPT 生成对偶变量 ↵

默认值：5

值含义

0 从不调用 NLP 求解器来生成对偶变量。

1 每当 NLP 求解器在节点处找到可行点时，也调用它来生成对偶变量。

2 仅偶数字调用 NLP 求解器来生成对偶变量。

5 仅根节点处调用 NLP 求解器来生成对偶变量。

ANTIGONE 算法特性

模型输入重构

ANTIGONE 首先将 GAMS 模型转换为以下形式的简化表示：

单一类型方程；
从非线性表达式中分解出的线性项；
双向不等式约束；
符号、指数和对数项被分解为辅助变量；
等式约束（如果可能）被传播到目标函数中。

特殊结构识别

在重构阶段之后，ANTIGONE 分析非线性表达式中的项。

凸性/凹性使得可以轻松生成切割平面。
边缘凸性/边缘凹性意味着一个顶点多面体包络；ANTIGONE 通过简单的区间算术测试，将项和多项表达式标记为始终/有时/从不边缘凸/边缘凹 [133, 177, 175, 176]。
\(\alpha\textbf{BB}\) 下估计器使用单变量二次项对表达式进行凸化 [4, 5, 9, 67, 128]；ANTIGONE 使用 \(\alpha\)BB 来松弛双线性项的聚集。
特定项下估计器如下图所示；其实现基于公开文献中的工作 [51, 52, 66, 76, 118, 125, 123, 124, 129, 133, 134, 146, 177, 175, 178]。

基类 Term 的继承结构

分支定界全局优化

在重构和特殊结构检测阶段之后，ANTIGONE 启动分支切割全局优化算法，该算法生成紧的凸下估计、动态生成分离超平面、对变量进行定界 [5, 9, 4, 10, 17, 48, 49, 116, 157, 158, 171, 172, 191]；在搜索空间上进行分支 [1, 17]，并寻找可行解。

尊敬的客户朋友，如您有任何意见建议，请通过下表反馈给我们，我们会尽快与您联系。

ANTIGONE 全局优化求解器

目录

介绍