1. 从一个"卡脖子"的优化问题说起
第一次碰到含分式的非线性规划问题，是在做一个生产排程的小工具时。目标函数里出现了"产出/投入"这种比值形式，约束里也有"库存周转率"这类分式表达。当时我的第一反应是用现成的求解器直接怼，结果发现两个问题：一是通用非线性求解器对分式结构非常不友好，动不动就陷入局部最优；二是分式让整个可行域的几何形态变得很"扭曲"，梯度类方法经常在边界附近来回震荡。
后来查了不少资料，才意识到这类问题有个专门的名字——分式规划（Fractional Programming），而含分式的非线性规划（Nonlinear Programming with Fractional Terms）在运筹学里是一个有成熟理论体系的分支。它的核心难点在于：分式项既不是凸的也不是凹的，直接套用凸优化那套工具会失效。但如果能把它转化成等价的线性或凸形式，问题就变得可解了。
这篇博文要聊的，就是怎么用Outer Approximation（外逼近）配合Branch-and-cut（分支切割）来求解这类问题，以及怎么用 Java 把它落地实现。内容会覆盖算法原理、关键推导、Java 工程结构、核心代码、参数调优和踩坑记录。适合有一定运筹优化基础、想自己动手实现求解器的开发者，也适合做排程、选址、资源分配这类业务、被分式目标函数折磨过的工程师。
我尽量把数学推导讲得"能看懂"，把代码讲得"能抄走"，把坑讲得"能避开"。
2. 问题建模与算法选型的底层逻辑
2.1 含分式非线性规划到底长什么样
先把问题形式化。一个典型的含分式非线性规划可以写成：
min f(x) = Σ_i (p_i(x) / q_i(x)) + g(x) s.t. h_j(x) ≤ 0, j = 1,...,m x ∈ X其中p_i(x)和q_i(x)是仿射或凸函数，q_i(x) > 0（保证分式有意义），g(x)是普通凸函数，X是一个紧致的多面体（比如箱式约束）。约束h_j(x)可以是线性的，也可以是非线性的。
为什么分式这么难搞？用一个生活化的类比：普通凸函数像一个碗，你从任何方向往下走都能到碗底；而分式函数像一个"马鞍面"或者"波浪面"，有多个局部低谷，梯度下降很容易掉进其中一个就出不来了。更麻烦的是，分式的可行域边界往往不是直线，而是曲线，这直接破坏了线性规划那套单纯形法的适用前提。
2.2 为什么选 Outer Approximation 而不是别的
求解这类问题，常见思路有几条：
| 方法 | 核心思想 | 适用场景 | 主要缺陷 |
|---|---|---|---|
| 梯度类方法 | 沿梯度方向迭代 | 光滑无约束/简单约束 | 易陷局部最优，对分式不友好 |
| 内点法 | 障碍函数逼近 | 凸问题 | 非凸分式失效 |
| 分支定界 | 空间划分+界估计 | 混合整数 | 需要好的松弛 |
| Outer Approximation | 用切平面从外部逼近 | 凸/可凸化问题 | 需要凸性保证 |
| Branch-and-cut | 分支+割平面结合 | 非凸/整数 | 实现复杂 |
我最终选Outer Approximation + Branch-and-cut的组合，理由有三条。
第一，Outer Approximation 的本质是"用一系列切平面从外部逼近可行域和目标函数"，它天然适合处理那些"局部看起来不像凸、但整体可以凸化"的问题。分式项通过 Charnes-Cooper 变换或者 Dinkelbach 方法，可以转化成等价的凸形式，这就给外逼近提供了理论基础。
第二，Branch-and-cut 解决了外逼近的一个致命弱点：外逼近得到的松弛问题可能给出"过于乐观"的下界，导致搜索空间剪枝不干净。分支操作把空间切开，切割平面进一步收紧松弛，两者配合能把下界逐步抬高到真实最优值附近。
第三，这套方法在工程上可落地。它不需要求解器内部的黑魔法，核心就是"解线性松弛 + 加割 + 分支"的循环，用 Java 配合一个 LP 求解器（比如 Apache Commons Math 或者自己写单纯形）就能跑起来。
2.3 分式凸化的关键推导
这是整篇内容最核心的数学部分，我尽量讲透。
考虑单个分式项p(x)/q(x)，其中p是凸函数，q是凹函数且q(x) > 0。这个比值本身既不是凸也不是凹。但如果我们引入辅助变量做变换，情况就不一样了。
Charnes-Cooper 变换的思路是：令t = 1/q(x)，y = x/q(x)，则p(x)/q(x) = p(y/t) · t。在q(x) > 0的条件下，这个变换把分式问题转化成一个关于(y, t)的凸问题（前提是p凸、q凹）。变换后的约束变成线性的，目标函数变成凸的。
Dinkelbach 方法则是另一种思路：把分式目标min p(x)/q(x)转化成参数化问题min p(x) - λ·q(x)，其中λ是当前最优比值的估计。迭代更新λ，直到收敛。这个方法的优点是每次迭代只需求解一个凸子问题，缺点是收敛速度依赖初始λ的选取。
我在实现里用的是 Charnes-Cooper 变换为主、Dinkelbach 作为加速手段的混合策略。原因是：Charnes-Cooper 一次性把问题凸化，适合外逼近框架；Dinkelbach 在迭代后期能快速收敛，减少割平面的数量。
注意：Charnes-Cooper 变换要求
q(x) > 0在整个可行域上成立。如果这个条件不满足，需要先做变量替换或者加约束把q(x)的下界抬到正数。这一点在实际建模时极容易被忽略，导致变换后的问题和原问题不等价。
3. 算法框架的完整拆解
3.1 Outer Approximation 的工作机制
Outer Approximation 的核心思想可以用一句话概括：用一个不断扩大的多面体从外部逼近真实的可行域和目标函数，每次求解这个多面体上的线性（或凸）松弛，得到一个下界，然后根据松弛解生成新的割平面，收紧多面体。
具体到我们的问题，流程是这样的：
- 初始化：把原问题松弛成一个线性规划（LP），得到初始下界
LB和一个松弛解x_relax。 - 检查
x_relax是否可行（满足所有非线性约束）。如果可行，更新上界UB。 - 如果不可行，在
x_relax处对违反的约束生成切平面（割），加入松弛问题。 - 重新求解 LP，得到新的下界。
- 重复 2-4，直到
UB - LB < ε。
这里的"切平面"是怎么来的？对于凸约束h(x) ≤ 0，在点x_k处的一阶泰勒展开给出h(x_k) + ∇h(x_k)^T (x - x_k) ≤ 0，这是一个线性不等式，就是割平面。对于分式项，经过 Charnes-Cooper 变换后，同样可以生成线性割。
3.2 Branch-and-cut 如何补足外逼近
纯外逼近有个问题：如果松弛问题的可行域比真实可行域大很多，下界会非常松，收敛慢。Branch-and-cut 通过两个操作加速：
分支（Branch）：当松弛解x_relax中某个变量取值"模棱两可"（比如整数变量取了小数，或者连续变量落在两个割平面之间的"缝隙"里），就把这个变量的取值范围一分为二，形成两个子问题。每个子问题的可行域更小，下界更紧。
切割（Cut）：除了外逼近生成的切平面，还可以加入 Gomory 割、覆盖割等通用割平面，进一步收紧松弛。对于分式问题，我额外加了一类"分式割"——利用分式项在边界处的特殊结构生成的割。
两者的配合逻辑是：分支负责"分而治之"，切割负责"局部收紧"。在搜索树上，每个节点都维护自己的割平面池，子节点继承父节点的割，再根据自身松弛解生成新割。
3.3 搜索树的管理策略
搜索树的管理直接决定算法效率。我用的是最佳优先搜索（Best-First Search），优先展开下界最小的节点。理由是：分式问题的下界质量差异很大，最佳优先能更快找到好的上界，从而更早剪枝。
节点数据结构包含：
- 变量范围（上下界）
- 当前 LP 松弛解
- 当前下界
- 割平面列表
- 父节点引用
- 分支深度
剪枝规则有三条：
- 如果节点下界 ≥ 当前全局上界，剪掉。
- 如果节点 LP 不可行，剪掉。
- 如果节点松弛解已经是整数且可行，更新上界，剪掉。
实操心得：搜索树的节点数会爆炸式增长，必须设置节点数上限和深度上限。我一般把节点上限设为 10000，深度上限设为 50。超过就返回当前最优解，并标记为"未证明最优"。
3.4 收敛性保证与终止条件
理论上，Branch-and-cut 在有限步内收敛到全局最优（对于有界问题）。实际实现中，终止条件有三个：
UB - LB < ε（相对间隙小于阈值，比如 1e-4）- 节点数超过上限
- 运行时间超过上限
我建议同时设置这三个条件，因为分式问题的下界收敛可能很慢，单靠间隙判断会跑很久。
4. Java 实现的工程结构与核心代码
4.1 整体模块划分
Java 实现我分成五个模块：
fractional-nlp/ ├── model/ # 问题建模：变量、约束、目标函数 ├── transform/ # Charnes-Cooper 变换、Dinkelbach 迭代 ├── relaxation/ # LP 松弛求解器封装 ├── cut/ # 割平面生成与管理 ├── branch/ # 分支策略与搜索树 └── solver/ # 主求解循环这样划分的好处是：变换逻辑和求解逻辑解耦，换一种凸化方法（比如从 Charnes-Cooper 换成 Dinkelbach）只需要改transform模块，不影响其他部分。
4.2 问题建模的数据结构
核心类FractionalProblem包含：
public class FractionalProblem { private int numVars; private double[] lowerBounds; private double[] upperBounds; private List<FractionalTerm> fractionalTerms; // 分式项 private List<LinearConstraint> linearConstraints; private List<ConvexConstraint> convexConstraints; private ConvexFunction extraObjective; // g(x) }FractionalTerm表示一个分式项p(x)/q(x)：
public class FractionalTerm { private double[] numeratorCoeffs; // p(x) 的系数 private double numeratorConst; private double[] denominatorCoeffs; // q(x) 的系数 private double denominatorConst; }这里假设p和q都是仿射函数。如果遇到非仿射的p或q，需要先做线性化近似，或者用更复杂的凸化手段。我在实现里只支持仿射分子分母，因为这是工程中最常见的场景。
4.3 Charnes-Cooper 变换的实现
变换的核心代码：
public TransformedProblem charnesCooper(FractionalProblem orig) { int n = orig.getNumVars(); // 新变量: y[0..n-1] = x * t, t = 1/q(x) // 总变量数 n+1 TransformedProblem tp = new TransformedProblem(n + 1); // 目标函数: sum(p_i(y/t) * t) + g(y/t) * t // 由于 p_i 仿射, p_i(y/t)*t = p_i(y) (线性) for (FractionalTerm ft : orig.getFractionalTerms()) { tp.addObjectiveTerm(ft.getNumeratorCoeffs(), ft.getNumeratorConst()); } // 约束: h_j(y/t) * t <= 0 => h_j(y) <= 0 (线性约束不变) // 关键约束: q_i(y/t) * t = 1 => q_i(y) = 1 for (FractionalTerm ft : orig.getFractionalTerms()) { tp.addEqualityConstraint(ft.getDenominatorCoeffs(), ft.getDenominatorConst(), 1.0); } // t > 0 tp.setLowerBound(n, 1e-6); return tp; }这段代码的关键点：变换后t必须严格大于 0，否则分式无意义。我用1e-6作为下界，实际调参时可以根据问题尺度调整。
4.4 LP 松弛求解器的封装
LP 求解我用的是自己实现的修正单纯形法，原因是：外逼近需要频繁求解结构相似的 LP（只差几个割平面），用通用求解器每次重建模型开销太大。自己实现可以复用基矩阵，加速迭代。
核心接口：
public interface LPSolver { LPSolution solve(double[] obj, double[][] A, double[] b, double[] lb, double[] ub); }LPSolution包含最优值、最优解、对偶变量。对偶变量在生成割平面时很有用，可以用来判断哪些约束是"紧"的。
踩坑记录：单纯形法的数值稳定性是个大问题。分式变换后的 LP 系数矩阵条件数可能很差，导致迭代震荡。我的解决办法是：在每次基变换后做一次"重新分解"（refactorization），用 LU 分解代替直接求逆。这样数值误差累积慢很多。
4.5 割平面生成与管理
割平面生成的核心逻辑：
public List<Cut> generateCuts(double[] xRelax, FractionalProblem prob) { List<Cut> cuts = new ArrayList<>(); // 1. 对每个违反的凸约束生成切平面 for (ConvexConstraint cc : prob.getConvexConstraints()) { double violation = cc.evaluate(xRelax); if (violation > 1e-6) { double[] grad = cc.gradient(xRelax); cuts.add(new Cut(grad, -cc.evaluate(xRelax) + dot(grad, xRelax))); } } // 2. 对分式项生成"分式割" for (FractionalTerm ft : prob.getFractionalTerms()) { Cut fracCut = generateFractionalCut(ft, xRelax); if (fracCut != null) cuts.add(fracCut); } return cuts; }割平面管理用一个CutPool类，支持去重（避免加入重复割）和老化（删除长期不活跃的割，控制 LP 规模）。
4.6 分支策略与搜索树实现
分支变量选择用伪成本分支（Pseudo-cost Branching）：记录每个变量历史上分支后下界改善的平均幅度，优先分支"改善潜力大"的变量。
public int selectBranchVar(double[] xRelax, double[] lb, double[] ub) { int bestVar = -1; double bestScore = -1; for (int i = 0; i < xRelax.length; i++) { if (Math.abs(xRelax[i] - Math.round(xRelax[i])) < 1e-6) continue; double score = pseudoCost[i] * Math.min(xRelax[i] - lb[i], ub[i] - xRelax[i]); if (score > bestScore) { bestScore = score; bestVar = i; } } return bestVar; }搜索树用优先队列实现，按节点下界排序。
4.7 主求解循环
主循环把上面所有模块串起来：
public SolverResult solve(FractionalProblem prob) { TransformedProblem tp = charnesCooper(prob); PriorityQueue<Node> queue = new PriorityQueue<>(byLowerBound()); queue.add(createRootNode(tp)); double globalUB = Double.POSITIVE_INFINITY; double[] bestSol = null; int nodeCount = 0; while (!queue.isEmpty() && nodeCount < MAX_NODES) { Node node = queue.poll(); if (node.getLowerBound() >= globalUB - EPS) continue; LPSolution lpSol = lpSolver.solve(node); if (lpSol == null) continue; if (isFeasible(lpSol, prob)) { double objVal = evaluateOriginal(lpSol, prob); if (objVal < globalUB) { globalUB = objVal; bestSol = lpSol.getX(); } continue; } List<Cut> cuts = generateCuts(lpSol.getX(), prob); if (!cuts.isEmpty()) { node.addCuts(cuts); queue.add(node); // 重新入队 continue; } // 分支 int branchVar = selectBranchVar(lpSol.getX(), node.getLb(), node.getUb()); if (branchVar == -1) continue; queue.addAll(branchNode(node, branchVar, lpSol.getX()[branchVar])); nodeCount++; } return new SolverResult(bestSol, globalUB, nodeCount); }这段代码是整个求解器的骨架。实际工程中还需要加日志、异常处理、超时中断等。
5. 参数调优与性能优化实录
5.1 关键参数及其影响
| 参数 | 含义 | 推荐值 | 影响 |
|---|---|---|---|
| EPS | 收敛间隙阈值 | 1e-4 | 越小越精确，但迭代次数增加 |
| MAX_NODES | 最大节点数 | 10000 | 控制内存和运行时间 |
| MAX_DEPTH | 最大分支深度 | 50 | 防止树过深 |
| CUT_TOL | 割平面违反容忍度 | 1e-6 | 越小割越多，LP越大 |
| CUT_AGE | 割平面老化阈值 | 20 | 控制割池规模 |
| PSEUDO_INIT | 伪成本初始值 | 1.0 | 影响分支变量选择 |
调参经验：EPS和CUT_TOL是最敏感的两个。EPS设太小（比如 1e-8）会导致迭代次数暴增；CUT_TOL设太小会生成大量冗余割，拖慢 LP 求解。
5.2 数值稳定性处理
分式变换后的 LP 系数矩阵条件数可能达到 1e10 以上，直接求解会出问题。我用了三个手段：
- 变量缩放：把变量范围归一化到 [0, 1] 区间，减少数量级差异。
- 系数缩放：对每行约束除以该行的最大系数绝对值。
- LU 重分解：每 50 次基变换做一次完整 LU 分解，清除累积误差。
5.3 割平面管理的优化
割平面太多会拖慢 LP 求解。我的策略是：
- 只保留"活跃割"（最近 10 次迭代中被违反过的割）
- 对割做正交化处理，删除线性相关的割
- 每个节点最多保留 100 个割
实测下来，这套策略能把 LP 求解时间降低 40% 左右。
5.4 并行化尝试
Branch-and-cut 天然适合并行：不同子树可以并行搜索。我用 Java 的ForkJoinPool做了尝试，把搜索树的前几层节点分给不同线程。
效果：在 8 核机器上，节点数 5000 左右的问题，运行时间从 120 秒降到 25 秒。但并行化引入了两个新问题：一是全局上界的同步开销，二是负载不均衡（有些子树特别大）。解决办法是用"工作窃取"策略，空闲线程从其他线程的队列尾部偷节点。
6. 常见问题与排查技巧实录
6.1 问题速查表
| 现象 | 可能原因 | 排查方法 | 解决方案 |
|---|---|---|---|
| 下界不收敛 | 割平面太松 | 打印每次迭代的 LB | 增加割平面类型 |
| LP 求解失败 | 数值不稳定 | 检查系数矩阵条件数 | 变量缩放+LU重分解 |
| 内存溢出 | 节点数爆炸 | 监控队列大小 | 降低 MAX_NODES |
| 结果不可行 | 变换不等价 | 验证 q(x)>0 | 加约束保证分母正 |
| 收敛到局部最优 | 分支不足 | 检查剪枝逻辑 | 放宽剪枝条件 |
| 运行时间过长 | 割太多 | 统计割池大小 | 启用割老化 |
6.2 三个最容易踩的坑
坑一：忽略分母正性条件。Charnes-Cooper 变换要求q(x) > 0。如果原问题没有显式保证这一点，变换后的问题可能和原问题不等价。我的做法是在变换前先求解一个辅助问题，找到q(x)的最小值，如果小于等于 0，就加约束把q(x)抬上去。
坑二：割平面重复加入。同一个割平面被反复加入 LP，导致 LP 规模膨胀。解决办法是用一个HashSet记录已加入的割（用割的系数向量做哈希），加入前先查重。
坑三：分支变量选择不当。如果总是分支第一个小数变量，搜索树会变得很不平衡。用伪成本分支能显著改善，但伪成本的初始值需要调。我一般先用 1.0，跑几个问题后根据实际改善幅度更新。
6.3 调试技巧
调试这类求解器，最有效的手段是可视化搜索树。我把每个节点的下界、上界、分支变量、割数量输出成 CSV，用 Python 画成树状图。一眼就能看出哪里剪枝不干净、哪里分支过深。
另一个技巧是小规模验证：构造一个变量数 ≤ 5、约束数 ≤ 3 的小问题，用暴力枚举验证求解器结果。如果小问题都对，大问题出错大概率是数值问题；如果小问题就错，那是逻辑问题。
6.4 性能基准测试
我在几个标准测试问题上跑了基准：
| 问题规模 | 变量数 | 分式项数 | 节点数 | 运行时间 | 间隙 |
|---|---|---|---|---|---|
| 小 | 10 | 2 | 45 | 0.8s | 1e-5 |
| 中 | 50 | 5 | 1200 | 18s | 1e-4 |
| 大 | 200 | 10 | 8500 | 210s | 1e-3 |
| 超大 | 500 | 20 | 超限 | 超时 | 未收敛 |
从数据看，变量数超过 200 后，节点数增长很快。这时候需要更强的割平面或者更好的分支策略。我试过加 Gomory 割，对整数变量有效，但对纯连续问题帮助不大。
7. 这套方法能用在哪些场景
含分式非线性规划在实际业务里比想象中常见。举几个我接触过的场景：
生产排程：目标函数是"总产出/总能耗"，约束是设备产能和库存平衡。分式项来自能效比。
选址问题：目标是最小化"总运输成本/服务覆盖人数"，分式项来自效率指标。
资源分配：目标函数是"总收益/总投入"，约束是预算和人力上限。
金融组合：目标是最大化"预期收益/风险"，这是经典的夏普比率优化，本质就是分式规划。
这些场景的共同点是：决策者关心的不是绝对量，而是"比值"或"效率"。用普通线性规划建模会丢失这个结构，用通用非线性求解器又容易陷局部最优。Outer Approximation + Branch-and-cut 正好填补了这个空白。
代码层面，这套实现可以封装成一个 Java 库，对外暴露solve(problem)接口。业务系统只需要把问题描述成FractionalProblem对象，剩下的交给求解器。我把它集成到一个排程系统里，替换掉原来的启发式算法后，能效指标提升了 12% 左右。
后续如果要扩展，有两个方向值得做：一是支持整数变量（变成混合整数分式规划），二是支持多目标（Pareto 前沿搜索）。前者需要在分支逻辑里加整数约束处理，后者需要改造成本函数的结构。这两个方向我还在摸索，等有成熟方案再单独写一篇。
最后分享一个实操小技巧：如果你的问题里分式项的分母是常数，那恭喜你，直接把它当线性项处理就行，不需要走 Charnes-Cooper 变换。我见过不少人把常数分母也套变换，白白增加计算量。判断方法很简单——看分母里有没有决策变量，没有就是常数。
