VERY LARGE-SCALE LINEAR-PROGRAMMING - A CASE-STUDY IN COMBINING INTERIOR POINT AND SIMPLEX METHODS
成果类型：
Article
署名作者：
BIXBY, RE; GREGORY, JW; LUSTIG, IJ; MARSTEN, RE; SHANNO, DF
署名单位：
University System of Georgia; Georgia Institute of Technology; Princeton University; Rutgers University System; Rutgers University New Brunswick
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.5.885
发表日期：
1992
页码：
885-897
关键词：
摘要：
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 OB1, 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.