关于割平面法中Gomory约束构造的研究

Research about the Construction of Gomory Constraint in Cutting Plane Method

在使用割平面法求解整数规划时,寻找Gomory约束是其中最为关键的一步.一般地,选取非整数解变量中分数部分最大的一个基变量,写下相应行的约束.将这个约束等式中的系数进行整数和非负真分数的分解,再加上整数条件进行逼迫,得到一个小于等于0的不等式.从这个小于等于0的不等式出发,有五种方法构造Gomory约束.通过具体例子,详细讲解这五种方法,并进行比较,从而更加深刻地理解Gomory约束的构造,在以后的解题中可以灵活运用.

When using cutting plane method for solving integer programming,finding Gomory constraint is one of the key steps.In general,we choose the basis variable whose fraction is lagest among all variables of the non-integer solution.Then write the constraint in the corresponding row.By decomposing each coefficient in this equality constraint into an integer and a nonnegative proper fraction,we use integer conditions for persecution,and obtain an inequality which is less than or equal to zero.According to this inequality which is less than or equal to zero,five methods are summarizd,under which Gomory constraints are constructed.We give an example to illustrate and compare this five methods.Thus the readers can deeply understand the construction of Gomory constraint,and flexibly use the cutting plane method in the after.