A partial updating algorithm for linear programs with many more variables than constraints

Robert A. Bosch; Kurt M. Anstreicher

doi:10.1080/10556789508805591

Back

A partial updating algorithm for linear programs with many more variables than constraints

Journal article

Peer reviewed

A partial updating algorithm for linear programs with many more variables than constraints

Robert A. Bosch and Kurt M. Anstreicher

Optimization methods & software, Vol.4(4), pp.243-257

01/01/1994

DOI: 10.1080/10556789508805591

View Online

Abstract

We present a modified version of Ye's potential reduction algorithm for linear programming. By using partial updating and incorporating scaling factors based on subsets of variables, we are able to solve linear programs having many more variables than constraints faster than comparable full updating algorithms. Our scheme for choosing scaling factors is motivated by certain asymptotic properties of interior point methods.

Interior point method

Linear programming

partial updating

Potential reduction

rank-one updates

Details

Title: Subtitle: A partial updating algorithm for linear programs with many more variables than constraints
Creators: Robert A. Bosch - Oberlin College
Kurt M. Anstreicher - University of Iowa
Resource Type: Journal article
Publication Details: Optimization methods & software, Vol.4(4), pp.243-257
Publisher: Gordon and Breach Science Publishers
DOI: 10.1080/10556789508805591
ISSN: 1055-6788
eISSN: 1029-4937
Language: English
Date published: 01/01/1994
Academic Unit: Industrial and Systems Engineering; Computer Science; Business Analytics
Record Identifier: 9984380552202771

Metrics

1 Record Views