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

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1991
Accession Number
ADA452700

Entities

People

  • David F. Shanno
  • Irvin J. Lustig
  • John W. Gregory
  • Robert E. Bixby
  • Roy E. Marsten

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Case Studies
  • Computer Programming
  • Convex Programming
  • Information Operations
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research
  • Simplex Method
  • Systems Science

Readers

  • Operations Research