Browse Prior Art Database

Partially Normalized Pivot Selection in Linear Programming

IP.com Disclosure Number: IPCOM000084160D
Original Publication Date: 1975-Sep-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Crowder, HP: AUTHOR [+2]

Abstract

By changing the usual pivot selection rule in the simplex method for linear programming, the number of basis changes required to solve problems may be significantly decreased. The usual pivot choice rule in the simplex method is to choose that nonbasic column which has the most negative reduced cost, c(j).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 83% of the total text.

Page 1 of 1

Partially Normalized Pivot Selection in Linear Programming

By changing the usual pivot selection rule in the simplex method for linear programming, the number of basis changes required to solve problems may be significantly decreased. The usual pivot choice rule in the simplex method is to choose that nonbasic column which has the most negative reduced cost, c(j).

It has been shown that if the method of fully normalized pivot column selection is used instead of the usual rule, this can, in some cases, reduce the number of simplex iterations by almost 50 per cent [1]. The pivot selection rule for the fully normalized method is:

(Image Omitted)

where a(i) are the updated 1.p. tableau entries. While no better pivot choice rule in terms of iteration counts is known, this fully normalized method requires too much computation to be of practical value.

In our partially normalized pivot selection procedure, a subset of the column entries are used to construct an approximation to the full norm; the pivot selection rule becomes:

It has been shown in [1] that this partial norm method is comparable to the DEVEX procedure (Harris' DEVEX method for approximating the full norm is given in [2]. The primary advantages of the partial norm method over DEVEX are; (1) the DEVEX approximation to the full norm of the pivot columns degrades after a few iterations and requires restarting; this method does not need restarting; and (2) the method is amenable to multiple pricing codes while...