介绍

分支缩减优化导航器（BARON，Branch-And-Reduce Optimization Navigator）是 GAMS 的一个求解器，用于非线性规划（NLP）和混合整数非线性规划（MINLP）的全局求解。

传统的 NLP 和 MINLP 算法仅在某些凸性假设下才能保证收敛，而 BARON 实现了分支定界类型的确定性全局优化算法，在相当一般的假设下保证提供全局最优解。这些假设包括对要求解的 NLP 或 MINLP 中非线性表达式存在有限的下界和上界。

BARON 实现了分支定界类型的算法，并增强了多种约束传播、区间分析和对偶技术，用于在算法过程中缩小变量的范围。通过扩大可行区域和/或低估目标函数来构建严格的松弛。

BARON 软件的部分内容是在伊利诺伊大学厄巴纳-香槟分校创建的。该软件实现的算法、其背后的理论基础以及一些相关应用（部分）在以下文献中描述：[157, 50, 158, ...]。

许可和软件要求

要使用 GAMS/BARON，用户需要拥有 GAMS/BARON 许可证。BARON 附带多个嵌入式 LP/MIP/QP 和 NLP 求解器（CBC；IPOPT、FilterSD、FilterSQP）。此外，GAMS/BARON 用户可以通过访问 CPLEX 和 XPRESS 来加速收敛，以求解 BARON 的 LP/MIP/QP 子问题，以及使用 MINOS、SNOPT 和任何 GAMS NLP 求解器（如 CONOPT）来求解 BARON 的 NLP 子问题。这些求解器需要单独向 GAMS 获取许可。

默认情况下，GAMS/BARON 将尝试使用 CPLEX 作为 LP 求解器，并自动选择 NLP 求解器。用户可以使用选项 LPSol 和 NLPSol 分别指定 LP/MIP/QP 和 NLP 求解器。如果用户没有指定求解器的许可证，BARON 将自动选择一个已获许可的求解器，并在没有其他 LP/MIP 和 NLP 求解器可用时分别默认使用 CLP/CBC 和 IPOPT。通过将 DoLocal 和 NumLoc 设置为 0，可以在没有本地 NLP 求解器的情况下使用 BARON。

运行 GAMS/BARON

BARON 能够求解以下类型的模型：LP、MIP、RMIP、NLP、DNLP、RMINLP 和 MINLP。如果 BARON 未被指定为这些模型的默认求解器，可以通过在求解语句之前发出以下命令来调用它：

option <modeltype>=baron;

其中 <modeltype> 代表 LP、MIP、RMIP、QCP、MIQCP、RMIQCP、CNS、NLP、DNLP、MINLP 或 RMINLP。

模型要求

为了实现全局最优的收敛，可能需要额外的模型约束。这些额外约束可以加快求解器速度并提高成功概率。

变量和表达式界限

要求解的数学规划中的所有非线性表达式必须有下界和/或上界。用户必须为所有问题变量提供有限的下界和上界。请注意，仅提供变量的有限界限可能不足以保证模型中出现的非线性表达式的有限界限。

例如，考虑项 1/x，其中 x ∈ [0,1]，该变量具有有限界限，但表达式是无界的。提供能够保证问题函数具有有限值的问题变量界限非常重要。如果用户模型没有包含能保证所有非线性表达式具有有限值的变量界限，BARON 将尝试从问题约束中推断适当的界限。如果此步骤失败，则不能保证所提供解的全局最优性。有时，由于缺乏界限，无法构建数值稳定的下界问题，此时 BARON 可能会终止。

关于如何指定变量界限，请参见BARON 特性一节。

允许的非线性函数

除了乘法和除法之外，GAMS/BARON 还可以处理涉及 exp(x)、ln(x)、x^α（α 为实数）、β^x（β 为实数）、x^y 和 |x| 的非线性函数。目前不支持其他函数，包括三角函数 sin(x)、cos(x) 等。

BARON 输出

BARON 日志输出

下面的日志输出是使用 GAMS 模型库中的 MINLP 模型 gear.gms，设置绝对和相对最优容差为 1e-6 获得的。

===========================================================================
 BARON version 24.9.12. Built: LNX-64 Thu Sep 12 14:58:30 EDT 2024

 BARON is a product of The Optimization Firm.
 For information on BARON, see https://minlp.com/about-baron

 If you publish work using this software, please cite publications from
 https://minlp.com/baron-publications, such as:

 Khajavirad, A. and N. V. Sahinidis,
 A hybrid LP/NLP paradigm for global optimization relaxations,
 Mathematical Programming Computation, 10, 383-421, 2018.
===========================================================================
 This BARON run may utilize the following subsolver(s)
 For LP/MIP/QP: CLP/CBC, ILOG CPLEX
 For NLP: MINOS, SNOPT, External NLP, IPOPT, FILTERSQP
===========================================================================
 Starting solution is feasible with a value of   36.1768
 Doing local search
 Solving bounding LP
 Starting multi-start local search
 Preprocessing found feasible solution with value 1.02321
 Preprocessing found feasible solution with value 1.00014
 Done with local search
===========================================================================
  Iteration       Time (s)     Mem   Lower bound     Upper bound   Progress
          1           0.04    27MB     1.00000         1.00014        NA
 *         5           0.05    27MB     1.00000         1.00006        0.55%
 *         6           0.06    86MB     1.00000         1.00002        1.64%
 *         7           0.06    86MB     1.00000         1.00001        1.64%
          7           0.06    86MB     1.00001         1.00001      100.00%

                          *** Normal completion ***

 Wall clock time:                     0.07
 Total CPU time used:                 0.06

 Total no. of BaR iterations:       7
 Best solution found at node:       7
 Max. no. of nodes in memory:       4

 All done
===========================================================================

求解器首先测试用户提供的初始点的可行性。该点被发现可行，目标函数值为 36.1768。BARON 随后执行随机局部搜索过程，最终找到目标值为 1.00014 的可行解。然后，迭代日志每 1,000,000 次分支定界迭代和每 30 秒提供一次信息。此外，在根节点结束时、当前最优解的值改善至少 10^-5 时以及搜索结束时也会打印信息。一行第一个位置出现星号（*）表示找到了更好的可行解，将先前已知最佳解的值改善了至少 10^-5。日志字段包括迭代次数、已用时间、BARON 消耗的内存量、问题的下界和上界，以及已完成搜索百分比的大致估计。日志输出字段总结如下：

字段	说明
`Itn. no.`	当前迭代次数。迭代次数后面的加号（`+`）表示报告时正在求解对应节点的探测（而非松弛）子问题。
`Time`	当前计算时间（秒）。单线程作业报告 CPU 时间，多线程作业报告墙钟时间。
`Mem`	BARON 数据结构使用的内存量。这不包括外部子求解器（如 CPLEX）在 BARON 调用之间可能分配/释放的内存。
`Lower Bound`	模型的当前下界。
`Upper Bound`	模型的当前上界。
`Progress`	已完成分支定界搜索百分比的大致估计。该估计在早期迭代中可能不准确，且对于可行性问题不可用。

终止消息、模型和求解器状态

GAMS 检查 BARON 返回的模型和求解器状态。下表描述了模型状态：

GAMS 模型状态

模型状态	说明
`1` 最优	BARON 报告已找到全局最优解。当然，这仅适用于已建立有效下界的问题。
`2` 局部最优	BARON 的初始化或局部搜索部分找到了一个可能不是全局最优的解。这发生在用户将 MaxTime 设置为 0 时，或由于数值困难或耗尽内存而导致 BARON 的全局搜索异常终止且无法证明最优性时。
`4` 不可行	BARON 已证明模型不可行。
`5` 无界	BARON 已证明模型无界。
`6` 无界-不可行	BARON 确定模型可能是无界或不可行的。
`7` 完成	BARON 已完成搜索，可能找到了一个可行解，但既不能证明最优性也不能证明不可行性。
`8` 求解器错误	用户提供了一个错误的选项。
`9` 求解器错误	发生了某种错误。
`12` 求解中出错	发生了内部错误。
`13` 求解器错误	求解器未返回解。

BARON 求解器状态

求解器状态	说明
`1` 正常完成	这是最理想的终止状态。在这种情况下，问题已在容差范围内求解。如果 BARON 返回代码 `-3`，则不存在可行解。
`2` 迭代中断	已超过允许的最大迭代次数。
`3` 资源中断	已超过允许的最大 CPU 时间。
`4` 终止，但未求解	求解器因某种原因无法开始求解。
`5` 评估错误极限	已超过函数或导数评估次数限制。
`6` 容量	已达到 BARON 树中允许的最大节点数。
`7` 用户中断	用户中断了运行。
`8` 设置错误	选项文件中提供了错误的 BARON 选项。
`9` 读取错误	读取选项文件时出错。
`10` 许可错误	BARON 许可证有问题。
`11` 出价错误	出价环境出错。
`12` 内存不足	内存不足以设置或处理问题。
`13` 语法错误	选项文件的语法无效。
`14` 数值问题	问题是数值敏感的。

此外，BARON 在终止时会报告 nodeopt，指示找到最佳可行解的节点（在 BARON 的分支定界树中的节点号）：

-1：最佳解在预处理期间找到

i：最佳解在树的第 i 个节点中找到

除了报告 nodeopt 之外，BARON 在终止时还会发出以下语句之一：

*** 正常完成 ***

这是最理想的终止状态。在这种情况下，问题已在容差范围内求解。如果 BARON 返回代码 -3，则不存在可行解。

*** 启发式终止 ***

虽然在这种情况下不保证全局最优性，但当 (a) 已找到可行解且 (b) 下界/上界的进展满足用户通过 BARON 的 DeltaTerm 选项设置的启发式终止准则时，BARON 会以此消息终止。

*** 用户未提供适当的变量界限 ***

用户需要阅读 BARON 输出（在临时目录中的文件 sum.dat 中，使用 GAMS 参数 keep=1 防止此目录被自动删除）以获取缺失界限的变量和表达式的指示。应修改模型以为变量和中间表达式提供界限，使 BARON 能够构建可靠的松弛。尽管松驰界限会打印在屏幕上以让用户了解收敛情况，但这些界限可能对当前问题无效。此消息后跟以下两个消息之一：

*** 因此不保证不可行性 ***

这表明，由于缺少界限，未找到可行解，但未证明模型不可行。

*** 因此不保证全局性 ***

这表明，由于缺少界限，找到的可行解的全局最优性未得到证明。

*** 达到内存中允许的最大节点数 ***

用户需要增加计算机的物理内存或更改算法选项（如分支和节点选择规则），以减少搜索树的大小和存储所需的内存。

*** 达到允许的最大 BaR 迭代次数 ***

用户需要增加允许的最大迭代次数。BARON 选项为 MaxIter。在 GAMS 中指定此项，可以使用 NodLim 选项。我们注意到 BARON 选项 MaxIter 会覆盖 NodLim。

*** 超过允许的最大 CPU 时间 ***

用户需要增加允许的最大 CPU 时间。BARON 选项为 MaxTime。在 GAMS 中指定此项，可以使用 ResLim 选项。我们注意到 BARON 选项 MaxTime 会覆盖 ResLim。

*** 问题对数值敏感 ***

BARON 设计为自动处理数值困难的问题。然而，对于某些问题，全局最优对数值敏感。例如，当目标函数值在严格位于可行域之外但在数值容差内仍然可行的点的微小邻域内变化显著时，就会发生这种情况。当 BARON 返回此消息时，报告的 "Best possible" (最佳可能值) 很可能是正确的。

*** 搜索被用户中断 ***

运行被用户中断（Ctrl-C）。

*** 数据结构内存不足 ***

需要更多内存来设置问题数据结构。用户需要增加计算机上可用的物理内存。

BARON 特性

无需初始点

只要用户提供了适当的变量界限，BARON 不需要初始点。BARON 会自动生成起点，并使用多起点局部搜索来寻找好的可行解，以及一个填充函数来寻找代表不同局部极小点的多个解。如果需要，用户仍可以通过标准 GAMS 方法的变量赋值语句提供初始可行点。

寻找若干最优解或所有可行解

将 NumSol 设置为大于 1 的值会生成 BARON 找到的多个最优解。将 FindSol 设置为 1 会输出 BARON 找到的所有整数可行解。

将 BARON 用作多起点启发式求解器

将 MaxTime 设置为 0 仅会触发 BARON 的初始化和局部搜索部分，而没有后续的全局搜索。此选项允许将 BARON 快速用作多起点启发式求解器来寻找好的（但不一定全局最优的）解。

无界问题的系统化处理

当整数变量固定为特定值时，许多 MINLP 可能被证明是无界的。BARON 通过为变量引入大界限以及在求解过程中根据需要自动增加这些界限来系统化处理此类问题。可以通过 InfBnd 选项控制此特性。

不可行问题的系统化处理

BARON 能够通过分析约束的不可行性来识别不可行模型。

互补约束的处理

BARON 可以自动检测并用适当的公式替换互补约束。

并行能力

BARON 可以在多核环境中并行运行。多线程执行可以通过 NumThreads 选项启用。BARON 的并行化策略是在可用的处理器之间分配分支定界搜索树中的节点。以下操作默认是并行的：节点处理（局部搜索、边界收缩、下界求解和边界改进）以及根节点的多起点搜索。

BARON 选项

选项通过 GAMS 的 option 语句传递或使用 baron.opt 选项文件。例如，要将 MaxTime 设置为 100：

option baron="maxtime 100";

要使用选项文件：

$onecho > baron.opt
maxtime 100
$offecho
option baron=baron.opt;

选项摘要

选项	说明	默认值
abs_opt_tol	绝对最优容差	1e-9
rel_opt_tol	相对最优容差	1e-5
maxtime	最大 CPU 时间（秒）	1e10
maxiter	最大迭代次数	1000000
prlevel	日志输出级别（0：无，1：正常，2：详细）	1
prfreq	日志输出频率（每 N 次迭代）	1000
threads	线程数	1
lpsol	LP 求解器选择	自动
nlpsol	NLP 求解器选择	自动

容差选项

选项	说明	默认值
AbsConTol	约束满足的绝对容差	1e-7
AbsObjTol	目标函数的绝对容差	1e-9
RelConTol	约束满足的相对容差	1e-5
RelObjTol	目标函数的相对容差	1e-5
EpsX	变量扰动容差	1e-5
DeltaTerm	终止界限的分数差距	0（关闭）

...

（由于页面内容较长，此处省略了 BARON 选项说明中关于树管理、局部搜索、输出、时间、预处理、松弛、杂项、高级、约束和范围等选项表的完整翻译。更多详细信息请参阅原始 GAMS 文档。）

非 BARON 选项

以下选项由 GAMS 管理，传递给 BARON，但并非 BARON 专有：

选项	说明	备注
optca	绝对最优容差（GAMS optca）	覆盖 AbsObjTol
optcr	相对最优容差（GAMS optcr）	覆盖 RelObjTol
reslim	资源限制（GAMS reslim）	覆盖 MaxTime
nodlim	节点限制（GAMS nodlim）	覆盖 MaxIter
iterlim	迭代限制（GAMS iterlim）	覆盖 MaxIter
domlim	定义域错误限制（GAMS domlim）	-

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

BARON 全局优化求解器

目录

介绍