Improved integer programming bounds using intersections of corner polyhedra
Improved integer programming bounds using intersections of corner polyhedra
复制标题
使用角多面体的交集改进整数规划边界
作者：
David E. Bell;M. Fisher
考虑一个整数规划（IP）问题的松弛性，其中可行域被线性规划（LP）可行域与特定LP基的角多面体的交点所取代。最近提出了一种原始-对偶上升算法来求解这种松弛。给定该松弛的最优解，我们陈述了选择关联松弛更强的新LP基的标准。可以依次应用这些准则来获得最优IP解决方案或该解决方案成本的下界。给出了可行IP解的凸壳和所有角多面体的交点相等的条件。
Consider the relaxation of an integer programming (IP) problem in which the feasible region is replaced by the intersection of the linear programming (LP) feasible region and the corner polyhedron for a particular LP basis. Recently a primal-dual ascent algorithm has been given for solving this relaxation. Given an optimal solution of this relaxation, we state criteria for selecting a new LP basis for which the associated relaxation is stronger. These criteria may be successively applied to obtain either an optimal IP solution or a lower bound on the cost of such a solution. Conditions are given for equality of the convex hull of feasible IP solutions and the intersection of all corner polyhedra.