Gomory Cut

释义 Definition

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

发音 Pronunciation (IPA)

/ˈɡoʊməɹi kʌt/

例句 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”即指其代表性的割平面构造方法。

相关词 Related Words

• Integer Programming
• Mixed-Integer Programming
• Linear Programming
• Cutting Plane
• Branch and Bound
• LP Relaxation
• Polyhedron
• Simplex Method

文学与经典出处 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）