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

Construction and Selection for Gomory Cutting Plane

本文从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.