A Short-Cut Potential Reduction Algorithm for Linear Programming

John A. Kaliski and Yinyu Ye
Additional contact information
John A. Kaliski: Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242
Yinyu Ye: Department of Management Sciences, University of Iowa, Iowa City, Iowa 52242

Management Science, 1993, vol. 39, issue 6, 757-776

Abstract: As most interior point algorithms iterate, they repeatedly perform costly matrix operations, such as projections, on the entire constraint matrix. For large-scale linear programming problems, such operations consume the great majority of the computation time required. However, for problems where the number of variables far exceeds the number of constraints, operations over the entire constraint matrix are unnecessary. We will examine and extend decomposition techniques which greatly reduce the amount of work required by such interior point methods as the dual affine scaling and the dual potential reduction algorithms. In an effort to judge the practical viability of the decompositioning, we compare the performance of the dual potential reduction algorithm with and without decompositioning over a set of randomly generated transportation problems. Accompanying a theoretical justification of these techniques, we focus on the implementation details and computational results of one such technique.

Keywords: linear programming; potential reduction algorithms; transportation problem; decomposition; short-cut technique (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.39.6.757 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:39:y:1993:i:6:p:757-776

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().