SBB 求解器 — 基于分支定界法的 MINLP 求解器

SBB（Simple Branch and Bound）是 GAMS 中用于求解混合整数非线性规划（MINLP）问题的求解器，基于标准的分支定界（Branch and Bound）算法框架，能够高效处理同时包含整数变量和非线性约束的复杂优化问题。

SBB 求解器在分支定界框架下，通过在每个分支节点上求解 NLP 子问题（放松整数约束后的连续非线性规划）来推进搜索过程。它支持多种 NLP 求解器作为子求解器，包括 CONOPT、MINOS 和 SNOPT，用户可根据问题特性灵活选择最合适的求解方案。

SBB 广泛应用于过程工程、能源系统优化、供应链管理、工程设计等领域的 MINLP 问题求解，是 GAMS 中解决混合整数非线性优化问题的可靠工具。

1. Introduction（简介）

SBB 是 GAMS 中最早推出的 MINLP 求解器之一，其核心算法为经典的分支定界法（Branch and Bound，简称 B&B）。与 DICOPT 等基于外逼近法的求解器不同，SBB 采用直接枚举整数解空间的搜索方式，通过系统性地分支和剪枝操作找到最优解。

SBB 适用于求解以下类型的 MINLP 问题：

凸 MINLP 问题：目标函数和约束均为凸函数时，SBB 可保证找到全局最优解。
非凸 MINLP 问题：SBB 采用局部 NLP 求解器求解子问题，适用于非凸问题的局部优化。
具有 0-1 变量的问题：SBB 对二元变量问题具有较高的求解效率。
具有一般整数变量的问题：支持任意整数变量的分支操作。

SBB 的主算法流程如下：

初始化：求解 NLP 松弛问题（放松所有整数约束），若无可行解则问题不可行；若松弛解中整数变量均为整数，则直接得到最优解。
分支：选择一个不满足整数条件的变量进行分支，生成两个子节点（上取整和下取整）。
定界：对每个子节点求解相应的 NLP 子问题，获得该节点的目标函数值作为下界（最小化问题）。
剪枝：若某节点的下界超过当前最优上界，或其 NLP 子问题不可行，则剪去该分支。
迭代：重复步骤 2-4，直到所有分支均被处理或搜索完毕。

2. Branch and Bound（分支定界算法说明）

SBB 的分支定界算法是其核心计算框架。本节详细介绍算法的各个关键环节。

2.1 算法框架

SBB 的分支定界算法采用树形搜索结构，树的每个节点代表一个 NLP 子问题。根节点为原始问题放松整数约束后的 NLP 问题。每层分支将当前节点分裂为两个子节点，分别对分支变量施加额外的上界或下界约束。

2.2 节点选择策略

SBB 提供多种节点选择策略，用于决定下一个需要处理的节点：

Depth First（深度优先）：优先搜索深度最大的节点，有助于快速找到可行解，建立初始上界。
Best Bound（最佳界限优先）：优先选择下界最小的节点（最小化问题），有助于减少搜索树规模。
Mixed（混合策略）：在搜索前期采用深度优先快速寻找可行解，后期切换至最佳界限优先策略以证明最优性。

2.3 分支变量选择

分支变量的选择对算法效率有显著影响。SBB 支持以下分支策略：

Most Infeasible（最不可行性）：选择与整数值偏离最大的变量进行分支。
Pseudo Costs（伪费用）：基于历史分支信息估算分支收益，选择预期改进最大的变量。
Strong Branching（强分支）：对候选变量进行预分支评估，选择效果最优的变量。

2.4 NLP 子问题求解

在每个节点上，SBB 需要求解一个 NLP 子问题。子问题的求解方式和求解器选择对整体性能影响重大：

子求解器选择：可通过 option 语句指定 NLP 子求解器，如 CONOPT、MINOS、SNOPT。
热启动：SBB 支持利用父节点的求解信息作为子节点的初始点，减少 NLP 求解迭代次数。
预求解：在分支前对问题进行预处理，识别冗余约束、固定变量、简化问题规模。

3. Pseudo Costs（伪费用分支策略）

伪费用（Pseudo Costs）是 SBB 中一种重要的分支变量选择策略。该策略通过记录历史分支信息，估算每个整数变量在分支后可能产生的目标函数变化，从而选择预期效果最优的分支变量。

3.1 基本原理

伪费用为每个整数变量维护两组统计数据：向上分支和向下分支的单位费用估计值。当变量 x_j 在第 k 次被选为分支变量时，系统记录上取整和下取整后的目标函数变化量，并更新对应的伪费用值：

向上伪费用 P⁺_j：变量向上取整后目标函数的单位变化量。
向下伪费用 P^-_j：变量向下取整后目标函数的单位变化量。

3.2 收益估计

对于当前处于松弛解的变量 x_j，其分支收益的估计值按下式计算：

Score_j = max(P⁺_j · frac_j, P^-_j · (1−frac_j))

其中 frac_j 为变量的分数部分。得分越高的变量被认为分支收益越大，优先选择。

3.3 自适应更新

SBB 的伪费用策略具有自适应性：在求解过程中，随着更多分支信息的积累，伪费用的估计值会越来越准确，分支决策的质量也随之提升。初期缺乏历史数据时，SBB 会退化为最不可行性分支作为默认策略，待积累足够数据后再切换到伪费用策略。

4. Options（求解器选项）

SBB 提供了丰富的求解器选项，帮助用户根据问题特性调整求解行为。下表列出主要的控制参数：

选项名称	默认值	说明
ResLim	1000	求解时间限制（秒）
IterLim	2000000	总迭代次数限制
NodeLim	10000000	最大分支节点数限制
OptCA	0	绝对最优性间隙容差
OptCR	0.1	相对最优性间隙容差（默认 10%）
NlpSolver	CONOPT	指定 NLP 子求解器（CONOPT / MINOS / SNOPT）
NodeSel	1	节点选择策略：1=深度优先，2=最佳界限优先，3=混合策略
BranchSel	2	分支变量选择策略：1=最不可行性，2=伪费用，3=强分支
NumOffiles	0	工作文件数量（用于保存中间 NLP 子问题）
PseudoCostUp	0.1	初始向上伪费用值
PseudoCostDown	0.1	初始向下伪费用值
IntSolver	—	指定整数求解引擎（一般为 SBB 自身）

选项可通过 GAMS 的 option 语句设置，例如：

option NLP = conopt;
option optcr = 0.05;
option reslim = 3600;
option nodeLim = 500000;
SBB.optFile = 1;
$onecho > sbb.opt
NodeSel 3
BranchSel 2
PseudoCostUp 0.2
PseudoCostDown 0.2
$offecho

5. Log File（日志文件解读）

SBB 在求解过程中会输出详细日志，帮助用户了解求解进度和问题特性。以下是一个典型的日志示例及解读：

5.1 日志示例

--- SBB reading parameter(s)
--- SBB started solving
--- NLP Solver CONOPT
--- SBB: Node 0  Depth 0  Obj 125.34  Best  +inf  Gap  Inf
--- SBB: Node 1  Depth 1  Obj 128.50  Best  +inf  Gap  Inf
--- SBB: Node 3  Depth 2  Obj 130.20  Best  135.80 Gap  4.12%
--- SBB: Node 7  Depth 3  Obj 132.10  Best  135.80 Gap  2.79%
--- SBB: Node 15 Depth 4  Obj 135.80  Best  135.80 Gap  0.00%
--- SBB: Search Completed - Best 135.80
--- SBB: 15 nodes processed

5.2 字段说明

字段	说明
Node	当前处理的节点编号
Depth	节点在搜索树中的深度
Obj	当前节点的 NLP 子问题目标函数值
Best	当前找到的最优可行解目标值（上界）
Gap	最优性间隙：(Best − Obj) / Best × 100%

5.3 终止状态解读

Search Completed：搜索完成，所有节点已处理完毕，得到全局最优解。
Terminated due to node limit：达到节点数上限，当前解可能不是全局最优。
Terminated due to resource limit：达到时间限制，当前解可能不是全局最优。
Infeasible：问题不可行，无任何可行解存在。
Unbounded：问题无界。

6. Comparison with DICOPT（与 DICOPT 的比较）

DICOPT 是 GAMS 中另一款常用的 MINLP 求解器，基于外逼近法（Outer Approximation）和等式松弛法（Equality Relaxation）。SBB 和 DICOPT 具有不同的算法特点，适合不同类型的问题：

特性	SBB	DICOPT
算法基础	分支定界法（B&B）	外逼近法（OA）
整数变量处理	通过分支操作直接枚举	通过交替求解 MILP 主问题和 NLP 子问题
凸问题适用性	可保证全局最优	可保证全局最优
非凸问题适用性	仅保证局部最优	仅保证局部最优
求解速度	整数变量较多时节点数可能爆炸	通常较快，适合大规模整数变量
非线性强度	每次求解完整的 NLP 子问题，适合高度非线性问题	MILP 主问题逼近非线性，适合非线性程度适中的问题
热启动能力	支持 NLP 子问题热启动	支持 NLP 子问题热启动
适用场景	整数变量较少（一般小于 50）、非线性较强的问题	整数变量较多、非线性中等、凸性较好的问题

6.1 选型建议

若问题的整数变量数量较少（≤ 30~50），且非线性程度较高，推荐优先尝试 SBB。
若问题的整数变量数量较多，且非线性程度适中，推荐优先尝试 DICOPT。
对于关键问题的求解，建议同时尝试 SBB 和 DICOPT，对比结果以获得更可靠的解。
对于凸 MINLP 问题，SBB 和 DICOPT 均可保证全局最优性，选择依据主要是求解效率。

在线留言

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

联系我们
	微信公众号	咨询微信	企业店铺
400-621-1085
（节假日期间办公室座机如无人接听，请选择其他联系方式，感谢理解！祝您节日快乐！）