Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods

Robert E. Bixby, John W. Gregory, Irvin J. Lustig, Roy E. Marsten and David F. Shanno
Additional contact information
Robert E. Bixby: Rice University, Houston, Texas
John W. Gregory: Cray Research, Inc., Eagan, Minnesota
Irvin J. Lustig: Princeton University, Princeton, New Jersey
Roy E. Marsten: Georgia Institute of Technology, Atlanta, Georgia
David F. Shanno: Rutgers University, New Brunswick, New Jersey

Operations Research, 1992, vol. 40, issue 5, 885-897

Abstract: Experience with solving a 12.753.313 variable linear program is described. This problem is the linear programming relaxation of a set partitioning problem arising from an airline crew scheduling application. A scheme is described that requires successive solutions of small subproblems, yielding a procedure that has little growth in solution time in terms of the number of variables. Experience using the simplex method as implemented in CPLEX , an interior point method as implemented in OBI , and a hybrid interior point/simplex approach is reported. The resulting procedure illustrates the power of an interior point/simplex combination for solving very large-scale linear programs.

Keywords: programming; linear: large-scale systems (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.5.885 (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:oropre:v:40:y:1992:i:5:p:885-897

Access Statistics for this article

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