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.
|Research Programs:||System and Decision Sciences - Core (SDS)|
|Bibliographic Reference:||Mathematical Programming; 89(1):345-368 |
|Depositing User:||IIASA Import|
|Date Deposited:||15 Jan 2016 01:41|
|Last Modified:||26 Feb 2016 10:17|
Actions (login required)