Branch-and-Cut

释义 Definition

branch-and-cut（分支-割平面法）：一种求解整数规划/混合整数规划的算法框架，把分支定界（branch-and-bound）与割平面（cutting planes）结合起来：在搜索树的各个节点上不断加入有效不等式（“割”）来收紧松弛问题，从而更快地排除不可行或非最优区域，常用于如旅行商问题等组合优化。

发音 Pronunciation (IPA)

/ˌbræntʃ ən ˈkʌt/

例句 Examples

We solved the model using a branch-and-cut algorithm.
我们用分支-割平面算法求解了这个模型。

The solver’s branch-and-cut procedure added cuts at several nodes to tighten the LP relaxation and speed up convergence.
求解器的分支-割平面过程在多个节点加入割平面，以收紧线性规划松弛并加快收敛。

词源 Etymology

该术语由两个优化领域常用词组合而成：branch（分支）指在搜索过程中对变量取值进行分裂形成搜索树；cut（割）源自割平面法，意为加入新的线性不等式“切掉”松弛解空间中不该存在的部分。作为复合术语，体现了两类方法的融合。

相关词 Related Words

• Branch-and-Bound
• Cutting-Plane
• Integer-Programming
• Mixed-Integer-Programming
• Linear-Programming
• LP-Relaxation
• Gomory-Cut
• Combinatorial-Optimization
• Traveling-Salesman-Problem
• Solver

文学/著作中的用例 Literary / Notable Works

• Integer and Combinatorial Optimization（Nemhauser & Wolsey）
• Integer Programming（Laurence A. Wolsey）
• The Traveling Salesman Problem: A Computational Study（Applegate, Bixby, Chvátal, Cook）
• Handbook of Combinatorial Optimization（相关章节常讨论 branch-and-cut 框架）