Improved Bounds for Integer Programs: A Supergroup Approach

Bell, D.E. (1973) Improved Bounds for Integer Programs: A Supergroup Approach. IIASA Research Memorandum. IIASA, Laxenburg, Austria, RM-73-005

[img]
Preview
Text
RM-73-005.pdf

Download (268kB) | Preview

Abstract

Recent work by Fisher and Shapiro has used Gomory's group theoretic methods together with Lagrange multipliers to obtain bounds for the optimal value of integer programs. Here it is shown how an extension of the associated abelian group to a supergroup can improve the bound without the artificiality of adding a cut. It is proved that there exists a finite group for which the dual ascent procedure of Fisher and Shapiro converges to the optimal integer solution. Constructive methods are given for finding this group. A worked example is included.

Item Type: Monograph (IIASA Research Memorandum)
Research Programs: System and Decision Sciences - Core (SDS)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 01:40
Last Modified: 27 Jul 2016 19:05
URI: http://pure.iiasa.ac.at/57

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313