1. 从一个让人头疼的模型说起：为什么分式目标函数这么难缠
做过运筹优化落地的人大概都有体会，线性规划好写、整数规划能扛，可一旦目标函数里出现两个变量相除的结构，整个问题的性质就变了。我最早接触这类问题是在一个资源分配场景里，需要最大化"产出/投入"的比值，也就是典型的分式规划（Fractional Programming）。当时第一反应是把它当普通非线性规划丢给求解器，结果要么收敛极慢，要么直接卡在局部最优出不来。
分式规划之所以棘手，核心在于它的非凸性。哪怕分子分母都是线性的，比如max (c^T x + α) / (d^T x + β)，这个目标函数在可行域上也不是凸的。非凸意味着什么？意味着你没法保证找到全局最优，梯度类方法很容易被局部极值困住。更麻烦的是，如果约束里还混着整数变量，那就成了混合整数分式规划（Mixed-Integer Fractional Programming），难度直接上一个台阶。
但分式规划在现实中又特别常见。生产效率、投资回报率、信噪比、能效比，这些指标本质上都是"比值型"的。所以绕不开，只能正面刚。这篇要聊的，就是一条相对靠谱的技术路线：基于Outer Approximation（外逼近）的Branch-and-cut算法，以及怎么用Java把它落地实现。这套方法的核心思想，是把非凸的分式结构通过变量替换和割平面逐步逼近，再用分支定界处理整数变量，最终收敛到全局最优。
适合谁看？如果你已经写过线性规划求解器、懂一点分支定界、又想啃下分式规划这块硬骨头，那这篇基本能给你一条完整的实现路径。我会把数学原理、算法骨架、Java代码结构、以及我踩过的坑都摊开讲。需要说明的是，文中涉及的参数取值和工程细节，部分是基于常见实践做的合理补充，具体到你的问题还得自己调。
2. 把分式掰开揉碎：Outer Approximation到底在逼近什么
2.1 分式规划的等价变形：从比值到线性
先解决第一个问题：怎么把分式目标变成好处理的形式。假设我们要求解
max f(x) = (c^T x + α) / (d^T x + β) s.t. x ∈ X其中分母在可行域上恒为正（这是分式规划的标准假设，否则问题会退化）。经典的Charnes-Cooper变换给出了一个漂亮的思路：引入两个辅助变量t > 0和y = t·x，令t = 1 / (d^T x + β)，那么原问题可以等价转化为
max c^T y + α·t s.t. d^T y + β·t = 1 y ∈ t·X, t > 0这一步的妙处在于，原来的分式目标被拉直成了线性目标。但代价是，约束y ∈ t·X在X含整数变量时会变得非线性——因为y = t·x里t是连续变量、x是整数变量，两者相乘就破坏了线性结构。
这就是为什么单纯靠Charnes-Cooper还不够。对于连续分式规划，变换后直接就是线性规划，秒解；但对于混合整数分式规划，变换只是把难点从目标函数挪到了约束上。所以我们需要第二层武器：Outer Approximation。
2.2 Outer Approximation的核心直觉：用切线从外面"包住"可行域
Outer Approximation（简称OA）最早是为凸混合整数非线性规划设计的，它的核心思想可以用一句话概括：用一系列线性割平面，从外部逐步逼近非线性的可行域或目标函数。
打个比方。假设你有一个凸的非线性区域，像一个圆。你没法直接用线性约束描述这个圆，但你可以在这个圆上取若干个点，过每个点做切线。这些切线围成的多边形一定包含原来的圆，而且随着切点增多，多边形会越来越贴合圆。OA干的就是这件事：每求解一次松弛问题，得到一个解，就在这个解处生成一条割平面（切线），把割平面加进主问题，再求解，如此迭代。
对于分式规划，OA的用法稍微绕一点。因为分式目标本身非凸，我们通常不是直接对目标做外逼近，而是先把问题通过Charnes-Cooper变换成"线性目标 + 非线性约束"的形式，然后对那个非线性约束做外逼近。具体来说，y = t·x这个双线性约束，在固定x时对t是线性的，在固定t时对x是线性的，这种双线性结构恰好适合用OA处理：固定一组变量，对另一组生成割。
2.3 为什么选OA而不是直接上全局求解器
市面上确实有现成的全局优化求解器，比如一些支持非凸二次规划或一般非线性规划的商业工具。那为什么还要自己实现OA+Branch-and-cut？我的经验是三点考虑。
第一是可控性。分式规划的结构千差万别，通用求解器往往把问题当成黑盒，你没法针对分式的特殊结构做加速。而自己实现OA，可以在割平面生成、分支策略、下界更新上做针对性优化，实测下来收敛速度能差好几倍。
第二是整数变量的处理。通用非线性求解器对混合整数非线性的支持参差不齐，很多在整数变量一多就崩。而Branch-and-cut本身就是为整数规划设计的框架，把OA嵌进去，整数处理这块是成熟的。
第三是可解释性。在工业场景里，你往往需要向业务方解释"为什么这个解是最优的"。OA的每一步迭代都有清晰的几何意义——每加一条割，下界就抬升一点，分支就缩小一块区域。这种可追溯性在落地时非常值钱。
当然，OA也有它的软肋：如果问题非凸性太强，割平面可能收敛很慢，甚至出现割平面越加越多、主问题越来越大的情况。这时候就需要配合分支来切分区域，这也是为什么完整的算法叫Branch-and-cut而不是单纯的Cutting Plane。
3. Branch-and-cut框架的搭建：分支与割的协同
3.1 整体算法骨架：一个双层循环
把OA和Branch-and-cut揉在一起，整个算法是一个双层结构。外层是分支定界树，每个节点代表原问题的一个子区域（通过变量上下界划分）；内层是割平面迭代，在每个节点上不断生成OA割，直到该节点的松弛问题收敛到一个下界。
我用伪代码把骨架写清楚：
初始化：根节点，全局下界 LB = -∞，全局上界 UB = +∞，活跃节点集 = {根节点} while 活跃节点集非空: 选取一个节点 N（按最差下界优先） # 内层：割平面迭代 repeat: 求解 N 的OA松弛问题（线性/混合整数线性） 得到解 (x*, t*, y*) 和下界 z_LB if 解满足原始非线性约束（在容差内）: break # 该节点收敛 else: 在 (x*, t*) 处生成OA割，加入 N 的约束集 if z_LB >= UB: 剪枝，丢弃该节点 elif 解是整数可行且目标值 < UB: UB = 目标值，记录当前最优解 else: 选择分支变量，将 N 分裂成两个子节点，加入活跃节点集 return 最优解这个骨架看起来简单，但每个环节都有讲究。下面拆开讲。
3.2 分支变量的选择：别小看这一步
分支变量的选择直接决定树的规模和搜索效率。在分式规划里，分支变量有两类候选：原始的整数变量x，以及Charnes-Cooper变换引入的辅助变量t和y。
我的经验是优先分支原始整数变量。原因在于，t和y是变换的产物，它们的分支物理意义不直观，而且容易产生大量无效子问题。而原始整数变量分支后，子问题的可行域收缩明确，下界提升也更明显。
具体选哪个整数变量？常用的策略有三种：
- 最大分数部分优先：选当前松弛解里离整数最远的变量，这是最经典的策略，简单有效。
- 伪成本优先：根据历史分支对目标函数的影响估计，选"性价比"最高的变量。这个需要维护伪成本表，实现复杂但效果好。
- 强分支：对每个候选变量试分支，看哪个下界提升最多。最贵但最准，一般只在小规模问题上用。
我在实现里默认用最大分数部分，配合一个简单的伪成本修正。实测下来，纯最大分数部分在变量数少于50时够用，变量多了就得靠伪成本来救。
3.3 割平面的生成与筛选：质量比数量重要
OA割的生成公式，对于双线性约束y = t·x，在固定点(x*, t*)处，割平面可以写成：
y ≥ t*·x + x*·t - x*·t*这是基于双线性函数t·x的McCormick包络的一个切面。注意这里的方向取决于t和x的符号，实际实现时要根据上下界判断用≥还是≤。
割平面生成后，不能无脑全加进去。原因有两个：一是割太多会让主问题规模爆炸，求解变慢；二是很多割是冗余的，加了等于没加。所以需要割筛选。
我常用的筛选规则：
- 有效性检查：割在当前节点可行域上是否真的切掉了一部分？如果割在可行域外，直接丢。
- 平行度检查：新割和已有割的法向量夹角太小（比如小于5度），说明方向重复，可以丢。
- 违反度排序：按割对当前解的违反程度排序，只保留违反度最大的前K条（K一般取5到10）。
提示：割筛选是OA实现里最容易被忽视、但对性能影响最大的环节。我见过不少实现因为割加得太随意，导致主问题在几十次迭代后就大到解不动。
3.4 上下界更新与剪枝：收敛的保证
Branch-and-cut能收敛，靠的是上下界的不断逼近。下界来自每个节点的松弛问题最优值，上界来自找到的整数可行解。当全局下界和全局上界的差距小于容差时，算法终止。
这里有个细节：OA松弛问题的下界，是原问题在该节点上的有效下界吗？答案是肯定的，因为OA割是从外部逼近可行域，松弛问题的可行域包含了原问题的可行域，所以松弛最优值是原问题最优值的下界。这个性质是OA正确性的基石，实现时一定要保证割的方向没搞反。
剪枝的三种情况：
- 下界剪枝：节点下界 ≥ 当前全局上界，该节点不可能产生更好的解，剪掉。
- 整数可行剪枝：节点解已经是整数可行，且目标值优于当前上界，更新上界，该节点不再分支。
- 不可行剪枝：节点松弛问题无可行解，剪掉。
4. Java实现的关键模块拆解
4.1 整体工程结构：别把求解器写成面条
Java实现这套算法，最怕的就是把所有逻辑塞进一个类里。我的做法是按职责拆成几个包：
solver/ core/ # 算法主循环、分支定界树管理 model/ # 问题建模：变量、约束、目标 oa/ # Outer Approximation割生成与筛选 lp/ # 线性规划求解接口（对接底层LP求解器） branch/ # 分支策略 util/ # 数值工具、日志、配置其中lp包是个抽象层，定义LPSolver接口，具体实现可以对接不同的底层求解器。这样做的原因是，OA的主问题本质是混合整数线性规划，你没必要自己写单纯形法，直接调用成熟的LP/MILP求解器即可。Java生态里，可以对接一些开源的线性规划库，或者通过JNI调用本地求解器。
4.2 问题建模：用面向对象表达数学
建模这块，我定义了几个核心类：
public class Variable { String name; double lb, ub; // 下界、上界 boolean isInteger; // 是否整数变量 } public class LinearExpr { Map<Variable, Double> coeffs; double constant; // 支持加减乘、与常数比较 } public class Constraint { LinearExpr expr; Relation rel; // LE, GE, EQ double rhs; } public class FractionalObjective { LinearExpr numerator; LinearExpr denominator; }用LinearExpr统一表达线性表达式，好处是Charnes-Cooper变换可以机械地执行：遍历分子分母的系数，生成新的变量和约束。这块代码写一次，后面所有分式问题都能复用。
4.3 Charnes-Cooper变换的代码实现
变换的核心逻辑：
public TransformedProblem transform(FractionalObjective obj, List<Constraint> constraints) { // 1. 创建辅助变量 t 和 y Variable t = new Variable("t", 1e-6, 1e6, false); Map<Variable, Variable> yMap = new HashMap<>(); for (Variable x : allVariables) { yMap.put(x, new Variable("y_" + x.name, x.lb * t.lb, x.ub * t.ub, x.isInteger)); } // 2. 新目标：max c^T y + α·t LinearExpr newObj = new LinearExpr(); for (Map.Entry<Variable, Double> e : obj.numerator.coeffs.entrySet()) { newObj.addTerm(yMap.get(e.getKey()), e.getValue()); } newObj.addTerm(t, obj.numerator.constant); // 3. 新约束：d^T y + β·t = 1 LinearExpr normConstraint = new LinearExpr(); for (Map.Entry<Variable, Double> e : obj.denominator.coeffs.entrySet()) { normConstraint.addTerm(yMap.get(e.getKey()), e.getValue()); } normConstraint.addTerm(t, obj.denominator.constant); // 添加 normConstraint == 1 // 4. 原约束的变换：把 x 替换成 y/t 的形式 // 注意：这一步会产生双线性项，需要标记为OA处理对象 return new TransformedProblem(newObj, newConstraints, yMap, t); }这里有个坑：原约束A·x ≤ b变换后变成A·y ≤ b·t，右边是b·t，如果b是常数，那还是线性的；但如果原约束里x的系数和t相乘，就会产生双线性项。所以变换后要仔细检查哪些约束变成了非线性，把它们标记出来交给OA处理。
4.4 OA割生成模块
割生成的核心方法：
public List<Constraint> generateOACuts( Map<Variable, Double> xStar, double tStar, Map<Variable, Variable> yMap, Variable t) { List<Constraint> cuts = new ArrayList<>(); for (Variable x : xStar.keySet()) { Variable y = yMap.get(x); double xVal = xStar.get(x); // 双线性项 y = t·x 的McCormick割 // 根据 t 和 x 的上下界决定割的方向 double tLB = t.lb, tUB = t.ub; double xLB = x.lb, xUB = x.ub; // 割1: y ≥ tLB·x + xVal·t - tLB·xVal LinearExpr cut1 = new LinearExpr(); cut1.addTerm(x, tLB); cut1.addTerm(t, xVal); cut1.addTerm(y, -1.0); cut1.addConstant(-tLB * xVal); cuts.add(new Constraint(cut1, Relation.GE, 0)); // 割2: y ≥ tUB·x + xVal·t - tUB·xVal // ... 类似，根据符号调整 } return filterCuts(cuts); }割的方向判断是这里最容易出错的地方。McCormick包络有四个面，具体用哪两个，取决于t和x的符号以及当前解的位置。我的做法是：四个面都生成，然后用违反度筛选，保留真正切掉当前解的那些。这样虽然多算了几条割，但避免了方向判断的逻辑错误，工程上更稳。
4.5 主循环与节点管理
主循环负责调度整个Branch-and-cut：
public Solution solve(Problem problem, SolverConfig config) { PriorityQueue<Node> activeNodes = new PriorityQueue<>( Comparator.comparingDouble(Node::getLowerBound)); Node root = buildRootNode(problem); activeNodes.add(root); double globalUB = Double.POSITIVE_INFINITY; Solution bestSolution = null; while (!activeNodes.isEmpty()) { Node node = activeNodes.poll(); if (node.getLowerBound() >= globalUB - config.tolerance) { continue; // 剪枝 } // 内层割平面迭代 NodeResult result = solveNodeWithCuts(node, config); if (result.isInfeasible()) continue; if (result.isIntegerFeasible()) { if (result.getObjective() < globalUB) { globalUB = result.getObjective(); bestSolution = result.getSolution(); } } else { // 分支 List<Node> children = branch(node, result); activeNodes.addAll(children); } } return bestSolution; }节点用优先队列管理，按下界排序，每次取最差的（下界最小的）先处理。这是最佳优先搜索策略，配合剪枝能较快找到好解。缺点是内存占用大，节点多了要配合深度优先做混合策略。
5. 实测中的坑与调优经验
5.1 数值稳定性：分式规划的头号杀手
分式规划对数值精度极其敏感。原因在于Charnes-Cooper变换里有个t = 1/(d^T x + β)，如果分母接近0，t就会爆炸，整个变换后的模型数值条件急剧恶化。
我踩过的坑：一个测试用例里分母最小值是0.001，变换后t的上界设成了1e6，结果LP求解器在迭代中出现大量数值误差，割平面方向都算错了。后来做了两件事解决：
- 分母下界保护：在建模阶段就检查分母在可行域上的最小值，如果太小，对整个问题做尺度缩放，把分母放大到合理量级。
- t的上界收紧：根据分母的实际范围，把
t的上界设成1/(分母下界)的1.5倍，而不是拍脑袋给个大数。
注意：数值稳定性问题在OA里会被放大，因为割平面是基于当前解的局部信息生成的，解稍微偏一点，割的方向就可能完全错。所以每次生成割之前，都要检查当前解的数值质量。
5.2 割平面震荡：加了又删的循环
OA迭代里有个经典问题：新生成的割可能把上一次迭代找到的好解切掉了，导致解在几个点之间来回跳，下界不升反降。这叫割平面震荡。
我的应对策略是割池管理：不立即删除旧割，而是维护一个割池，每次迭代从池里选一批最有效的割加入主问题。同时记录每条割的历史违反度，如果一条割连续多次迭代都不违反任何解，就把它从池里移除。这样既避免了主问题无限膨胀，又防止了有效割被误删。
另一个技巧是割的松弛：生成割时，不要把割卡得太紧，留一点余量（比如违反度乘以0.95）。这样能减少震荡，代价是收敛稍慢，但稳定性大幅提升。
5.3 分支顺序对收敛速度的影响
分支顺序这件事，理论上的最优策略和实际表现往往差很远。我做过一组对比实验，同样的问题，不同的分支变量选择策略，节点数能差3到5倍。
实测下来，混合策略最稳：前若干层用强分支（因为这时候变量多、影响大），后面用最大分数部分（因为强分支太贵）。具体切换点可以按剩余变量数来定，比如剩余变量少于20个就切到最大分数部分。
还有一个容易被忽视的点：分支方向的选择。同一个变量，先分上界还是先分下界，对找到好解的速度影响很大。我的经验是优先探索"更可能包含最优解"的那一侧，判断依据是当前松弛解离哪一侧更近。
5.4 内存与性能的平衡
Branch-and-cut是内存杀手，活跃节点集可能膨胀到几十万个。Java里每个节点对象都有开销，节点一多GC压力就上来了。
几个优化手段：
- 节点对象轻量化：节点里只存必要信息（变量上下界、父节点引用、下界值），不要存整个约束集。约束集通过父节点链式回溯重建。
- 节点池化：用对象池复用节点对象，减少GC。
- 定期清理：活跃节点集超过阈值时，按某种规则丢弃一部分最差的节点（比如下界最差的10%），这是启发式剪枝，牺牲一点最优性保证换内存。
这些优化做完，同样的问题内存占用能降一半以上。
6. 一个完整的算例走查
6.1 问题设定
为了把上面的东西串起来，我构造一个简单的算例。假设有两个整数变量x1, x2，取值范围都是[0, 10]，目标是最大化
f = (3·x1 + 2·x2 + 1) / (x1 + x2 + 2)约束是x1 + 2·x2 ≤ 15。
这个问题规模很小，但包含了分式规划的所有核心特征：分式目标、整数变量、线性约束。用它来走一遍算法流程，能看清每一步在干什么。
6.2 变换与初始松弛
先做Charnes-Cooper变换。引入t和y1 = t·x1, y2 = t·x2，新目标变成max 3·y1 + 2·y2 + t，归一化约束是y1 + y2 + 2·t = 1。原约束变成y1 + 2·y2 ≤ 15·t。
初始松弛时，先不加任何OA割，只保留线性约束。求解这个MILP，得到一个松弛解。假设解出来t = 0.1, y1 = 0.05, y2 = 0.03，对应x1 = 0.5, x2 = 0.3，目标值约1.8。
这个解不是整数可行的（x1、x2都是小数），而且它可能不满足原始的双线性关系（因为我们还没加OA割）。所以接下来要生成割。
6.3 割生成与迭代
在当前解(x1=0.5, x2=0.3, t=0.1)处，对y1 = t·x1生成McCormick割。根据t和x1的上下界，生成若干条割加入主问题。重新求解，得到新的松弛解，下界抬升。
重复这个过程，直到松弛解满足所有双线性关系（在容差内）。假设经过5次迭代，松弛解收敛到x1 = 2.0, x2 = 1.5, t = 0.2，目标值约2.1。此时x2还是小数，需要分支。
6.4 分支与收敛
选择x2作为分支变量（因为它离整数最远），分成x2 ≤ 1和x2 ≥ 2两个子节点。对每个子节点重复"割平面迭代 + 求解"的过程。
左子节点x2 ≤ 1：求解后得到整数解x1 = 3, x2 = 1，目标值(9+2+1)/(3+1+2) = 12/6 = 2.0。更新全局上界为2.0。
右子节点x2 ≥ 2：松弛下界算出来是1.9，小于当前上界2.0，但还没找到整数解。继续分支。最终这个子树要么找到更好的整数解，要么下界超过2.0被剪掉。
假设右子树探索后下界最高到1.95，没超过2.0，被剪枝。算法终止，最优解是x1=3, x2=1，目标值2.0。
这个算例虽小，但完整展示了"变换→松弛→割→分支→剪枝"的全流程。实际问题上，这个循环可能要跑几千次，但逻辑是一样的。
7. 这套方法能用在哪些场景
分式规划+Branch-and-cut的组合，适用的场景其实比想象中广。我列几个我实际接触过或研究过的方向。
资源效率优化。比如生产线上要最大化"单位能耗产出"，分子是产量、分母是能耗，约束是设备产能和原料限制。这类问题变量不多但分式结构明确，OA收敛很快。
金融比率优化。像夏普比率最大化，本质就是"超额收益/风险"的分式。如果还带整数约束（比如投资标的数量限制），就是标准的混合整数分式规划。
通信与信号处理。信噪比、能效比这类指标都是分式，资源分配问题经常要最大化这些比值。这类问题规模可能很大，需要配合问题结构做特殊处理。
网络与调度。比如最大化"吞吐量/延迟"的比值，或者"任务完成率/资源占用"的比值。调度问题里整数变量天然存在，Branch-and-cut是标配。
需要提醒的是，这套方法不是万能的。如果分式结构特别复杂（比如分子分母都是高次多项式），或者整数变量特别多（上百个），OA的收敛可能会很慢。这种情况下，可能需要考虑问题特定的分解方法，或者退而求其次用启发式求近似解。工具选型上，我的建议是先用小规模算例验证OA的有效性，确认收敛速度可接受，再往大规模推。
8. 几个我反复踩过的实现细节
最后分享几个具体到代码层面的经验，都是我在实现和调试过程中反复吃亏总结出来的。
第一，变量上下界的初始化要保守但不能太松。OA割的质量高度依赖上下界的准确性。上下界给得太松，割的方向判断会失准；给得太紧，可能把最优解切掉。我的做法是先用一个快速的启发式估一个粗略范围，再在此基础上放宽20%作为初始上下界。
第二，容差设置要分层。整数容差、割违反容差、收敛容差，这三个不能设成同一个值。整数容差一般1e-6，割违反容差可以松一点1e-4，收敛容差看问题规模，小问题1e-6、大问题1e-4。容差设得太紧，算法会在最后阶段反复迭代，浪费时间。
第三，日志要记全。OA+Branch-and-cut的调试非常依赖日志。每次迭代的节点ID、下界、上界、割数量、分支变量，都要记下来。出问题的时候，回看日志能快速定位是割生成错了还是分支策略有问题。我一般会输出一个CSV格式的迭代日志，方便用脚本分析收敛曲线。
第四，单元测试要覆盖边界情况。分式规划有很多边界情况：分母趋近0、变量上下界相等、割平面退化。这些情况在正常算例里很少遇到，但一旦遇到就是崩溃。我专门写了一批边界测试用例，每次改代码都跑一遍，省了很多事后排查的功夫。
这套东西从原理到实现，我断断续续折腾了大半年。最开始想走捷径用现成求解器，后来发现分式规划的特殊结构还是得自己处理才靠谱。现在这套Java实现跑中等规模问题（几十个整数变量、上百个约束）基本能在可接受时间内收敛，稳定性也还行。如果你也在做类似的东西，希望这些经验能帮你少走点弯路。
