论文标题
关于chvatal-gomory闭合的概括
On a generalization of the Chvatal-Gomory closure
论文作者
论文摘要
许多实用的整数编程问题涉及一个或两侧界限的变量。 Dunkel and Schulz（2012）考虑了在变量上使用0-1界限的Chvatal-Gomory（CG）不平等的增强版本，并表明满足所有这些增强这些不平等的理性多层点的点集是一件多人。最近，我们通过考虑使用所有可变界限的加强CG不平等现象来概括这一结果。在本文中，我们不仅考虑变量界限，而且对变量的一般线性约束进行进一步概括。我们表明，满足这种增强CG不平等的有理多面体中的所有点形成了有理多面体。我们还考虑由线性约束定义的混合组集，通过定义整数变量上加强的CG不等式来扩展多面体结果。
Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use all variable bounds. In this paper, we generalize further by considering not just variable bounds, but general linear constraints on variables. We show that all points in a rational polyhedron that satisfy such strengthened CG inequalities form a rational polyhedron. We also consider mixed-integer sets defined by linear constraints, to which we extend our polyhedrality result by defining the strengthened CG inequalities on integer variables.
