Very large-scale linear programming: A case study in combining interior point and simplex methods

Very large-scale linear programming: A case study in combining interior point and simplex methods

0.00 Avg rating0 Votes
Article ID: iaor19931173
Country: United States
Volume: 40
Issue: 5
Start Page Number: 885
End Page Number: 897
Publication Date: Sep 1992
Journal: Operations Research
Authors: , , , ,
Keywords: scheduling, personnel & manpower planning, transportation: air
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 arisng 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.

Reviews

Required fields are marked *. Your email address will not be published.