Improved integer programming bounds using intersections of corner polyhedra

Bell, D.E. & Fisher, M.L. (1975). Improved integer programming bounds using intersections of corner polyhedra. Mathematical Programming 89 (1) 345-368. 10.1007/BF01580451.

Full text not available from this repository.

Abstract

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.

Item Type:	Article
Research Programs:	System and Decision Sciences - Core (SDS)
Bibliographic Reference:	Mathematical Programming; 89(1):345-368 [1975]
Depositing User:	IIASA Import
Date Deposited:	15 Jan 2016 01:41
Last Modified:	27 Aug 2021 17:35
URI:	https://pure.iiasa.ac.at/208

Actions (login required)

View Item