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.

## 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: | http://pure.iiasa.ac.at/208 |

### Actions (login required)

View Item |