Gomory Cut

释义 Definition

Gomory cut（戈莫里割/戈莫里切割平面）：整数规划中常用的一类割平面（cutting plane）不等式。它从线性规划松弛（LP relaxation）的分数解出发，构造出一个对所有整数可行解都成立、但会切掉当前分数解的新约束，用于逐步收紧可行域、逼近整数最优解。（也常说 Gomory fractional cut；此外还有 Gomory mixed-integer cut 等变体。）

发音 Pronunciation (IPA)

/omi kt/

例句 Examples

We added a Gomory cut to eliminate the fractional solution.
我们加入了一条戈莫里割来去除分数解。

After solving the LP relaxation, the solver generated several Gomory cuts and then re-optimized to improve the integer bound.
在求解线性规划松弛后，求解器生成了多条戈莫里割，并重新优化以改进整数界。

词源 Etymology

该术语以美国数学家与运筹学家 Ralph E. Gomory（拉尔夫E戈莫里） 命名。他在 20 世纪 50 年代提出并系统化了用于整数规划的割平面思想，“Gomory cut”即指其代表性的割平面构造方法。

文学与经典出处 Literary Works

R. E. Gomory，《An Algorithm for Integer Solutions to Linear Programs》（1958，学术论文，首次系统提出相关割平面方法）
George L. Nemhauser & Laurence A. Wolsey，《Integer and Combinatorial Optimization》（教材/专著中讲解 Gomory cuts 与割平面法）
Laurence A. Wolsey，《Integer Programming》（专著中涵盖 Gomory fractional cuts 与相关理论）
Alexander Schrijver，《Theory of Linear and Integer Programming》（理论专著中讨论割平面与多面体方法，包括 Gomory cuts）