Gomory割平面的构造方式与选择标准  

Construction and Selection for Gomory Cutting Plane

作　　者：杨静蕾[1] 梁恬宁 张建勇[1] YANG Jing-lei;LIANG Tian-ning;ZHANG Jian-yong(Business School,Nankai University,Tianjin 300071,China)

机构地区：[1]南开大学商学院,天津300071

出　　处：《数学的实践与认识》2020年第15期246-252,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(61772290)。

摘　　要：本文从Gomory割平面构造原理出发,在证明了利用Gomory割平面法则导出的整数和真分数两种割平面等价的基础上,将当前Gomory割平面分为标准割平面和化整割平面两类.其次,通过比较两类割平面,指出化整割平面存在使系数向量压缩,从而导致化整割平面构造困难的不足;最后,在扩大割平面备选集合和改进备选方程选择标准的基础上,给出了更为系统的Gomory割平面选择方法.Based on the construction principle of Gomory cutting plane,this paper firstly proves that two kinds of cutting plane,which are exported respectively from the integer side and the proper fraction side of Gomory constraint,is equivalent.Then,all the currently-discussed Gomory cutting planes are divided into two categories:Standard Cutting Plane(SCP for short)and Integerized Cutting Plane(ICP for short).Further,it is pointed out that ICP has the disadvantage of compressing the coefficient vector and leading to the difficulty of the ICP construction when comparing with SCP.Finally,this paper presents a more systematic Gomory cutting plane selection method by expanding the candidate set of cutting plane construction and enhancing the criteria of cutting plane selection.

关 键 词：Gomory割平面 割平面构造 割平面选择 整数规划 

分 类 号：O221.4[理学—运筹学与控制论]